stack

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Examples

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
-> ((10 * (6 / ((9 + 3) * (-11)))) + 17) + 5 -> 22

Solution

Use stack to store ints, pop and eval two ints when get an operator.

Time O(n), Space O(n).

def evalRPN(tokens):
    stack = []
    for t in tokens:
        if t not in '+-*/':
            stack.append(int(t))
        else:
            r, l = stack.pop(), stack.pop()
            if '+' == t: stack.append(l+r)
            elif '-' == t: stack.append(l-r)
            elif '*' == t: stack.append(l*r)
            else: stack.append(int(float(l)/r))
    return stack.pop()