Evaluate Reverse Polish Notation: The Evaluation Stack, Distilled
Evaluate Reverse Polish Notation with one stack: push numbers, pop two on each operator, and truncate division toward zero. Code, walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Reverse Polish Notation looks like a typo the first time you see it. ["2","1","+","3","*"] means (2 + 1) * 3, and somehow it needs no parentheses, no precedence rules, and no ambiguity. That's not an accident — postfix notation was designed so a machine could evaluate it in a single left-to-right pass.
The machine in question is a stack: numbers get deferred, operators fire immediately, and when the input runs out, the answer is the one value left standing. Old HP calculators, the JVM, and most bytecode interpreters run on exactly this loop.
The whole solution is one pattern — the evaluation stack — plus two details that fail hidden test cases if you get them wrong: which popped value is the left operand, and how division rounds.
The problem
You're given an array of string tokens representing an arithmetic expression in Reverse Polish (postfix) notation. Each token is either an integer or one of the four operators +, -, *, /. Evaluate the expression and return the result as an integer. Division between integers truncates toward zero, the expression is always valid, and no intermediate value overflows a 32-bit integer.
Input: tokens = ["2","1","+","3","*"]
Output: 9 // (2 + 1) * 3
Input: tokens = ["4","13","5","/","+"]
Output: 6 // 4 + (13 / 5) = 4 + 2Postfix means every operator comes after its two operands. That single rule replaces parentheses entirely: by the time you read an operator, both of its inputs have already appeared.
The brute force baseline
If you treat the token array as text to be simplified, the obvious move is repeated reduction: find the leftmost operator, apply it to the two numbers just before it, splice the three tokens down to one, and repeat until one token remains.
function evalRPN(tokens) {
const ops = new Set(["+", "-", "*", "/"]);
const list = [...tokens];
while (list.length > 1) {
const i = list.findIndex((t) => ops.has(t)); // leftmost operator
const a = Number(list[i - 2]);
const b = Number(list[i - 1]);
let result;
if (list[i] === "+") result = a + b;
if (list[i] === "-") result = a - b;
if (list[i] === "*") result = a * b;
if (list[i] === "/") result = Math.trunc(a / b);
list.splice(i - 2, 3, String(result)); // 3 tokens become 1
}
return Number(list[0]);
}This is correct — the leftmost operator is always ready to fire, because both tokens before it must be numbers. But every reduction rescans the array from the front (findIndex) and shifts everything after the splice point. An expression with n tokens has roughly n/2 operators, each costing O(n) work, so the total is O(n²) — plus a pile of string-to-number round trips. For 10⁴ tokens that's tens of millions of pointless re-reads of tokens you've already understood.
The key insight: defer numbers, fire operators
Look at what the brute force actually computes each round: the two numbers immediately before the leftmost operator. Those are precisely the two most recently seen values that haven't been consumed yet. "Most recently seen, not yet consumed" is the definition of a stack top.
So skip the searching entirely. Walk the tokens once, left to right:
- A number can't do anything yet — its operator hasn't arrived. Push it and move on.
- An operator is ready the instant you reach it — its operands are guaranteed to be the top two stack entries. Pop both, compute, and push the result back, because that result is itself an operand for some later operator.
The push-back is what makes the loop compose. When * arrives in ["2","1","+","3","*"], one of its operands is the literal 3 and the other is the output of +. The stack doesn't care which is which — a computed 3 and a literal 3 look identical sitting in a slot. That indifference is why one flat loop evaluates arbitrarily nested expressions with zero lookahead.
One ordering rule matters: the value you pop first was pushed last, so it's the right operand. For a - b and a / b, first pop = b, second pop = a.
The optimal solution
This is the same algorithm the visualizer traces step by step:
function evalRPN(tokens) {
const stack = [];
for (const token of tokens) {
if (!["+", "-", "*", "/"].includes(token)) {
stack.push(Number(token)); // operand: defer it
} else {
const b = stack.pop(); // right operand (pushed last)
const a = stack.pop(); // left operand
if (token === "+") stack.push(a + b);
if (token === "-") stack.push(a - b);
if (token === "*") stack.push(a * b);
if (token === "/") stack.push(Math.trunc(a / b));
}
}
return stack.pop(); // exactly one value remains
}Two deliberate choices:
- Operator detection compares whole tokens.
["+","-","*","/"].includes(token)can never confuse"-3"with subtraction — a trap you walk straight into if you testtoken[0]instead. Math.trunc, notMath.floor. The problem demands truncation toward zero. For positive results they agree, butMath.floor(-13 / 5)is-3while the required answer is-2.Math.truncdrops the fractional part regardless of sign.
Valid RPN guarantees the stack never underflows and ends with exactly one entry, so no defensive checks are needed.
Walkthrough: tokens = ["2","1","+","3","*"]
| Step | Token | Kind | Action | Stack after |
|---|---|---|---|---|
| 1 | "2" | number | push 2 | [2] |
| 2 | "1" | number | push 1 | [2, 1] |
| 3 | "+" | operator | pop b=1, a=2 → push 2+1 | [3] |
| 4 | "3" | number | push 3 | [3, 3] |
| 5 | "*" | operator | pop b=3, a=3 → push 3×3 | [9] |
The loop ends, stack.pop() returns 9. Notice step 4: after + fires, its result sits under the fresh literal 3, and step 5 multiplies them without knowing or caring that one was computed two steps earlier. For the division example ["4","13","5","/","+"], the / step pops b=5, a=13 and pushes Math.trunc(13 / 5) = 2; the final + then produces 6.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Reduce-in-place (find + splice) | O(n²) | O(n) | every operator triggers a rescan and an array shift |
| Recursive descent from the right | O(n) | O(n) | one visit per token, but recursion depth can hit n |
| Evaluation stack | O(n) | O(n) | each token is one push or one pop-pop-push, all O(1) |
Both linear approaches touch each token exactly once; the stack version wins on clarity and avoids deep recursion. Worst-case space is a token list like ["1","1","1",...,"+","+",...] where all the numbers arrive before any operator — about n/2 values sit on the stack at the peak.
Common mistakes
- Swapped operand order.
stack.push(b - a)instead ofa - b. Addition and multiplication are commutative, so tests built only from+and*pass — then["3","4","-"]returns 1 instead of -1. Always name the pops: first pop isb(right), second isa(left). - Flooring instead of truncating.
Math.floor(a / b)and Python'sa // bround toward negative infinity.6 / -132must be0, not-1. UseMath.trunc(a / b)in JavaScript andint(a / b)in Python. - Detecting operators by first character. Checking
"+-*/".includes(token[0])classifies"-3"as subtraction and corrupts the stack several steps before anything visibly fails. Compare the entire token. - Reaching for
eval(). Building an infix string and evaluating it is banned in interviews, and JavaScript's/produces floats anyway — you'd still owe the truncation logic. - Adding underflow guards mid-interview. The constraints promise valid RPN, so two operands always exist when an operator arrives. Say that out loud instead of cluttering the loop; mention that malformed input would surface as a pop on an empty stack.
Where this pattern shows up next
The evaluation stack is the "process it now vs. defer it" decision in its purest form, and the rest of the stack family riffs on the same question:
- Remove Outermost Parentheses — the gentlest entry point: a depth counter standing in for a stack of open parens.
- Next Greater Element I — the monotonic stack, where popping means "your answer just arrived."
- Daily Temperatures — the same monotonic pop, but deferring indices to measure waiting time.
- Next Greater Element II — a circular array forces two passes over the same stack discipline.
To watch the stack breathe — operands piling up, + collapsing two into one, * finishing the job — step through it interactively.
FAQ
Why does a stack correctly evaluate Reverse Polish Notation?
Because postfix notation guarantees that when an operator appears, its two operands are the two most recently produced values that haven't been consumed yet — either literals just read or results just computed. "Most recent, unconsumed" is exactly what a stack's top two slots hold, so pop-pop-compute-push is always the right move. No parentheses or precedence are needed because the token order itself encodes the evaluation order.
Why is the first value popped the right operand?
Stacks reverse order: the left operand a was pushed before the right operand b, so b sits on top and comes off first. For ["3","4","-"], popping gives 4 then 3, and the answer is 3 - 4 = -1. Writing const b = stack.pop(); const a = stack.pop(); and then computing a op b keeps the roles straight. Only subtraction and division expose the bug, which is why it survives weak test cases.
How do you truncate division toward zero in JavaScript?
Use Math.trunc(a / b), which drops the fractional part regardless of sign: Math.trunc(-13 / 5) is -2. Math.floor rounds toward negative infinity and gives -3 for the same input, which fails the problem's spec. In Python the equivalent is int(a / b) — the floor-division operator a // b has the same negative-number problem as Math.floor.
What is the time and space complexity of evalRPN?
O(n) time and O(n) space for n tokens. Each token is processed exactly once with constant work: numbers cost one push, operators cost two pops and one push. The stack is the only extra memory, and it peaks at about n/2 entries when every number in the expression appears before the first operator.
Where is Reverse Polish Notation used outside of interviews?
Stack-based virtual machines — the JVM, the CPython bytecode interpreter, WebAssembly — all execute an operand-stack loop that is this problem at industrial scale. Compilers emit postfix-style instruction sequences precisely because a stack machine can execute them in one pass with no parsing. HP's RPN calculators shipped the same idea in hardware in the 1970s.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.