Evaluate Reverse Polish Notation

Intuition

Postfix notation is built for a stack. As you scan left to right, every number you meet is an operand waiting to be used, so you simply push it. When you meet an operator, its two operands are exactly the two most recently pushed values, which sit on top of the stack. You pop them, apply the operator, and push the single result back so it can serve as an operand for a later operator. Order matters for subtraction and division: the value popped first is the right operand and the value popped second is the left operand. When the tokens run out, the stack holds one value, which is the answer.

Algorithm walkthrough

1. 1Create an empty stack that will hold integer operands.
2. 2Iterate through the tokens one by one.
3. 3If a token is an operator, pop the top value as b (right operand) and the next value as a (left operand).
4. 4Compute a op b, using truncation-toward-zero for division, and push the result back onto the stack.
5. 5If a token is a number, parse it to an integer and push it.
6. 6After processing all tokens, the single remaining value on the stack is the final result.

Implementation

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {"+", "-", "*", "/"}
        for token in tokens:
            if token in operators:
                b = stack.pop()
                a = stack.pop()
                if token == "+":
                    stack.append(a + b)
                elif token == "-":
                    stack.append(a - b)
                elif token == "*":
                    stack.append(a * b)
                else:
                    # int() truncates toward zero
                    stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[-1]