LeetCode 150 · Medium · Stack

Evaluate Reverse Polish Notation

Evaluate an arithmetic expression written in postfix order, where each operator comes after its two operands, as in 2 1 + 3 * for (2 + 1) * 3. Division truncates toward zero.

O(n)time
O(n)space
pop 2, push 1per operator

integers −99 to 99 and + − * / · space or comma separated · 1–13 tokens · must be a valid postfix expression · every result within ±99999

=

stackoperands waiting

public int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String t : tokens) { if ("+-*/".contains(t)) { int b = stack.pop(); int a = stack.pop(); // right operand is on top if (t.equals("+")) { stack.push(a + b); } else if (t.equals("-")) { stack.push(a - b); } else if (t.equals("*")) { stack.push(a * b); } else { stack.push(a / b); // truncates toward 0 } } else { stack.push(Integer.parseInt(t)); } } return stack.peek();}
t
—
a, b
—
stack
[]
top means
—

Why it works

  1. Brute force rewrites the list: find the first operator, replace it and its two operands with their result, and repeat. Each rewrite rescans and shifts the list: O(n²).
  2. Key insight: an operator always applies to the two most recent unused values. Most recent first is last in, first out: a stack. Invariant: the stack holds the values of the complete sub-expressions read so far, in order.
  3. O(n) time, O(n) space. Every token is pushed once, and every operator pops two and pushes one. A valid expression ends with exactly one value: the answer.
  4. Pitfall: operand order and division. The first pop is the right operand, so 3 4 - is 3 - 4, not 4 - 3. And division must truncate toward zero: Java's / on int already does, so -7 / 2 is -3 (Math.floorDiv would give -4). Compare tokens with equals, not ==. Also, "-11" is a number, not an operator.
  5. Related: Basic Calculator (224, 227) turns infix into this form on the fly with an operator stack; the shunting-yard algorithm is the general version.