Evaluate Reverse Polish Notation — Step-by-Step Visualization

Algorithm Pattern

Stack Evaluation

Key Idea

RPN expressions are evaluated using a stack. When we see a number, we push it onto the stack. When we see an operator, we pop the top two numbers, apply the operator, and push the result back. This naturally handles order of operations without parentheses.

Step-by-Step Approach

1. Initialize an empty stack.
2. Iterate through each token in the expression.
3. If token is a number: `stack.push(int(token))`.
4. If token is an operator: `b = stack.pop()`, `a = stack.pop()`. Calculate result and `stack.push(result)`.
5. After all tokens, the stack will contain exactly one value: the final result.

Common Gotchas

• Truncation toward zero for division: In Python/JS, use `Math.trunc(a / b)` or `int(a / b)`.
• Order of operands: `a` is the first element popped second, `b` is the first element popped first. Operation is `a op b`.