#150 Evaluate Reverse Polish Notation
the problem
In plain words
Evaluate an arithmetic expression written in Reverse Polish (postfix) notation, given as an array of tokens. Operators are + − * /. Division between integers truncates toward zero. The expression is always valid.
in tokens = ["2","1","+","3","*"]
out 9
((2 + 1) * 3) = 9
in tokens = ["4","13","5","/","+"]
out 6
4 + (13 / 5) = 4 + 2 = 6
in tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
out 22
9 + 3 = 12; 12 × −11 = −132; 6 / −132 = 0 (truncated); 10 × 0 = 0; 0 + 17 + 5 = 22.
- 1 ≤ tokens.length ≤ 10⁴
- Each token is an operator or an integer in [−200, 200]
- No division by zero; every intermediate value fits in a 32-bit int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternStack for matching & nesting
where this runsThe JVM runs your compiled Java the same way: iload, iload, iadd pushes two values and an operator pops them.
In postfix, an operator always applies to the two most recent values. Keep values on a stack; an operator pops two and pushes one.
solutions
From brute force to optimal
Find the first operator; the two tokens before it are its operands. Replace the three tokens with the result. Repeat.
- Copy tokens into an ArrayList.
- Find the first operator at index i.
- Replace tokens i−2..i with the result.
- Repeat until one token is left.
Up to n/2 operators, and each search + ArrayList removal is O(n).
The list copy.
class Solution { public int evalRPN(String[] tokens) { List<String> list = new ArrayList<>(Arrays.asList(tokens)); while (list.size() > 1) { int i = 0; while (!isOperator(list.get(i))) i++; // first operator in the list int a = Integer.parseInt(list.get(i - 2)); int b = Integer.parseInt(list.get(i - 1)); int result = apply(list.get(i), a, b); list.set(i - 2, String.valueOf(result)); // replace "a b op" with its value list.remove(i); list.remove(i - 1); } return Integer.parseInt(list.get(0)); } private boolean isOperator(String t) { return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/"); } private int apply(String op, int a, int b) { return switch (op) { case "+" -> a + b; case "-" -> a - b; case "*" -> a * b; default -> a / b; }; }}Numbers are pushed. An operator pops b (right) then a (left), and pushes a op b.
- For each token:
- number → push it.
- operator → b = pop(), a = pop(), push(a op b).
- The single value left is the answer.
Each token is handled once with O(1) stack work.
Up to about n/2 numbers can wait on the stack (e.g. "1 2 3 4 + + +").
class Solution { public int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String t : tokens) { switch (t) { case "+", "-", "*", "/" -> { int b = stack.pop(); // right operand comes off FIRST int a = stack.pop(); int result = switch (t) { case "+" -> a + b; case "-" -> a - b; case "*" -> a * b; default -> a / b; // Java int division truncates toward zero, as required }; stack.push(result); } default -> stack.push(Integer.parseInt(t)); } } return stack.pop(); }}Dry run
Same algorithm with a primitive array and a top index — no Integer boxing.
- Size the array (n + 1) / 2: at most that many numbers wait at once.
- stack[top++] = number; operators read stack[--top] twice.
One pass.
The array of ⌈n/2⌉ ints.
class Solution { public int evalRPN(String[] tokens) { int[] stack = new int[(tokens.length + 1) / 2]; // at most ceil(n/2) numbers wait at once int top = 0; // next free slot for (String t : tokens) { if (t.length() == 1 && "+-*/".indexOf(t.charAt(0)) >= 0) { int b = stack[--top]; int a = stack[--top]; stack[top++] = switch (t.charAt(0)) { case '+' -> a + b; case '-' -> a - b; case '*' -> a * b; default -> a / b; }; } else { stack[top++] = Integer.parseInt(t); // "-3" is a number, not an operator } } return stack[0]; }}in the room
How to say it in the interview
talk track
- Explain postfix in one line: "operators come after their operands, so no parentheses are needed."
- Stress the pop order: the first pop is the right operand.
- Mention that Java's
/on ints already truncates toward zero, matching the spec.
traps
- Checking
token.charAt(0) == '-'to detect an operator: "-11" is a number. Compare the whole token. - Swapping a and b — wrong answers for − and / only, so simple tests can hide the bug.
what they ask next
Follow-ups
Basic Calculator II (LC 227): infix with + − * / and no parentheses?
Keep a stack of signed terms: push ±num for + and −, but for * and / pop the last term, combine, and push back. Sum the stack at the end.
Convert infix to postfix?
Dijkstra's shunting-yard algorithm: an operator stack ordered by precedence; output numbers directly.
before you submit
Edge cases to test
- A single number like ["42"] is already the answer.
- "-11" is a number, not the '-' operator — compare the whole token.
- Division truncates toward zero: -7 / 2 = -3. Java's int
/already does exactly that.
practise next
Similar problems
- #394Decode StringMediumin Stacks
- #20Valid ParenthesesEasyin Stacks