LeetCode · #150

Evaluate Reverse Polish Notation Solution

Evaluate an arithmetic expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #150

🏗️

Pattern

Stack — expression evaluation

You are given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation. Evaluate the expression and return the result as an integer. Division truncates toward zero. The input is always a valid RPN expression.

Example 1

 Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9 // ((2 + 1) * 3) = 9 

Example 2

 Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6 // (4 + (13 / 5)) = 4 + 2 = 6 

Constraints

 • 1 ≤ tokens.length ≤ 10⁴ • tokens[i] is an operator (+, -, *, /) or an integer in [-200, 200] • Division truncates toward zero • Input always represents a valid RPN expression 

Section Two · Approach 1

Why No Brute Force?

RPN was invented for stack-based evaluation. There's no simpler approach — the stack solution is both the natural and optimal way to evaluate postfix expressions. Without a stack, you'd need to recursively reconstruct the expression tree, which is more complex, not simpler.

Context:

RPN (postfix notation) eliminates the need for parentheses and operator precedence rules.
The stack processes it in a single left-to-right pass.
This is exactly how calculators and many programming language VMs (like the JVM bytecode interpreter) evaluate expressions internally.

Section Three · Approach

Stack Evaluation — O(n)

Scan tokens left to right. If it's a number, push onto stack. If it's an operator, pop two operands, apply the operator, and push the result back. The final answer is the one remaining element on the stack.

💡 Mental model: Think of stacking ingredients for a recipe. Numbers are ingredients that pile up. An operator is a cooking step: take the top two ingredients, combine them, and put the result back. At the end, you have one finished dish — the answer.

Algorithm

Step 1: Create an empty stack.
Step 2: For each token: if it's a number, push it.
Step 3: If it's an operator, pop b (top) then a (second). Compute a op b. Push result.
Step 4: Return the single element remaining on the stack.

⚠ Operand order matters:

Pop b first, then a. The operation is a op b, not b op a.
For subtraction and division, order changes the result: "4 2 -" = 4 − 2 = 2, not 2 − 4 = −2.

Section Four · Trace

Visual Walkthrough

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

Stack — push numbers, pop-compute-push on operators

Section Five · Implementation

Code — Java & Python

Java — Stack Evaluation

 import java.util.Stack;
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
switch (token) {
case "+": stack.push(stack.pop() + stack.pop()); break;
case "-": { int b=stack.pop(), a=stack.pop(); stack.push(a-b); break; }
case "*": stack.push(stack.pop() * stack.pop()); break;
case "/": { int b=stack.pop(), a=stack.pop(); stack.push(a/b); break; }
default: stack.push(Integer.parseInt(token));
            }
        }
return stack.pop();
    }
}

Python — Stack Evaluation

 class Solution:
def evalRPN(self, tokens: list[str]) -> int:
        stack = []
for token in tokens:
if token in "+-*/":
                b, a = stack.pop(), stack.pop()
if token == '+': stack.append(a + b)
elif token == '-': stack.append(a - b)
elif token == '*': stack.append(a * b)
else:               stack.append(int(a / b)) # truncate toward 0 else:
                stack.append(int(token))
return stack[0]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Stack ← only approach	O(n)	O(n)	Each token processed once. Stack holds at most (n+1)/2 numbers.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Single number	`["42"]`	No operators — push 42, return 42.
Negative numbers	`["-1", "2", "+"]`	Negative tokens like "-1" must be parsed, not confused with "-" operator.
Division truncation	`["7", "-2", "/"]`	7 / -2 = -3.5 → truncate toward zero = -3 (not -4).
Subtraction order	`["4", "2", "-"]`	Pop b=2, a=4. Result = 4-2=2. Swapping gives wrong answer.

⚠ Common Mistake (Python): Using // for integer division. In Python, -7 // 2 = -4 (floor division), but the problem wants truncation toward zero: -7 / 2 = -3. Use int(a / b) instead of a // b to truncate correctly for negative results.

← Back to Stack problems

LearningTree

LC 150 · Evaluate Reverse Polish Notation — Solution & Explanation | DSA Guide