Evaluate Reverse Polish Notation
Evaluate an expression in reverse Polish notation. Each operator consumes the preceding two results. Integer division truncates toward zero.
Work through the cases
3 examplesInput notation
Space-separated integers and operators +, -, *, /. The expression is valid and no divisor is zero.Expected result
The resulting integer.Case 1
Input
4 2 + 3 *
Expected output
18
Case 2
Input
7 -2 /
Expected output
-3
Case 3
Input
-3 2 * 4 +
Expected output
-2
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Reverse Polish notation puts the operator after its operands, so evaluation order is already fixed and we need no parentheses or precedence. n ≤ 10^4. Push numbers; on an operator pop two values, compute, and push back. The stack holds pending intermediates; one value remains.
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stk = new ArrayDeque<>();
for (String t : tokens) {
if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
stk.push(Integer.parseInt(t));
} else {
int y = stk.pop();
int x = stk.pop();
switch (t) {
case "+":
stk.push(x + y);
break;
case "-":
stk.push(x - y);
break;
case "*":
stk.push(x * y);
break;
default:
stk.push(x / y);
break;
}
}
}
return stk.pop();
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.