4.8.3 — Evaluate Reverse Polish Notation

LeetCode 150 · Medium

The problem

Evaluate an expression written in Reverse Polish Notation, where each operator comes after its two operands.

["2","1","+","3","*"]        →  9      ((2 + 1) × 3)
["4","13","5","/","+"]       →  6      (4 + (13 / 5) = 4 + 2)

Division truncates toward zero, so -13 / 5 is -2, not -3.

The Plain-English Breakdown

Normally, we write math like 2 + 3 (Infix notation). In Reverse Polish Notation (RPN), the operator comes after the numbers: 2 3 +. This might look weird, but it's incredibly powerful because it completely eliminates the need for parentheses or worrying about the order of operations (like PEDMAS/BODMAS).

Constraints to note:

The input array length is up to $10^4$ .
The numbers are valid integers in the range $[-200, 200]$ .
The expression is guaranteed to be valid (you won't be given ["+"] with no numbers, or divide by zero).

Brute Force Analysis

What happens if we don't use a stack? A naive approach would be to scan the array left-to-right until we find the first operator. Then, we look at the two numbers immediately preceding it, compute the result, replace those three items (two numbers and one operator) with the new result, and start scanning again.

Time Cost: Each reduction step shifts the rest of the array left by 2 positions. Doing this $N/2$ times leads to $O(N^2)$ time.
Why it fails: At 10,000 tokens, shifting arrays inside a loop takes roughly $10^8$ operations, which is way too slow. The waste here is constantly rescanning the array and shifting elements. We need a way to process numbers as they come and instantly access the two most recent ones.

The pattern

RPN needs no brackets and no precedence rules, because the order is already fixed by the arrangement. That is exactly why it exists.

Walk the tokens left to right. A number gets pushed. An operator pops the two most recent numbers, combines them, and pushes the result back. At the end the stack holds one value: the answer.

The order of the two pops matters. The first value popped is the second operand, because it was pushed last. For ["13","5","/"] you pop 5, then 13, and compute 13 / 5. Getting this backwards gives the right answer for + and * and the wrong one for - and /, which is exactly the kind of bug that passes half the tests.

ELI5 Analogy: Imagine you are at a checkout counter, placing items onto the counter one by one. The cashier (the operator) comes along. They always grab the item closest to them first (the most recently placed one), and then the item behind it. If they are subtracting, they subtract the closest item from the one behind it. You have to wait for them to process those two before they put the combined total back on the counter.

The solution

PythonTypeScript

python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        ops = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: int(a / b),     # truncate toward zero
        }
        stack = []

        for t in tokens:
            if t in ops:
                b = stack.pop()               # second operand
                a = stack.pop()               # first operand
                stack.append(ops[t](a, b))
            else:
                stack.append(int(t))

        return stack[0]

function evalRPN(tokens: string[]): number {
  const ops: Record<string, (a: number, b: number) => number> = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };
  const stack: number[] = [];

  for (const t of tokens) {
    if (t in ops) {
      const b = stack.pop()!;
      const a = stack.pop()!;
      stack.push(ops[t](a, b));
    } else {
      stack.push(Number(t));
    }
  }

  return stack[0];
}

if t in ops is the right membership test, and it is safer than checking whether the token looks like a number. A token can be "-4", which starts with a minus sign but is an operand. Testing against the operator set removes the ambiguity.

The map from symbol to function is a dispatch table. It replaces a chain of if/elif branches, and adding a new operator becomes one line rather than a new branch. That is the same idea as the Strategy pattern in Chapter 9.4.12, in its smallest form.

Code Walkthrough

The Dispatch Table: ops is a dictionary where the keys are strings ("+", "-", etc.) and the values are anonymous lambda functions that know how to combine two numbers. This acts as our calculation engine.
The Stack: We initialize an empty list stack. This will hold numbers waiting to be operated on.
The Iteration: We loop through each string t in our tokens.
Is it an operator? We check if t in ops. If it is, we are ready to compute. We pop the top of the stack and call it b (the right-hand side), and pop again and call it a (the left-hand side). We pass a and b into our lambda function, and push the result back onto the stack.
Is it a number? If t is not in ops, it must be a number. We convert it to an integer using int(t) and push it onto the stack.
The Result: Because the problem guarantees a valid expression, when the loop finishes, exactly one number will remain on the stack. We return stack[0].

Hand Trace

Let's trace ["4", "13", "5", "/", "+"]:

Token	Type	Action	Stack State
`"4"`	Number	Push 4	`[4]`
`"13"`	Number	Push 13	`[4, 13]`
`"5"`	Number	Push 5	`[4, 13, 5]`
`"/"`	Operator	Pop 5 (`b`), Pop 13 (`a`), `13/5`	`[4, 2]`
`"+"`	Operator	Pop 2 (`b`), Pop 4 (`a`), `4+2`	`[6]`

Final answer is 6, which sits alone in the stack.

Edge Cases Handled

Negative numbers as tokens: "-11" is properly handled because it won't match our ops keys, and int("-11") correctly parses it.
Single number input: If the input is just ["18"], the loop pushes 18, bypasses operators, and returns 18 immediately.
Deep nesting: Something like ["1", "2", "3", "4", "5", "+", "+", "+", "+"] will build up a massive stack of 5 numbers before collapsing them all one by one. The stack handles this seamlessly.

The division trap

This is the detail the problem is built around, and your Report 2 flagged it.

Python's // is floor division, not truncation. It rounds towards negative infinity, so -13 // 5 is -3. RPN requires truncation towards zero, which is -2.

The fix is int(a / b). Float division gives -2.6, and int() in Python truncates towards zero, giving -2.

For positive numbers the two agree, which is why this bug survives until a test uses negatives.

JavaScript has the same issue in a different place. / gives a float, and Math.floor(-2.6) is -3. Use Math.trunc, which rounds towards zero by definition.

expression	Python `//`	`int(a/b)`	correct for RPN
`13 / 5`	2	2	2
`-13 / 5`	−3	−2	−2

Complexity

$O(n)$ time — one pass, and each token does constant work. $O(n)$ space for the stack.

Derivation:

Time Complexity: $O(N)$ where $N$ is the number of tokens. We iterate through the tokens array exactly once. For each token, we do $O(1)$ work: either converting a string to an integer and pushing it, or popping twice, doing a basic arithmetic operation, and pushing once. Since $N \times O(1) = O(N)$ , time is linear.
Space Complexity: $O(N)$ memory is used for the stack. In the worst-case scenario where we have all numbers first followed by all operators (e.g., ["1", "2", "3", "+", "+"]), the stack will grow to store $(N + 1) / 2$ elements before any operators reduce them. This scales linearly with $N$ , hence $O(N)$ space.

Where this goes next

RPN is not a curiosity. It is the form expressions take after parsing, which is why this matters:

The shunting-yard algorithm converts ordinary infix notation like 2 + 3 * 4 into RPN, using a second stack for operators and their precedence. Then this code evaluates it. Together they are a complete expression evaluator.
Stack-based virtual machines — the JVM and WebAssembly both execute bytecode that is essentially RPN. iadd pops two values and pushes their sum. Chapter 3.3.
Basic Calculator (LeetCode 224 and 227) — evaluate an infix string with brackets and precedence directly. Harder, and it is shunting-yard folded into one pass.

The rule: when an operator consumes the most recent results, use a stack. That covers expression evaluation, postfix machines, and undo systems.

What the interviewer will push on

"Which operand is which?" The first pop is the right-hand operand. Say it before you write the line.

"Why not use // in Python?" Floor versus truncation on negative numbers. Give -13 / 5.

"How would you handle infix input instead?" Shunting-yard: one stack for output, one for operators, popping operators of higher or equal precedence before pushing.

"What if a token is malformed, or the expression is invalid?" The stack is either empty when an operator arrives, or has more than one value at the end. Real parsers check both and report the position. On a judge you skip it; naming the difference is the good answer.

"Why a dispatch map rather than if-else?" Adding an operator is one entry, not a new branch, and the lookup is $O(1)$ .

"What if we want to add an exponentiation operator (^)?" With the dispatch map, you simply add "^": lambda a, b: a ** b to the dictionary. If you had used if/else, you would have to modify the core logic of the loop, breaking the Open-Closed Principle (code should be open for extension but closed for modification).

One thing to volunteer: mention that this is what a stack-based virtual machine does with bytecode. It reframes the problem from a puzzle into something real.

Next: 4.8.4 Generate Parentheses — not a stack problem at all, despite its filing, and the first backtracking problem in the book.

4.8.3 — Evaluate Reverse Polish Notation ​

The problem ​

The Plain-English Breakdown ​

Brute Force Analysis ​

The pattern ​

The solution ​

Code Walkthrough ​

Hand Trace ​

Edge Cases Handled ​

The division trap ​

Complexity ​

Where this goes next ​

What the interviewer will push on ​