Stack · LC #150
Evaluate Reverse Polish Notation
Evaluate a postfix (Reverse Polish Notation) arithmetic expression using a stack: operands are pushed, operators pop two operands and push the result.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are `+`, `-`, `*`, and `/`. Each operand may be an integer or another expression. Division between two integers truncates toward zero. It is guaranteed that the expression is valid and results in a 32-bit integer.
Sample I/O
Input: tokens = ["2","1","+","3","*"] Output: 9 ((2+1)*3 = 9) Input: tokens = ["4","13","5","/","+"] Output: 6 (4 + floor(13/5) = 4 + 2 = 6) Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
RPN eliminates the need for parentheses or operator-precedence rules. Operands build up on the stack until an operator arrives and "consumes" the top two. The order of popping matters: the second pop is the left operand and the first pop is the right operand - critical for non-commutative operators `-` and `/`.
Core Concept
Scan tokens left to right. If a token is a number, push it. If a token is an operator, pop `b` (right operand) then pop `a` (left operand), apply the operator `a OP b`, and push the result. After all tokens are processed, the single remaining stack element is the answer.
When to use
Postfix expression evaluation. Also the foundation for implementing infix-to-postfix conversion (Shunting Yard algorithm), calculator design questions, and AST evaluation.
When NOT to use
Infix or prefix expressions require parsing with precedence - use Shunting Yard or recursive descent instead of a simple operand stack.
Key Insights
What to Know Cold
- Pop order matters: first pop = right operand (b), second pop = left operand (a). Wrong order gives wrong result for `-` and `/`.
- Python's `int(a/b)` truncates toward zero correctly for negative numbers; `a//b` (floor division) does not match the spec.
- JavaScript/TypeScript `Math.trunc()` is the correct way to truncate toward zero; bitwise `| 0` only works for 32-bit safe integers.
- The problem guarantees valid input - no need to handle empty stack or unknown tokens in an interview.
- Single-token input (just one number) is valid and the stack ends with one element to return.
1 example
Worked Examples
Operand order trap with subtraction
Evaluate `["5","3","-"]` - must return 2, not -2.
Pop 3 (right = b), pop 5 (left = a), compute a - b = 5 - 3 = 2. If you compute b - a you get -2, which is wrong.
evalRPN(["5","3","-"]); // 2 (5-3) evalRPN(["3","5","-"]); // -2 (3-5) // Critical: first pop is RIGHT operand
Output: 2
The operand-order mistake is the most common interview bug in this problem. Demonstrating awareness of it signals deep understanding.