A quote engine in a pricing service already had a parser. What landed on the evaluate path was postfix tokens: integers and + - * /, parentheses gone. The intern rebuilt infix with a nest of parens and handed the string to an evaluator. A dozen tokens in staging quoted correctly. A few thousand tokens in the nightly book were still concatenating when the job timed out.
Evaluate Reverse Polish Notation asks you to fold a postfix token list into one integer. Postfix already tells you when to apply an operator. Rebuilding infix uses that and still pays a second parse. A nested scan that splices the first operator is honest and quadratic.
This is an interview writeup, not a LIFO lecture. The stack post owns push, pop, and why last-in is the ADT. Here we only care about pending numbers so an operator is a pop-pop-push, not a reparse. Matching brackets is Valid Parentheses — that post owns the parse-family checker. This prompt evaluates an expression that is already known valid.
The problem
Given a String[] tokens of integers and the operators +, -, *, and /, evaluate the Reverse Polish Notation expression and return the integer result. An operator applies to the two operands immediately before it. Division truncates toward zero. The expression is valid: no divide-by-zero, and every intermediate fits in a 32-bit int.
tokens = ["2","1","+","3","*"] → 9 because (2 + 1) * 3
tokens = ["4","13","5","/","+"] → 6 because 4 + (13 / 5)
tokens = ["7","2","/"] → 3 because 7 / 2 truncates toward zeroNote: Unary minus is not a token of its own. If the parser already split the input, a negative value is one string ("-11") and "-" by itself is subtraction. Java int division already truncates toward zero — 7 / 2 is 3, and (-7) / 2 is -3, not -4. You do not call Math.floor.
Splicing the first operator is the honest brute force
Rebuilding a fully parenthesized infix string and eval-ing it is the wrong interview bill — Java has no eval, and you would re-parse work the postfix already did. Recursive descent on the token array is the same idea with extra frames. The honest quadratic stays on the list: find the leftmost operator, take the two tokens immediately before it as a then b, replace those three with a op b, and repeat until one value remains.
int evalRpnReduce(String[] tokens) {
List<String> t = new ArrayList<>(Arrays.asList(tokens));
while (t.size() > 1) {
int i = 0;
while (i < t.size()
&& !t.get(i).equals("+")
&& !t.get(i).equals("-")
&& !t.get(i).equals("*")
&& !t.get(i).equals("/")) {
i++;
}
int a = Integer.parseInt(t.get(i - 2));
int b = Integer.parseInt(t.get(i - 1));
int v;
switch (t.get(i)) {
case "+":
v = a + b;
break;
case "-":
v = a - b;
break;
case "*":
v = a * b;
break;
default:
v = a / b;
break;
}
t.set(i - 2, Integer.toString(v));
t.remove(i);
t.remove(i - 1);
}
return Integer.parseInt(t.get(0));
}Each reduction copies the tail of the list. At n = 20 that is a rounding error. At n in the tens of thousands you paid nested splices for a question whose pending operands are already the top two of a stack.
Push numbers, pop two on an operator
Walk left to right. A number is a parseInt and a push. An operator pops the top two values, applies the op, and pushes the result.
First pop is the right operand. The stack’s top is whatever was pushed last — that is b. Then a. Then a / b, never b / a. Swap the names and ["7","2","/"] returns 0.
tokens = ["2","1","+","3","*"]
2 push stack: 2
1 push stack: 2 1
+ pop b=1, a=2 push 3 stack: 3
3 push stack: 3 3
* pop b=3, a=3 push 9 stack: 9
end → 9
tokens = ["7","2","/"]
7 push stack: 7
2 push stack: 7 2
/ pop b=2, a=7 7/2 = 3 stack: 3
end → 3The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack.
int evalRPN(String[] tokens) {
Deque<Integer> vals = new ArrayDeque<>();
for (String tok : tokens) {
if (tok.equals("+") || tok.equals("-")
|| tok.equals("*") || tok.equals("/")) {
int b = vals.pop();
int a = vals.pop();
int v;
switch (tok) {
case "+":
v = a + b;
break;
case "-":
v = a - b;
break;
case "*":
v = a * b;
break;
default:
v = a / b;
break;
}
vals.push(v);
} else {
vals.push(Integer.parseInt(tok));
}
}
return vals.pop();
}Time is O(n) — one pass, one push or two pops per token. Space is O(n) for pending numbers (worst case the tokens are all integers until a burst of operators). The prompt promised a valid expression, so the final pop is the answer; you do not guard an empty deque unless they change the contract.
Note: Distinguish "-" from "-11" by equality with the four operators, not by parseInt in a try/catch. A leading minus on a number is already inside that token.
What interviewers usually poke next
- Pop order. Say
bthenaout loud. Subtraction and division are not commutative; a swapped pair is a silent wrong answer, not a crash. - Toward-zero division. Java
intdivision is the spec.Math.floorof a negative quotient goes the other way; do not reach for it. - Only matching, not evaluating. That is Valid Parentheses. A checker does not compute
7 / 2. - Infix with precedence. Basic Calculator II is a later problem; it still uses a stack, but now you delay
+/-while*//bind tighter. Do not start that walk on a postfix prompt. - Invalid tokens / missing operands. The prompt forbids it. In production you would reject an operator on fewer than two values; at the board, ask.
You are done with this problem when you can pop b then a, say why 7 / 2 is 3 without Math.floor, and refuse to rebuild infix.