LeetCode #150: Evaluate Reverse Polish Notation

Description:

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

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

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Solution:

• Use stack to restore the results

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        """
        :type tokens: List[str]
        :rtype: int
        """
        n = len(tokens)
        if n < 3:
            return int(tokens[0])
        else:
            operator = ['+', '-', '*', '/']

            stack  = [ [int(tokens[0])],  [int(tokens[1])] ]
            k = 1
            for i in range(2,n):
                if tokens[i] in operator:
                    if tokens[i] == '+': stack[(k+1)%2][-1] += stack[k].pop()
                    if tokens[i] == '-': stack[(k+1)%2][-1] -= stack[k].pop()
                    if tokens[i] == '*': stack[(k+1)%2][-1] *= stack[k].pop()
                    if tokens[i] == '/': stack[(k+1)%2][-1] = int(stack[(k+1)%2][-1] / stack[k].pop())
                else:
                    stack[(k+1)%2].append(int(tokens[i]))

                k = (k+1) % 2
                #print(i, tokens[i], stack)
        if len(stack[0]) > 0:
            res = stack[0][-1]
        else:
            res = stack[1][-1]
        return res