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

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.

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.

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)$ .

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 pattern ​

The solution ​

The division trap ​

Complexity ​

Where this goes next ​

What the interviewer will push on ​