Evaluate Reverse Polish Notation

Given an array of string tokens representing a valid arithmetic expression in Reverse Polish Notation (postfix notation), evaluate it and return the integer result. Operators are +, -, *, /. Division truncates toward zero.

• 1 ≤ tokens.length ≤ 1000
• Each token is an operator or an integer in [-100, 100]
• Division always truncates toward zero
• The expression is always valid

Examples

How to think about it

Normal math uses parentheses to express order of operations: (2 + 1) * 3. Reverse Polish Notation removes the parentheses by placing the operator after its operands: 2 1 + 3 *. The order of the tokens encodes the order of evaluation.

A stack fits this perfectly. When you see a number, hold it. When you see an operator, the two most recent numbers are its operands — pop them, compute, push the result back. At the end, one number remains: the answer.

Brute Force — O(n²)

Repeatedly scan the token list. When you find an operator, take the two numbers before it, compute the result, and collapse those three tokens into one. Restart the scan until only one token remains.

def evalRPN(tokens):
    while len(tokens) > 1:
        for i in range(len(tokens)):
            if tokens[i] in "+-*/":
                a, b = int(tokens[i-2]), int(tokens[i-1])
                result = a + b if tokens[i] == '+' else \
                         a - b if tokens[i] == '-' else \
                         a * b if tokens[i] == '*' else int(a / b)
                tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                break
    return int(tokens[0])

Each scan is O(n) and you may do up to O(n) scans, giving O(n²) overall. The stack solution is a single pass.

Stack — O(n)

One pass through tokens. Numbers push; operators pop two, compute, push one.

def evalRPN(tokens):
    stack = []
    for c in tokens:
        if c not in "+-*/":
            stack.append(int(c))
        elif c == "+":
            stack.append(stack.pop() + stack.pop())
        elif c == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif c == "*":
            stack.append(stack.pop() * stack.pop())
        else:
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a))   # truncate toward zero
    return stack[0]

Complexity

When does this pattern show up?

Any time you need to evaluate a sequence where earlier values are consumed by later operators, a stack is the tool. This is the basis of how virtually every programming language evaluates expressions internally.

Same pattern elsewhere

• Valid Parentheses — push openers, pop when a closer matches.
• Basic Calculator — extends RPN with parentheses and sign tracking.
• Daily Temperatures — monotonic stack; elements wait on the stack until something "consumes" them.
• Decode String — nested brackets use a stack to defer processing until a closer arrives.

Reading the constraints

• tokens.length ≤ 1000 — O(n²) would work on size, but a clean O(n) stack is expected.
• Division truncates toward zero — not floor. This matters for negatives: -7/2 = -3, not -4.
• Input is always valid — no empty stack pops, no malformed tokens.

Where people go wrong

Wrong operand order for subtraction and division

The first pop gives the right operand; the second pop gives the left. For commutative operators (+, *) order doesn't matter. For - and / it does.

# tokens = ["5", "3", "-"]  → should be 5 - 3 = 2

a = stack.pop()   # a = 3  (right operand, pushed second)
b = stack.pop()   # b = 5  (left operand, pushed first)

# Wrong:
stack.append(a - b)  # 3 - 5 = -2  ✗

# Correct:
stack.append(b - a)  # 5 - 3 = 2   ✓

Floor division vs truncation toward zero

Python's // floors toward negative infinity. -7 // 2 = -4. The problem wants truncation toward zero: -7 / 2 = -3. Use int(b / a) or int(float(b) / a) in Python.

# Wrong — floors toward -inf:
stack.append(b // a)     # -7 // 2 = -4  ✗

# Correct — truncates toward zero:
stack.append(int(b / a)) # int(-7 / 2) = int(-3.5) = -3  ✓

Treating "-3" as the minus operator

Don't check token[0] == '-' to detect operators — that misclassifies negative numbers like "-3". Check exact equality: token in "+-*/" ortoken not in "+-*/".

Quick tests

• ["2","1","+","3","*"] → 9
• ["1","2","+","3","*","4","-"] → 5
• ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] → 22
• ["-7","2","/"] → -3 (not -4)

What to do next

• Valid ParenthesesEasyCore stack pattern — push openers, pop/match on closers. Foundational.›
• Min StackMediumAugmented stack — same structure, extra O(1) query on top of it.›
• Daily TemperaturesMediumMonotonic stack — values sit waiting until something larger arrives.›
• Basic CalculatorHardRPN + parentheses. Same stack idea but you must handle infix notation.›