Algorithm

Evaluate Reverse Polish Notation

Stacks & Queues Pattern

Evaluate RPN

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are '+', '-', '*', and '/'. Each operand may be an integer or another expression. Division between two integers should truncate toward zero. The given RPN expression is always valid.

CONSTRAINTS
  • 1 <= tokens.length <= 10⁴
  • tokens[i] is either an operator (+, -, *, /) or an integer in range [-200, 200]
  • Division truncates toward zero; expression is always valid
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)) = 6
EXAMPLE 3
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
How should the program handle division by zero?
In most interview settings, you can assume the input RPN expression is valid and will not result in division by zero unless specified otherwise.
What should we do if the calculated result exceeds the range of a 32-bit integer?
You should clarify this with the interviewer. Standard RPN problems often guarantee results fit within 32 bits, but using a 64-bit integer (long) for intermediate steps is a safe defensive practice.

Standard math (3 + 4) is like a bridge: the operator sits between two numbers. But in Reverse Polish Notation (3 4 +), the operator is like a hungry creature that arrives after the numbers. When it appears, it immediately consumes the two most recent values it saw and leaves a single result in their place.

Because an operator always needs the two values that arrived most recently, we need a data structure that prioritizes the Last-In items. A Stack is the perfect tool for this deferred calculation.

The Hungry Operator

1. Finding Food: As we scan the expression from left to right, every number we see is a potential meal. We Push these numbers onto the Stack to keep them ready.
2. The Feast: When we encounter an operator (+, -, *, /), it triggers a reaction. The operator Pops the two most recent numbers from the Stack.
- Important: The first number popped is the second operand, and the second number popped is the first operand (crucial for subtraction and division!).
3. The Leftovers: After the calculation, we Push the result back onto the Stack. It might become food for a future operator!
4. The Survivor: Once we finish the scan, every operator has eaten its fill, and exactly one number remains on the Stack—the final result.

Code Blueprint
text
stack = []

FOR each token in expression:
    IF token is a Number:
        stack.PUSH(int(token))
    ELSE (it is an operator):
        val2 = stack.POP()
        val1 = stack.POP()
        
        IF token is '+': result = val1 + val2
        IF token is '-': result = val1 - val2
        IF token is '*': result = val1 * val2
        IF token is '/': result = truncate(val1 / val2)
        
        stack.PUSH(result)

RETURN stack.POP()
Worked Example:["4", "13", "5", "/", "+"]
0
4
Top
Token: '4'. It is a number. Push onto stack. Stack = [4].
0
4
1
13
Top
Token: '13'. It is a number. Push onto stack. Stack = [4, 13].
0
4
1
13
2
5
Top
Token: '5'. It is a number. Push onto stack. Stack = [4, 13, 5].
0
4
1
2
Top
Token: '/'. Pop 5 (right operand) and 13 (left operand). Compute 13 / 5 = 2. Push result 2. Stack = [4, 2].
0
6
Result
Token: '+'. Pop 2 (right operand) and 4 (left operand). Compute 4 + 2 = 6. Push result 6. Stack = [6].
Interactive Strategy Visualization
POSTFIX EVALUATION ENGINE

Reverse Polish Notation Mechanics

2
1
+
3
*

Intuition

  • Post-Order Logic: In RPN, operators follow their operands. The stack naturally holds operands until an operator arrives.
  • The Order of Popping: The first popped item is the right operand (b), and the second is the left (a).
  • Recursive Nature: Each result pushed back to the stack becomes an operand for a future operator.
MECHANICSSTEP 1/7
Start with an empty stack.
LOGIC

RPN Strategy

Scan the tokens from left to right. If the token is a number, push it to the stack. If it is an operator, pop the two most recent numbers, apply the operator, and push the result back. At the end, the stack will contain exactly one value: the final result.

O(N) One Pass · O(N) Stack of Waiting Numbers