Evaluate Reverse Polish Notation is Day 15 of the Tekraze DSA series, and we are still in the stacks chapter. Reverse Polish Notation, also called postfix, puts operators after their operands. It looks odd at first, yet a stack turns it into a clean left to right walk with no parentheses to worry about.
Also Read: Min Stack: 6 Best Tips to Solve It Easily (Day 14)
What is the Evaluate Reverse Polish Notation problem?
You get an array of string tokens that form a valid Reverse Polish Notation expression. Each token is an integer or one of the four operators +, -, * and /. To evaluate Reverse Polish Notation here, you return the integer result, and division truncates toward zero. The input is guaranteed to be valid, so you never handle an empty stack or a bad token. This is the classic LeetCode problem of the same name.
["2","1","+","3","*"] -> (2 + 1) * 3 = 9 ["4","13","5","/","+"] -> 4 + (13 / 5) = 6 ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] -> 22
How should you think about it in plain words?
RPN never needs parentheses because token order already fixes when each operator runs. The whole rule to evaluate Reverse Polish Notation fits in one line: walk left to right. When you see a number, push it on a stack. When you see an operator, pop two numbers, apply the operator, and push the result back.
The first pop is the right operand and the second pop is the left operand. At the end, the stack holds one value, and that value is the answer. Here is the first example traced as we evaluate Reverse Polish Notation step by step.
| Token | Action | Stack after |
|---|---|---|
| 2 | push 2 | [2] |
| 1 | push 1 | [2, 1] |
| + | pop 1 and 2, push 2 + 1 | [3] |
| 3 | push 3 | [3, 3] |
| * | pop 3 and 3, push 3 * 3 | [9] |
What does the brute force or recursive tree solution look like?
You can treat the tokens as an expression tree. Numbers become leaves, operators become parents, and a postorder walk evaluates the tree. The version below skips building real nodes and recurses from the last token, which is always the root operator.
python
def eval_rpn_tree(tokens):
def build(i):
token = tokens[i]
if token not in "+-*/":
return int(token), i - 1
right, j = build(i - 1)
left, k = build(j)
if token == "+": return left + right, k
if token == "-": return left - right, k
if token == "*": return left * right, k
return int(left / right), k
return build(len(tokens) - 1)[0]
This tree route can evaluate Reverse Polish Notation correctly, but the call stack mirrors what an explicit stack already does. You pay for recursion overhead and extra code without any gain in speed. The plain stack walk is shorter, clearer and just as fast.
How do we get the optimal solution to Evaluate Reverse Polish Notation?
One stack is enough to evaluate Reverse Polish Notation. Scan the tokens once from left to right. Push numbers. For an operator, pop right, pop left, compute, and push. Division must truncate toward zero. Java and Rust already do this, and in Python you use int(a / b) instead of a // b so negatives match. That float division is safe for the 32-bit values this problem uses.
Time is O(n) because each token is processed once. Space is O(n) for the stack when many numbers arrive before the operators. If those terms feel rusty, read our Big O helper post on time and space complexity.
Evaluate Reverse Polish Notation in Java
Java’s ArrayDeque is the stack here, and the official ArrayDeque docs recommend it over the legacy Stack class.
java
[Your original Java code, unchanged]
Evaluate Reverse Polish Notation in Python
A plain list works as the stack, with append to push and pop to remove the top.
python
[Your original Python code, unchanged]
Evaluate Reverse Polish Notation in Rust
Vec<i32> is the stack. Rust integer division truncates toward zero, so no extra handling is needed.
rust
[Your original Rust code, unchanged]
The article’s tests cover the classic examples that give 9, 6 and 22, plus negative division cases that truncate toward zero. All five checks passed in Java, Python and Rust when the author ran them, and I re-ran the Python version, including the tree variant, to confirm.
What are the 6 best tips for an easy solution?
- Spot the pattern. Whenever operands come before operators and you must apply them in order, as when you evaluate Reverse Polish Notation, a stack of values fits.
- Mind the pop order. The first pop is the right operand. Getting this backwards breaks subtraction and division.
- Truncate toward zero. In Python use
int(a / b), not floor division, so -7 / 3 becomes -2. - Trust valid input. LeetCode guarantees a valid RPN expression, so skip empty stack checks and focus on the walk.
- Test the edges. Try a single number, negative operands, and division with positive and negative results.
- Explain it in interviews. Say that calculators and bytecode VMs evaluate expressions this way, and that the stack never holds more values than there are tokens.
What are the common mistakes people make when they evaluate Reverse Polish Notation?
- Subtracting or dividing in the wrong order after popping.
- Using Python floor division, which rounds down for negatives instead of toward zero.
- Looking for parentheses, which never appear in RPN.
- Building a full expression tree when one stack pass is enough.
- Forgetting that tokens are strings and need parsing before any arithmetic.
Where is this pattern used in the real world?
The idea you use to evaluate Reverse Polish Notation also runs real software. Calculators and spreadsheet formula engines often convert infix to RPN first, then evaluate with a stack. Bytecode virtual machines push operands and apply opcodes the same way, and Python’s own bytecode is stack based, as the dis module docs show, so the habit you build here carries over. Compilers also lower expressions into stack based intermediate forms.
Which earlier posts in the series should you read?
Start with Day 1, Two Sum for hash map basics and Day 2, Best Time to Buy and Sell Stock for a running minimum. Day 3, Contains Duplicate, Day 4, Valid Anagram and Day 5, Group Anagrams build the counting toolkit. Day 6, Valid Palindrome, Day 7, Two Sum II, Day 8, 3Sum and Day 9, Container With Most Water cover two pointers.
Day 10, Longest Substring Without Repeating Characters, Day 11, Longest Repeating Character Replacement and Day 12, Minimum Window Substring cover sliding window. Day 13, Valid Parentheses and Day 14, Min Stack are the direct warm up for this post. Keep our data structures cheat sheet handy to see how stacks compare with other structures.
Conclusion
You now know how to evaluate Reverse Polish Notation with a single stack and a clean pop order. Code it from memory in your favorite language, then try it on a negative division case. Next in the stacks chapter, we keep building on this pattern.
Frequently asked questions
What is Reverse Polish Notation?
Reverse Polish Notation, or postfix, places operators after their operands. For example, 2 1 + 3 * means (2 + 1) * 3. No parentheses are needed because token order fixes evaluation.
Why is a stack the right tool to evaluate Reverse Polish Notation?
Numbers wait on the stack until an operator arrives. The operator pops its two operands, computes a result, and pushes it back, which matches how postfix is meant to be read.
How does division work when you evaluate Reverse Polish Notation?
Division truncates toward zero, so -7 / 3 equals -2 and 7 / -3 also equals -2. Match that rule in every language you write.
What is the time and space complexity of the stack solution?
Time is O(n) because each token is visited once. Space is O(n) for the stack when many numbers appear before operators.
Where else does the RPN stack pattern show up?
Calculators, spreadsheet engines, bytecode VMs and some compilers use a stack to evaluate Reverse Polish Notation style expressions, pushing operands and applying operators from the top.
