reverse_polish_notation.py

from operator import (
    add,
    sub,
    mul,
    div,
    mod,
    pow
)

def parse_string(input_string):
    parsed_list = input_string.split(" ")
    return_list = []
    for element in parsed_list:
        if element.isdigit():
            return_list.append(int(element))
        else:
            return_list.append(element)
    return return_list

def reverse_combine_polish_list(input_list):
    number_storage = []
    operator_map = {
        "+": add,
        "-": sub,
        "*": mul,
        "/": div,
        "%": mod,
        "^": pow
    }
    for element in input_list:
        if isinstance(element, int):
            number_storage.append(element)
        else:
            operator    = operator_map.get(element, None)
            if operator is None:
                raise ValueError("The operator {0} is not supported".format(element))
            if len(number_storage) < 2:
                raise Exception('Invalid')
            value_1     = number_storage.pop()
            value_2     = number_storage.pop()
            number_storage.append(operator(value_2, value_1))
    if len(number_storage) != 1:
        raise Exception('Invalid')
    return number_storage[0]

def reverse_polish_notation(input_string):
    parsed_list = parse_string(input_string)
    return reverse_combine_polish_list(parsed_list)


####
## Tests
####

def test_function(actual, expected, helper=None):
    if helper is None:
        print "#######################"
    else:
        print "######## {0} ##########".format(helper)
    print "Expected {0}: Actual {1}".format(expected, actual)
    print expected == actual
    print "#######################"


print "PARSE STRING TESTS"
test_function(parse_string("3 4 +"), [3, 4, "+"], "PARSE ADDITION")
test_function(parse_string("3 4 -"), [3, 4, "-"], "PARSE SUBTRACTION")


print "COMBINE POLISH LIST TESTS"
test_function(reverse_combine_polish_list([3, 4, "+"]), 7)
test_function(reverse_combine_polish_list([3, 5, "+"]), 8)
test_function(reverse_combine_polish_list([2, 8, "+"]), 10)
test_function(reverse_combine_polish_list([20, 15, "+"]), 35)
test_function(reverse_combine_polish_list([-3, 4, "+"]), 1)
test_function(reverse_combine_polish_list([10, 5, "-"]), 5)
test_function(reverse_combine_polish_list([4, 10, "-"]), -6)
test_function(reverse_combine_polish_list([0, -10, "-"]), 10)
test_function(reverse_combine_polish_list([1, 2, 4, "+", "+"]), 7)
test_function(reverse_combine_polish_list([1, 3, 8, "+", "-"]), -10)


print "POLISH NOTATION FUNCTION TESTS"
test_function(reverse_polish_notation("3 4 +"), 7)
test_function(reverse_polish_notation("2 7 +"), 9)
test_function(reverse_polish_notation("1 4 +"), 5)

test_function(reverse_polish_notation('5 1 2 + 4 * 3 - +'), 14)
test_function(reverse_polish_notation('4 2 5 * + 1 3 2 * + /'), 2)
test_function(reverse_polish_notation('3 4 5 * +'), 23)
test_function(reverse_polish_notation('5 1 2 + 4 * 3 - +'), 14)
test_function(
    reverse_polish_notation(
        '42 3 + 5 * 6 3 / 2 % - 3000 + 4000 3 % - 4 2 / + 14 + 7 3 4 * * - 14 +'
    ),
    3170
)
test_function(reverse_polish_notation('42 62 -'), -20)
test_function(reverse_polish_notation('42 3 * 15 + 6 5 - *'), 141)
test_function(
    reverse_polish_notation(
        '42 3 + 5 * 6 3 / 2 % - 3000 + 4000 - 3 % 4 2 / + 14 + 7 3 4 * * - 14 +'
    ),
    -52
)
test_function(reverse_polish_notation('5 17 - 52 8 9 6 7 * + - + *'), -108)
test_function(reverse_polish_notation('5 1 2 + 4 * + 3 -'), 14)
test_function(reverse_polish_notation('4 7 3 * 14 + - 8 9 10 * * /'), -1)

test_function(reverse_polish_notation('5 2 ^ 4 -'), 21)
test_function(reverse_polish_notation('4 3 ^ 8 / 7 3 * +'), 29)

try:
    test_function(reverse_polish_notation('4 2 #'))
except ValueError as e:
    test_function(e.message, 'The operator # is not supported')

try:
    test_function(reverse_polish_notation('4 2 4 *'))
except Exception as e:
    test_function(e.message, 'Invalid')

try:
    test_function(reverse_polish_notation('4 2 * *'))
except Exception as e:
    test_function(e.message, 'Invalid')


###
# Notes
###

# 1 2 4 + +
# 1 (2 4 +) +
# 3 4 + => 7
# 2 7 + => 9
# 1 4 + => 5
# 4 4 - => 0
# [1, 2, 4, "+", "+"]

# number_list = [1, 2, 4]
# number_list[-1], number_list[-2]
# add(last_element, second_to_last_element)
# number_list.append(6) # => [1, 6]
# sum_number = add(last_element, second_to_last_element)
# number_list.append(sum_number) # => [7]