Skip to content
16-Week DSA Roadmap
LeetCode #150MediumProblem 3 of 8

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

The problem in plain English

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.

What is Reverse Polish Notation?

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’s 2 + 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.

tokens
  1. 20
  2. 11
  3. +2
  4. 33
  5. *4
tokens = ["2", "1", "+", "3", "*"] means (2 + 1) × 3 = 9.

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.

Before you code: think it through

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

Work out tokens = ["5", "3", "-"] by hand. Is it 5 − 3 or 3 − 5? Then try ["8", "2", "/", "3", "+"].

Approach 1: Brute force

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", "*"]

tokens
  1. 20
  2. 11
  3. +2
  4. 33
  5. *4
variables
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.

Step 1 / 5

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”.

Why is it slow?

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 pattern: stack-based expression evaluation

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

Template

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”

Approach 2: One pass with a stack

  1. Make an empty stack.
  2. Read the tokens left to right.
  3. Number? Convert the text to a number and push it.
  4. Operator? Pop once to get b (the second number), pop again to get a (the first number). Push calc(a, b, op).
  5. 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", "*"]

tokens
  1. 20
  2. 11
  3. +2
  4. 33
  5. *4
stacknumbers waiting
  1. empty
variables
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.

Step 1 / 11

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];}

The code, line by line

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 / 5 is 2.6. Math.trunc cuts off the decimals, toward zero: Math.trunc(2.6) is 2, Math.trunc(-1.5) is -1. Don’t use Math.floor: it rounds down, so Math.floor(-1.5) is -2. Wrong.
    • In Python, a / b also gives a decimal, and int(...) cuts off the decimals toward zero: int(-1.5) is -1. Don’t use a // b: Python’s // rounds down, so 6 // -4 is -2. Wrong.
  • Line 8 (JS) / line 11 (Py): the main function. LeetCode names it evalRPN (inside var evalRPN = function(tokens) in JS, or class Solution in 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.

Dry run

Trace LeetCode’s second example, ["4", "13", "5", "/", "+"], which is 4 + 13 / 5 in normal notation. The stack is written bottom → top.

tokennumber or operator?pops (a, b)computesstack after
"4"number[4]
"13"number[4, 13]
"5"number[4, 13, 5]
"/"operatora = 13, b = 513 / 5 = 2.6 → 2[4, 2]
"+"operatora = 4, b = 24 + 2 = 6[6]
endreturn 6[6]
tokens = ["4", "13", "5", "/", "+"]

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.

Complexity

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.

Common mistakes and edge cases

What to say out loud, in this order:

  1. Explain RPN in one sentence: “the operator comes after its two operands, so no brackets are needed.”
  2. “Each operator uses the two most recent unused numbers, which is a stack.”
  3. Point out the operand order (b pops first) and the truncation rule before you code.
  4. Cost: O(n) time, O(n) space.
  5. 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 to calc; 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.