Polish Notation String Calculator

Challenge: Given an always grammatically correct string that represent numbers, parenthesis, and operators add, sub, mult, and div, perform the simplification on the string.

Example

S = ( mult ( sub ( add 1 2 3 ) 4 ) 10 5 )
returns: 100, since (((1+2+3)-4)*10*5) = 100

The Idea: Using recursion with a stack. Use the stack to find matching parenthesis. That is, the moment you identify a closing parenthesis the stack will reveal the index of the closing parenthesis. At this point you know which part of the substring to simplify. To make this clean, map a string to an operator. Since things are always going to be grammatically correct, we can avoid trying to identify them. Similify the target operation which will be in the form of ( [op] [list of numbers] ). Replace the target operation with the simplification. Then recurse on the same string again with the new tokens. Eventually the tokens will all simplify to a single number which will signal the end of recursion calls and you can return the final answer.

import operator as op

map_op = {"add": op.add, "sub": op.sub, "mult": op.mul, "div": op.truediv }


def solve_ops(tokens):
    if len(tokens) is 1:
        return tokens[0]
    else:
        stack = []
        for index, tok in enumerate(tokens):
            if tok is '(':
                stack.append(index)
            elif tok is ')':
                __reduce(stack.pop(), index, tokens)
                return solve_ops(tokens)


def __reduce(start, end, tokens):
    operator = tokens[start + 1]
    nums = [int(tokens[i]) for i in range(start + 2, end)]
    sol = nums[0]
    for i in range(1, len(nums)):
        sol = map_op[operator](sol, nums[i])
    del tokens[start:end+1]
    tokens.insert(start, sol)


# (((1+2+3)-4)*10*5) = 100
print(solve_ops("( mult ( sub ( add 1 2 3 ) 4 ) 10 5 )".split()))

# (((1-2-3)/4)*2*-5 = 10
print(solve_ops("( mult ( div ( sub 1 2 3 ) 4 ) 2 -5 )".split()))

(((-10+-10)5(2+2))/10/5) = -32
print(solve_ops("( div ( mult ( add -10 -10 ) 5 4 ( add 2 2 ) ) 10 5 )".split()))

Simplified Python Solution

import operator


class Solution:
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """

        ops = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}
        s = []

        for token in tokens:
            if token not in ops:
                s.append(token)
            else:
                t1 = s[-1]; s.pop()
                t2 = s[-1]; s.pop()
                s.append(int(ops[token](int(t2), int(t1))))
        return int(s[0])