Problem Statement

Evaluate Reverse Polish Notation

You are given a math expression written in a special order called Reverse Polish Notation, or RPN. In normal math you write the operator between the numbers, like 2 + 1. In RPN you write both numbers first and then the operator, like 2 1 +. The valid operators are + (add), - (subtract), * (multiply), and / (divide). Each piece of the expression is called a token, which just means one item in the list, either a number or an operator. Your job is to work out the final value of the whole expression. One rule for division: the answer is cut toward zero, so 13 / 5 becomes 2, not 2.6, and the part after the decimal point is dropped.

easyStackStackTime: O(n) · Space: O(n)

Signals to notice

postfix expressionevaluate left-to-rightoperands before operator

Brute force first

No better approach exists — stack is the natural solution. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Push numbers onto stack; when you see an operator, pop two operands, compute, push result. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `tokens=["2","1","+","3","*"]`

token="2": not an operator -> push 2. stack=[2]
token="1": not an operator -> push 1. stack=[2,1]
token="+": pop b=1, a=2 -> push a+b=3. stack=[3]
token="3": not an operator -> push 3. stack=[3,3]
token="*": pop b=3, a=3 -> push a*b=9. stack=[9]
loop done -> return stack[0]=9

What must stay true

The stack always contains operands waiting for their operator. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

stack = []
for token in tokens:
    if token is an operator:
        b = stack.pop(); a = stack.pop()   # order matters: a op b
        stack.push(apply(token, a, b))     # for '/', truncate toward zero
    else:
        stack.push(int(token))
return stack[0]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Operand order matters for subtraction and division — second popped is left operand. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Stack Pattern