Evaluate Reverse Polish Notation
Work out the value of a maths expression written with the operator after its two numbers, like "2 1 + 3 *".
- Stack-based expression evaluation
Before this, know: What a stack is (push, pop, peek), Integer division
You get a list of tokens (small pieces of text). Each token is either a
whole number like "4" or "-11", or one of the four operators "+", "-",
"*", "/". Together they form a maths expression written in Reverse Polish
Notation (RPN). Return its value.
The way we normally write maths is called infix: the operator goes between
its two numbers, as in 2 + 1. In RPN (also called postfix) the operator
goes after its two numbers: 2 1 +.
That sounds odd, but it has a superpower: no brackets are ever needed. In
infix, (2 + 1) × 3 and 2 + 1 × 3 are different, so we need brackets and
“multiply before add” rules. In RPN:
2 1 + 3 *means: take 2 and 1, add them (3), then take that and 3, multiply (9). That’s(2 + 1) × 3.2 1 3 * +means: take 1 and 3, multiply (3), then add 2 (5). That’s2 + 1 × 3.
The order of the tokens alone says what to do first. Old HP calculators and some programming languages (Forth, PostScript) work this way, and compilers turn normal maths into RPN internally.
- 20
- 11
- +2
- 33
- *4
Rules from the problem statement:
- The expression is always valid: every operator will have two numbers available.
- Division between two integers truncates toward zero: drop everything after
the decimal point.
7 / 2 = 3.5 → 3, and-7 / 2 = -3.5 → -3(not −4). - No division by zero. All results fit in a 32-bit integer.
So when we read an operator, the two numbers it needs are the two most recent numbers we haven’t used yet. “Most recent” again means a stack.
Pause and think
5 3 - is 5 − 3 = 2. The first number written is the left side. When we pop
from a stack we get them in reverse: 3 comes off first, so it’s the second
number. That reversal is the number-one bug on this problem.
8 2 / 3 + is 8 ÷ 2 = 4, then 4 + 3 = 7.
Without a stack, we can do what you might do on paper: find the first operator in the list. The two tokens right before it are its numbers. Work out that small sum, replace the three tokens with the single result, and start again from the beginning. Repeat until one token is left.
2 1 + 3 * → the first operator is +, so replace 2 1 + with 3 →
3 3 * → replace with 9 → 9.
Brute force: collapse the first operator, start over
tokens = ["2", "1", "+", "3", "*"]
- 20
- 11
- +2
- 33
- *4
- tokens left
- 5
- tokens walked over (total)
- 3
- answer
- —
- The two numbers
- First operator
- Result written back
- Answer
Walk from the start to the first operator: "+" at index 2. The two tokens just before it, 2 and 1, are its numbers.
Which line is running?
function calc(a, b, op) { if (op === "+") return a + b; if (op === "-") return a - b; if (op === "*") return a * b; return Math.trunc(a / b); // divide, then drop the decimals (toward zero)}function evalRPN(tokens) { tokens = [...tokens]; // work on a copy while (tokens.length > 1) { let i = 0;Running now: while (!["+", "-", "*", "/"].includes(tokens[i])) i++; // first operator const value = calc(Number(tokens[i - 2]), Number(tokens[i - 1]), tokens[i]); tokens.splice(i - 2, 3, String(value)); // replace "a b op" with its value } return Number(tokens[0]);}Brute force: collapse and restart
function calc(a, b, op) { if (op === "+") return a + b; if (op === "-") return a - b; if (op === "*") return a * b; return Math.trunc(a / b); // divide, then drop the decimals (toward zero)}function evalRPN(tokens) { tokens = [...tokens]; // work on a copy while (tokens.length > 1) { let i = 0; while (!["+", "-", "*", "/"].includes(tokens[i])) i++; // first operator const value = calc(Number(tokens[i - 2]), Number(tokens[i - 1]), tokens[i]); tokens.splice(i - 2, 3, String(value)); // replace "a b op" with its value } return Number(tokens[0]);}def calc(a, b, op): if op == "+": return a + b if op == "-": return a - b if op == "*": return a * b return int(a / b) # divide, then drop the decimals (toward zero)def eval_rpn(tokens): tokens = list(tokens) # work on a copy while len(tokens) > 1: i = 0 while tokens[i] not in ("+", "-", "*", "/"): # first operator i += 1 value = calc(int(tokens[i - 2]), int(tokens[i - 1]), tokens[i]) tokens[i - 2 : i + 1] = [str(value)] # replace "a b op" with its value return int(tokens[0])The small calc helper does the maths for one operator. splice(i - 2, 3, value)
(JavaScript) and tokens[i - 2 : i + 1] = [value] (Python) both mean “remove the
3 tokens starting at i − 2, and put value in their place”.
Every round walks from the very start of the list to find an operator, and then
removing items from the middle of a list shifts everything after them. With 5
tokens that’s a handful of steps. But a list like 1 1 1 1 … 1 + + + … + with
5,000 ones and 4,999 pluses is bad: the first round walks past 5,000 tokens to
reach the first +, the next round past 4,999, and so on. That’s
5,000 + 4,999 + … + 1 ≈ 12,500,000 steps. The work grows like n × n:
O(n²).
The brute force keeps re-reading numbers it has already seen. Instead, read the tokens once and park each number on a stack. When an operator arrives, the two numbers it needs are on top.
Pattern
Stack-based expression evaluation
Use it when: you evaluate an expression or process tokens where each operation uses the most recent values (postfix, calculators, undo history, simplifying paths).
Signal words
- “reverse Polish notation”
- “postfix”
- “evaluate the expression”
- “tokens”
- “operators and operands”
- Make an empty stack.
- Read the tokens left to right.
- Number? Convert the text to a number and push it.
- Operator? Pop once to get
b(the second number), pop again to geta(the first number). Pushcalc(a, b, op). - At the end, the stack holds exactly one number. Return it.
Press Play. Watch numbers pile up on the stack, and every operator eat the top two and leave one in their place. Then try the “Order matters” example (7 − 2, not 2 − 7) and the negative division edge case, where −1.5 becomes −1.
One pass with a stack
tokens = ["2", "1", "+", "3", "*"]
- 20
- 11
- +2
- 33
- *4
- empty
- a (first)
- —
- op
- —
- b (second)
- —
- result
- —
- Reading now
- Just pushed
- Final answer
- Already read
We read the tokens left to right with an empty stack. Numbers wait on the stack until an operator comes along to use them.
Which line is running?
function calc(a, b, op) { if (op === "+") return a + b; if (op === "-") return a - b; if (op === "*") return a * b; return Math.trunc(a / b); // divide, then drop the decimals (toward zero)}function evalRPN(tokens) {Running now: const stack = []; for (const token of tokens) { if (["+", "-", "*", "/"].includes(token)) { const b = stack.pop(); // the top is the SECOND number const a = stack.pop(); // the one under it is the FIRST stack.push(calc(a, b, token)); } else { stack.push(Number(token)); // a number: park it on the stack } } return stack[0];}One pass with a stack
function calc(a, b, op) { if (op === "+") return a + b; if (op === "-") return a - b; if (op === "*") return a * b; return Math.trunc(a / b); // divide, then drop the decimals (toward zero)}function evalRPN(tokens) { const stack = []; for (const token of tokens) { if (["+", "-", "*", "/"].includes(token)) { const b = stack.pop(); // the top is the SECOND number const a = stack.pop(); // the one under it is the FIRST stack.push(calc(a, b, token)); } else { stack.push(Number(token)); // a number: park it on the stack } } return stack[0];}def calc(a, b, op): if op == "+": return a + b if op == "-": return a - b if op == "*": return a * b return int(a / b) # divide, then drop the decimals (toward zero)def eval_rpn(tokens): stack = [] for token in tokens: if token in ("+", "-", "*", "/"): b = stack.pop() # the top is the SECOND number a = stack.pop() # the one under it is the FIRST stack.append(calc(a, b, token)) else: stack.append(int(token)) # a number: park it on the stack return stack[0]Python spreads each if in calc over two lines, so its line numbers run
ahead of JavaScript’s. We give both.
calc(JS lines 1–6, Py lines 1–8): one small function that does the maths for one operator. Keeping it separate makes the main loop short and readable.- Division (JS line 5, Py line 8): this is the subtle line.
- In JavaScript,
/gives a decimal:13 / 5is2.6.Math.trunccuts off the decimals, toward zero:Math.trunc(2.6)is2,Math.trunc(-1.5)is-1. Don’t useMath.floor: it rounds down, soMath.floor(-1.5)is-2. Wrong. - In Python,
a / balso gives a decimal, andint(...)cuts off the decimals toward zero:int(-1.5)is-1. Don’t usea // b: Python’s//rounds down, so6 // -4is-2. Wrong.
- In JavaScript,
- Line 8 (JS) / line 11 (Py): the main function. LeetCode names it
evalRPN(insidevar evalRPN = function(tokens)in JS, orclass Solutionin Python). - Line 9 (JS) / line 12 (Py): an empty array/list used as a stack.
- Line 11 (JS) / line 14 (Py): is this token one of the four operators? We compare the
whole token, so
"-11"(a negative number) is not mistaken for"-". - Line 12 (JS) / line 15 (Py): the first pop is the number pushed last, so it’s
the right-hand side,
b. - Line 13 (JS) / line 16 (Py): the second pop is the left-hand side,
a. - Line 14 (JS) / line 17 (Py): push the result. It’s a number now, ready for the next operator.
- Line 16 (JS) / line 19 (Py): a number token is text, so convert it:
Number("13")/int("13"). Both handle a leading minus sign. - Line 19 (JS) / line 20 (Py): one number is left. That’s the answer.
Trace LeetCode’s second example, ["4", "13", "5", "/", "+"], which is
4 + 13 / 5 in normal notation. The stack is written bottom → top.
| token | number or operator? | pops (a, b) | computes | stack after |
|---|---|---|---|---|
| "4" | number | [4] | ||
| "13" | number | [4, 13] | ||
| "5" | number | [4, 13, 5] | ||
| "/" | operator | a = 13, b = 5 | 13 / 5 = 2.6 → 2 | [4, 2] |
| "+" | operator | a = 4, b = 2 | 4 + 2 = 6 | [6] |
| end | return 6 | [6] |
The "/" row is the interesting one: b is 5 (popped first) and a is 13, so we
compute 13 / 5, not 5 / 13. And 2.6 is truncated to 2.
Brute force (collapse and restart)
Time
O(n²)
Up to n/2 rounds, each walking and shifting up to n tokens.
Space
O(n)
A copy of the token list.
One pass with a stack
Time
O(n)
Each token is read once, and each push or pop takes one step. 10,000 tokens ≈ 10,000 steps.
Space
O(n)
In the worst case (all the numbers first, all the operators last) about half the tokens wait on the stack.
What to say out loud, in this order:
- Explain RPN in one sentence: “the operator comes after its two operands, so no brackets are needed.”
- “Each operator uses the two most recent unused numbers, which is a stack.”
- Point out the operand order (
bpops first) and the truncation rule before you code. - Cost: O(n) time, O(n) space.
- Dry-run an example with
-or/so the order is visibly right.
Likely follow-up questions:
- “What if the input could be invalid?” Check the stack has at least two numbers before popping, and exactly one at the end.
- “Evaluate normal infix like
3 + 4 * 2?” That’s Basic Calculator (harder): you need a stack for operators too, or the shunting-yard algorithm to convert to RPN first. - “More operators, like
^?” Add a line tocalc; the stack logic doesn’t change.
Related problems:
- Valid Parentheses (this week): the same “most recent unfinished thing” stack.
- Min Stack (this week): a stack with an extra job.
- The week 3 overview has the template.