Evaluate Reverse Polish Notation

1. Problem & Core Objective

The problem

Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /, and each operand may be an integer or another expression.

Input:  tokens = ["2","1","+","3","*"]              Output: 9       ((2 + 1) * 3)
Input:  tokens = ["4","13","5","/","+"]             Output: 6       (4 + (13 / 5))
Input:  ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]   Output: 22

Notes from the problem statement:

• Division between two integers truncates toward zero.
• The expression is always valid — no division by zero, and the result fits in a 32-bit integer.

Constraints:

• 1 <= tokens.length <= 10^4
• Each token is an operator, or an integer in [-200, 200]

What the interviewer is actually testing

The algorithm is six lines. The assessment is about precision:

1. Do you get the operand order right? - and / are not commutative, and the second pop is the left operand. This is the single most common bug in the problem.
2. Do you know Java's integer division semantics? Java truncates toward zero, which happens to match the spec — but knowing that it matches rather than assuming is the point.
3. Do you parse negative numbers correctly? "-11" is an operand, not a - operator. A naive "is it one character" check fails.
4. Can you explain why RPN needs no parentheses? That's the conceptual question behind the mechanical one.

2. First-Principles Thought Process

Step 1 — What Reverse Polish Notation is

Standard infix notation puts the operator between its operands: 2 + 1. That's ambiguous without precedence rules and parentheses — 2 + 1 * 3 could mean 9 or 5.

Postfix puts the operator after its operands: 2 1 +. There is exactly one way to read it, so no parentheses and no precedence rules are ever needed.

infix:    (2 + 1) * 3
postfix:   2 1 + 3 *

infix:     2 + (1 * 3)
postfix:   2 1 3 * +          ← different token order, no brackets required

Step 2 — Why a stack falls out naturally

Read the tokens left to right. When you meet an operator, which operands does it apply to?

The two most recently produced values. Those may be literal numbers just read, or results of earlier operations — it makes no difference.

"Most recently produced, not yet consumed" is exactly a stack.

Step 3 — The algorithm

• Number → push it.
• Operator → pop two values, combine them, push the result.

At the end, exactly one value remains: the answer. (The problem guarantees a valid expression, so this is assured.)

Step 4 — Get the operand order right

This is where the problem actually bites. Consider ["5", "2", "-"], meaning 5 - 2 = 3.

The stack after pushing is [5, 2] with 2 on top. So:

int b = stack.pop();    // 2  — pushed LAST, popped FIRST → the RIGHT operand
int a = stack.pop();    // 5  — the LEFT operand
push(a - b);            // 5 - 2 = 3   ✓

Writing stack.pop() - stack.pop() gives 2 - 5 = -3. Wrong.

The second pop is the left operand. For + and * it doesn't matter; for - and / it's the difference between right and wrong.

Naming the two values a and b rather than inlining the pops is what prevents this — and it also sidesteps Java's argument-evaluation subtleties.

Step 5 — Distinguish operators from operands

A negative number like "-11" starts with -. So "is this token an operator?" cannot be "does it start with a minus".

The reliable test is exact string equality against the four operators:

switch (token) { case "+": ... case "-": ... }

"-11" matches none of them and falls through to the number branch. A length check (token.length() == 1) would also work but is fragile.

3. Solution Paths

Approach 1 — Recursive evaluation from the right

private int pos;

public int evalRPN(String[] tokens) {
    pos = tokens.length - 1;
    return eval(tokens);
}

private int eval(String[] tokens) {
    String token = tokens[pos--];
    if (!isOperator(token)) return Integer.parseInt(token);

    int right = eval(tokens);      // the RIGHT operand is nearer the operator
    int left  = eval(tokens);      // then the left
    return apply(token, left, right);
}

How it works. Read from the right. The last token is always the outermost operator; its right operand is the sub-expression immediately before it, and its left operand precedes that.

• Time: O(n).
• Space: O(n) — recursion depth in the worst case.

Counter-questions on this approach

⭐ "Why does the right operand get evaluated first here, when the stack version pops it first too?"

Same underlying reason, mirrored. Scanning right-to-left, the tokens nearest an operator are its right operand — so the first recursive call consumes that sub-expression. In the stack version the right operand is on top for the same structural reason: it was produced most recently. Both are consequences of postfix ordering; neither is arbitrary.

"Why would you prefer the iterative version?"

Recursion depth is O(n) here, and with 10^4 tokens a deeply right-nested expression risks StackOverflowError. The iterative stack version uses heap memory instead of the call stack and has no depth limit. The recursion also relies on a mutable field for the cursor, which is easy to get wrong if the method is called twice.

Approach 2 — Stack evaluation (optimal)

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();

    for (String token : tokens) {
        switch (token) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
            case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); }
            default  -> stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

Trace on ["2","1","+","3","*"]:

Answer: 9 ✓

Trace on ["4","13","5","/","+"]:

Answer: 6 ✓ — note 13 / 5 truncates to 2, not 2.6.

• Time: O(n) — one pass, O(1) per token.
• Space: O(n) — the stack holds at most the operand depth.

Counter-questions on this approach

⭐ "Why do you name a and b for - and / but inline the pops for + and *?"

Because + and * are commutative — the order doesn't affect the result — while - and / are not. For those, the second pop is the left operand, since the right one was pushed last and comes off first. Writing stack.pop() - stack.pop() computes right-minus-left and is the most common bug in this problem.

Honestly I'd name them in all four cases for consistency; the inline form is fine but the asymmetry invites a copy-paste error.

⭐ "Does Java's integer division match the problem's 'truncate toward zero' requirement?"

Yes — Java's / on integers truncates toward zero, so -7 / 2 is -3, not -4. That matches the spec exactly, so no adjustment is needed. It's worth checking rather than assuming: Math.floorDiv(-7, 2) gives -4, and languages like Python floor rather than truncate, so this is a genuine portability trap.

"How does default correctly handle a token like \"-11\"?"

Because the switch compares whole strings for exact equality. "-11" doesn't equal "-", so it falls through to default and gets parsed as a number. A check like "starts with -" or "length is 1" would misclassify it — the string-equality switch makes this correct by construction.

"Could the intermediate results overflow?"

The problem guarantees the final answer fits in a 32-bit integer, and operands are bounded by ±200. Intermediate values could in principle exceed that in a malicious expression, but the validity guarantee rules it out. Without that guarantee I'd accumulate in long. Worth saying I checked the bound rather than relying on it silently.

"Why stack.pop() at the end rather than stack.peek()?"

Either works — the stack holds exactly one value for a valid expression. pop is marginally clearer about consuming the result. If I wanted to validate the input I'd assert the stack is empty afterwards, which pop makes natural.

Approach 3 — Array as a stack

public int evalRPN(String[] tokens) {
    int[] stack = new int[tokens.length];
    int top = 0;

    for (String token : tokens) {
        switch (token) {
            case "+" -> { stack[top - 2] += stack[top - 1]; top--; }
            case "-" -> { stack[top - 2] -= stack[top - 1]; top--; }
            case "*" -> { stack[top - 2] *= stack[top - 1]; top--; }
            case "/" -> { stack[top - 2] /= stack[top - 1]; top--; }
            default  -> stack[top++] = Integer.parseInt(token);
        }
    }
    return stack[0];
}

How it works. A plain int[] with a manual top index. The operation writes in place at top - 2 and decrements — no popping and re-pushing.

• Time: O(n).
• Space: O(n), but with no boxing — primitive ints rather than Integer objects.

Counter-questions on this approach

⭐ "Is avoiding autoboxing worth hand-rolling a stack?"

It's measurably faster — ArrayDeque<Integer> allocates an Integer for every push outside the −128..127 cache, and this does zero allocation. But it's more code and the index arithmetic (top - 2, top - 1) is easy to get wrong. I'd write the Deque version by default and reach for this only if profiling demanded it, or if the interviewer explicitly asked about allocation.

"How do you know tokens.length is a large enough array?"

Because every token either pushes one value or consumes two and pushes one — so the stack size never exceeds the number of tokens seen. It's a safe upper bound, and typically a generous one: a valid expression of n tokens has at most (n+1)/2 operands.

"Note the operand order here — did you get it right?"

Yes, and it's clearer than the pop version: stack[top - 2] is the left operand and stack[top - 1] is the right, because they were pushed in that order. stack[top-2] -= stack[top-1] is left-minus-right, which is correct. Positional indexing makes the ordering visible rather than something to reason about.

Comparison

4. Why the Optimal Wins

There's no O(n²) alternative to beat here — every approach is O(n), because each token is processed once. So this question isn't about complexity; it's about correctness and clarity. Say that explicitly rather than manufacturing a comparison.

Against recursion. Same complexity, but recursion depth is O(n) and could overflow the call stack on 10^4 deeply-nested tokens. The iterative version moves that storage to the heap, where it isn't bounded by JVM stack size.

Why the stack is the right structure and not just a structure:

Postfix notation is unambiguous precisely because each operator applies to the two most recently produced values. That's the defining property of a stack — RPN and stacks are two descriptions of the same structure.

That's why the algorithm needs no precedence table, no parentheses handling, and no lookahead. It's also why compilers convert infix to postfix (via the shunting-yard algorithm) before generating code.

Why O(n) time and space are both optimal. Every token must be read. And a right-leaning expression like 1 1 1 1 + + + genuinely requires holding O(n) operands before any operator arrives, so the space can't be reduced in the worst case.

5. Java Prerequisites

Integer division truncates toward zero

13 / 5      //  2
-13 / 5     // -2   ← truncation, NOT floor
13 / -5     // -2
Math.floorDiv(-13, 5)   // -3  ← floor, a different operation

Java's / truncates toward zero, which is what this problem requires. Verify the language's behaviour rather than assuming — Python's // floors, so -13 // 5 is -3 there.

% follows the same convention: -13 % 5 is -3 in Java.

Switch expressions (Java 14+)

switch (token) {
    case "+" -> stack.push(...);
    case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
    default  -> stack.push(Integer.parseInt(token));
}

Arrow syntax needs no break and cannot fall through. Braces allow multiple statements. Older Java needs case "+": ... break;.

switch on String compares with .equals, not == — which is what makes "-11" fall correctly to default.

Integer.parseInt

Integer.parseInt("-11");     // -11, handles a leading minus
Integer.parseInt("+5");      // 5, handles a leading plus (Java 7+)
Integer.parseInt("abc");     // throws NumberFormatException

The problem guarantees valid tokens, so no try/catch is needed — but say you checked rather than assuming.

Argument evaluation order

stack.push(stack.pop() - stack.pop());     // DON'T

Java evaluates arguments left to right, so this is firstPop - secondPop — which is right-minus-left and wrong. It's well-defined, just not what you want. Naming the operands removes both the bug and the need to remember the rule.

Deque vs int[]

Deque<Integer> stack = new ArrayDeque<>();   // boxes every value
int[] stack = new int[n]; int top = 0;       // no allocation

The Deque version is clearer; the array version avoids Integer allocation. Both O(n) space.

6. Interview Communication Guide

Clarifying questions

1. "How should division behave — truncate toward zero, or floor?" — the spec says truncate, and Java's / already does that. Asking shows you know they differ.
2. "Can operands be negative?" — yes, "-11" appears in the examples, which affects how you distinguish operators from numbers.
3. "Is the expression guaranteed valid?" — yes, so no division-by-zero handling or malformed-input checks.
4. "Can intermediate results overflow?" — the problem guarantees the answer fits in 32 bits.
5. "Are the tokens always single operators, or could there be multi-character ones like **?" — only the four listed.

The pitch

"Postfix notation puts the operator after its operands, which makes it unambiguous — no parentheses or precedence rules needed.

The reason it evaluates so cleanly is that an operator always applies to the two most recently produced values, whether those are literals or results of earlier operations. 'Most recent, not yet consumed' is exactly a stack.

So: push numbers; on an operator, pop two, combine, push the result. One value remains at the end — that's the answer.

The detail I want to be careful about is operand order. The value pushed last comes off first, so it's the right operand. For - and / that matters: 5 2 - means 5 minus 2, so I pop 2 first, then 5, and compute a - b. I'll name them rather than inlining the pops, because stack.pop() - stack.pop() computes it backwards.

Two other things: Java's integer division truncates toward zero, which matches the spec — worth confirming since some languages floor instead. And I'll dispatch on exact string equality so that \"-11\" is treated as a number rather than a minus operator.

O(n) time and space."

Edge cases to raise proactively

["5","2","-"] is the one to volunteer — it's the minimal case that exposes reversed operand order, and stating it before coding shows you anticipated the bug rather than discovering it.

["-11","2","*"] is the second — it's the case that breaks any "is the token a minus sign?" classification.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Evaluate an infix expression instead — \"(2 + 1) * 3\"."

Now you need precedence and parentheses. The standard approach is the shunting-yard algorithm: two stacks, one for operators and one for output, popping operators of higher-or-equal precedence when a new one arrives. It converts infix to postfix, which you then evaluate with exactly the code above. O(n) time and space. This is the natural escalation, and it's why RPN exists in the first place.

"What if the expression could be malformed?"

Add validation: check the stack has at least two values before each operator, catch NumberFormatException on parsing, guard division by zero, and assert exactly one value remains at the end. Each maps to a distinct malformation, so you can report which rather than just failing.

"Add support for unary minus, or operators like ^ and %."

% and ^ are mechanical additions to the switch. Unary minus is genuinely harder because - becomes context-dependent — it's binary after an operand and unary after another operator or at the start. In postfix this is usually resolved by using a distinct token (such as ~) for negation, precisely to keep the grammar unambiguous.

"What if operands were floating point?"

Switch the stack to Deque<Double> and use Double.parseDouble. Division no longer truncates, and you inherit floating-point issues — 0.1 + 0.2 != 0.3 — so equality comparisons on results become unreliable. For exact decimal arithmetic you'd use BigDecimal.

"What if the token stream were enormous and arrived incrementally?"

The stack version already handles it — it processes each token once and never looks back, so it works on a stream with O(depth) memory rather than O(n). The recursive version could not, since it reads from the right.

"Evaluate the expression and return the sequence of operations performed."

Record each (operator, left, right, result) as you go. No complexity change, and it's how a debugger or a spreadsheet's formula-audit view works. Since the stack already holds the operands at the moment of combination, the information is free.