Evaluate Reverse Polish Notation
A medium Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Evaluate an arithmetic expression given as a list of tokens in Reverse Polish Notation. The valid operators are plus, minus, multiply, and divide. Each operand may be an integer or another expression.
Example 1
- Input
- tokens = ["4","2","-","5","*"]
- Output
- 10
- Why
- 4 minus 2 is 2, and 2 times 5 is 10.
Example 2
- Input
- tokens = ["6","12","4","/","+"]
- Output
- 9
- Why
- 12 divided by 4 is 3, and 6 plus 3 is 9.
Constraints
- 1 <= tokens.length <= 10^4
- Each token is either an operator (+, -, *, /) or an integer in the range [-200, 200]
- The expression is guaranteed to be valid and evaluates to an integer
How to think about it
Updated 2026-09-29Postfix notation removes the ambiguity of precedence by placing every operator strictly after its two operands. Reading left to right, every operator consumes the most recent two numbers that have not yet been consumed. That last-in, first-out relationship means a stack naturally holds dormant operands until their operator arrives.
Approaches, worst first
In-place array compaction
time O(n^2) · space O(1)
Find the first operator, apply it to the preceding two indices, replace the triplet with the calculated result, and shift the remaining elements left. Loses because shifting the array on every operator produces quadratic work.
Operand stackWrite this one
time O(n) · space O(n)
Iterate through the tokens. Push numeric tokens directly onto a stack. When encountering an operator, pop the right operand first, then the left operand, evaluate the operation, and push the result back. At the end, the stack contains exactly one final value.
Where people lose marks · 3
- Operand order matters for subtraction and division. The first element popped from the stack is the right operand, and the second is the left operand; reversing them flips the sign or quotient.
- Language-level integer division differences: in JavaScript or Python, default floor division rounds negative numbers away from zero (-3 // 2 = -2), whereas the problem requires truncation toward zero (`Math.trunc`).
- Tokens with negative integers like `-4` start with a minus sign. Checking `token.startsWith('-')` can misidentify negative numbers as subtraction operators unless string length is verified.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .