LeetCode 150 · Stack

Evaluate Reverse Polish Notation, explained with a picture

A calculator built from plates.

MediumStack
▶ Watch it step by step

The problem

Evaluate an arithmetic expression written in Reverse Polish Notation, where each operator comes after its two numbers (e.g. “2 1 +” means 2 + 1). Division truncates toward zero.

Input:  ["2", "1", "+", "3", "*"]
Output: 9   ((2 + 1) × 3)

Picture it

Picture a calculator made of a stack of plates. Each number is written on a plate and put on top. When an operator arrives, take off the top two plates, combine them, and put the result back as one plate. When the tokens run out, the last plate is the answer.

How to recognise it

  • The input is a list of tokens where each operator comes after its operands, so no brackets or precedence rules are needed.
  • Every operator works on the two most recent results that have not been used yet. "Most recent first" is what a stack gives you.
  • Each intermediate result becomes an operand for a later operator, so results must go back where the next operator can find them.
  • Up to 10^4 tokens, so one left-to-right pass is expected.

Start with brute force

Find the first operator in the list. Because the expression is valid, the two tokens just before it are numbers. Replace those three tokens with the result and repeat until one token is left.

def eval_rpn_brute(tokens):
    tokens = list(tokens)
    while len(tokens) > 1:
        i = next(k for k, t in enumerate(tokens) if t in OPS)   # first operator
        a, b = int(tokens[i - 2]), int(tokens[i - 1])
        tokens[i - 2:i + 1] = [str(OPS[tokens[i]](a, b))]
    return int(tokens[0])

Each round removes one operator, but finding it and rebuilding the list costs O(n). With about n/2 operators that is O(n²) time: roughly 5 × 10^3 rounds over a list of up to 10^4 tokens, so around 5 × 10^7 steps. Space is O(n) for the copy.

From brute force to the idea

  1. Find the waste. Each round rescans from the start to find the next operator, even though everything before the previous result has not changed.
  2. Keep the unused results in order. As you read left to right, every number (or computed result) waits until an operator needs it. The operator always needs the two newest ones: that is the top of a stack.
  3. Numbers are pushed. stack.append(int(t)). A token like "-3" is not in OPS, so it is parsed as a negative number; only the single character "-" is the operator.
  4. Operators pop twice, in the right order. The first pop is the right operand b, the second is the left operand a. Order matters for - and /.
  5. Divide toward zero. int(a / b) truncates toward zero, as the problem asks. Python's a // b rounds down instead, so -7 // 2 is −4 but the answer needs −3.
  6. The result is the last item. A valid expression leaves exactly one value, so stack[0] is the answer.

This is the key idea: an operator always uses the two latest unused values, which are the top two items on a stack.

The key idea

Numbers push; operators pop two, compute, push the result. One pass with a stack, O(n).

Python solution

OPS = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)}
def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in OPS:
            b = stack.pop()
            a = stack.pop()
            stack.append(OPS[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from operator import add, sub, mul

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): about n/2 rounds, each scanning and rebuilding the listO(n): the token copy
Stack (shown code)O(n): each token is pushed once and popped at most onceO(n): up to about n/2 numbers wait on the stack

Edge cases

  • Imports: the shown code uses add, sub and mul without importing them; it needs from operator import add, sub, mul, or defining OPS raises NameError.
  • A single number (["5"]): nothing is popped, returns 5.
  • Negative division (["-7", "2", "/"]): returns −3, truncated toward zero.
  • Negative numbers as tokens (["3", "-4", "-"]): returns 7, because "-4" is read as a number.
  • Huge numbers: int(a / b) goes through a float, which is exact only up to about 2^53. ["10000000000000000001", "1", "/"] gives 10^19, not 10^19 + 1. LeetCode keeps every value within 32 bits, where this is safe.
  • Division by zero raises ZeroDivisionError; the problem promises it never happens.

Common mistakes

  • Popping a first and b second, which turns 13 4 - into 4 − 13 instead of 13 − 4.
  • Using // for division, which rounds toward minus infinity and is wrong whenever the result is negative and not whole.
  • Testing t.isdigit() to spot numbers, which treats "-3" as an operator.
  • Pushing the token strings without int(). Then add("2", "1") joins them into "21" instead of adding.
Your turn: Polish (prefix) notation

Now every operator comes before its two operands: ["*", "+", "2", "1", "3"] means (2 + 1) × 3 = 9. Evaluate it with the same stack idea. Describe your approach, then write it if you like.

Compare with our answer

Read the tokens from right to left. Then operands are seen before the operator that uses them, just as in RPN. The difference is the pop order: the first pop is now the left operand.

def eval_pn(tokens):
    stack = []
    for t in reversed(tokens):
        if t in OPS:
            a = stack.pop()          # left operand comes off first
            b = stack.pop()
            stack.append(OPS[t](a, b))
        else:
            stack.append(int(t))
    return stack[0]

eval_pn(["-", "10", "3"]) is 7. Time O(n), space O(n).

A strong answer mentions: scanning in reverse, why the pop order flips compared with RPN, and a test with - or / where swapping the operands would change the answer.

Check what stuck

1. A spreadsheet stores formulas in postfix form and adds a max token that takes two values. Which approach fits best?

2. Why does the shown code pop b before a?

3. A learner replaces the division lambda with lambda a, b: a // b. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.