Evaluate Reverse Polish Notation

PracticeNeetCode ↗LeetCode ↗

Evaluate an arithmetic expression given as a list of tokens in Reverse Polish (postfix) notation, where each token is an integer or one of + - * /. Division truncates toward zero.

Example

Key Pointers

• In postfix notation, an operator always comes right after its two operands — a stack naturally holds pending numbers until an operator consumes the most recent two.
• Order matters for non-commutative operators (-, /): the second value popped is the left operand, the first value popped is the right operand.
• This problem's division truncates toward zero, not floor division — matters for negative intermediate results.

Step-by-Step Analysis

1. Create an empty stack.
2. For each token: if it's a number, push it onto the stack.
3. If it's an operator, pop the top two values (b first, then a), apply the operator as a OP b, and push the result back.
4. After every token is processed, the one value left on the stack is the answer.

Complexity

Time: O(n) — Space: O(n)

Code

def evalRPN(tokens: list[str]) -> int:
    stack = []

    for token in tokens:
        if token not in {"+", "-", "*", "/"}:
            stack.append(int(token))
            continue

        b = stack.pop()
        a = 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))

    return stack[-1]

Code Explanation

How the solution above works, piece by piece.

1. In Reverse Polish Notation every operator comes after its two operands, so a stack is all you need: no parentheses or precedence rules.
2. A number is pushed as an int.
3. An operator pops b first, then a. Order matters for - and /: the expression is a op b.
4. int(a / b) truncates toward zero, which the problem requires. Python's // would round -7 // 2 down to −4 instead of −3.
5. The last value left is the answer. O(n) time, O(n) stack.

Visual Walkthrough

Running it on tokens = ["2", "1", "+", "3", "*"]:

Video Explanation

NeetCode — Evaluate Reverse Polish Notation, LeetCode 150