Intuition

Use a stack to pile all numbers, when an operator is found, pop the last two numbers, do the calculation and then push it to the stack again.

Assuming the expression is valid, at the end thre will be only one element in the stack that is the result.

Approach

Complexity

  • Time complexity: O(n)

  • Space complexity: O(n)

Code

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for t in tokens:
            if self.is_op(t):
                right = stack.pop()
                left = stack.pop()

                if t == "/":
                    stack.append(self.div(left , right))
                elif t == "*":
                    stack.append(left * right)
                elif t == "+":
                    stack.append(left + right)
                elif t == "-":
                    stack.append(left - right)
            else:
                stack.append(int(t))
        
        return stack[0]

    def div(self, left, right):
        r = left / right
        if r < 0 and right * r != left:
            return r + 1
        return r

    def is_op(self, token):
        return token == "/" or token == "*" or token == "+" or token == "-"