#150
Evaluate Reverse Polish Notation
Medium Operand stack
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Evaluate an arithmetic expression in Reverse Polish (postfix) notation with + - * / on integers. Division truncates toward zero.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: compute a postfix expression.
Why this works: numbers go on a stack; an operator pops two, applies, and pushes the result.
Example: ["2", "1", "+", "3", "*"]
2, 1 → + → 33, 3 → * → 9
✦Hints open one at a time
Push numbers. On an operator, pop two numbers, apply it, push the result.
The first pop is the right operand.
↗Approach
Scan tokens with a stack. For an operator, b = pop, a = pop, push a op b. The final stack top is the answer. Java's int division already truncates toward zero.
</>Solution (Java)
import java.util.*;
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+": st.push(st.pop() + st.pop()); break;
case "*": st.push(st.pop() * st.pop()); break;
case "-": { int b = st.pop(), a = st.pop(); st.push(a - b); break; } // order matters
case "/": { int b = st.pop(), a = st.pop(); st.push(a / b); break; }
default: st.push(Integer.parseInt(t));
}
}
return st.pop();
}
}!Common mistake
Swapping operands for - and /, giving b − a instead of a − b.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon