Evaluate Reverse Polish Notation: Stack Calculator

Evaluate Reverse Polish Notation is LeetCode 150, rated Medium, and it is one of the cleanest stack problems you will encounter. If you have ever used an old HP calculator or programmed in Forth, you already know how reverse polish notation works. For everyone else, it clicks fast once you see it.

The technique behind this problem, using a stack to evaluate expressions token by token, is a building block that shows up in calculators, compilers, and a bunch of other LeetCode problems. Let's break it down.

The problem

You are given an array of strings tokens that represents an arithmetic expression in reverse polish notation (also called postfix notation). Evaluate the expression and return the result as an integer.

The rules:

• Valid operators are +, -, *, and /.
• Each operand can be an integer or another expression.
• Division between two integers truncates toward zero.
• The input is guaranteed to be a valid RPN expression.

Examples:

• ["2", "1", "+", "3", "*"] evaluates to 9. That is (2 + 1) * 3.
• ["4", "13", "5", "/", "+"] evaluates to 6. That is 4 + (13 / 5), and 13 / 5 truncates to 2.
• ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] evaluates to 22.

In normal (infix) notation, you need parentheses to specify order of operations. Reverse polish notation eliminates that entirely. The position of the operator tells you exactly which operands it applies to.

Why a stack is the right tool

Think about what happens when you read RPN tokens left to right. When you see a number, you cannot do anything with it yet because you do not know which operator will use it. So you save it for later. When you finally see an operator, you need the two most recently seen operands.

"Most recently seen" is the key phrase. That is a last-in-first-out pattern, which means a stack.

The algorithm is almost embarrassingly simple:

1. Walk through the tokens left to right.
2. If the token is a number, push it onto the stack.
3. If the token is an operator, pop two numbers off the stack, apply the operator, and push the result back.
4. When you are done, the single number left on the stack is the answer.

That is it. No recursion, no precedence rules, no parentheses to deal with. The stack handles everything.

Visual walkthrough

Let's trace through ["2", "1", "+", "3", "*"] step by step. The expression in infix notation is (2 + 1) * 3 = 9. Watch how the stack grows when we push numbers and shrinks when operators consume them.

Notice the pattern: every operator reduces the stack size by one (pop two, push one result). At the end, exactly one value remains. That is our answer.

The code

Here is the Python solution for LeetCode 150, Evaluate Reverse Polish Notation:

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

    for token in tokens:
        if token in "+-*/":
            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:
                # Truncate toward zero
                stack.append(int(a / b))
        else:
            stack.append(int(token))

    return stack[0]

Let's walk through the important details:

• Pop order matters. When we pop two values, the first pop gives us b (the right operand) and the second gives us a (the left operand). For + and * the order does not matter, but for - and / it absolutely does. ["5", "3", "-"] means 5 - 3 = 2, not 3 - 5 = -2. The second-to-top element is the left operand.
• Truncation toward zero. Python's // operator floors toward negative infinity, but LeetCode wants truncation toward zero. int(a / b) handles this correctly. -7 / 2 gives -3.5, and int(-3.5) gives -3. If you used //, you would get -4, which is wrong.
• Checking for operators. The token in "+-*/" check works because each operator is a single character. Numbers like "13" or "-11" are multi-character strings, so they will never match.
• Return value. After processing all tokens, the stack has exactly one element. Return stack[0] (or stack.pop(), either works).

Complexity analysis

Time: O(n). We process each token exactly once. Each token triggers at most one push and/or one pop, all O(1) operations. Total work is proportional to the number of tokens.

Space: O(n). In the worst case, we could have a long sequence of numbers before any operators (like ["1", "2", "3", "4", "+", "+", "+"]), filling the stack to about n/2 elements. That is still O(n).

You cannot do better than O(n) time because you have to read every token at least once. The solution is optimal.

Edge cases to watch for

These come up in interviews and edge-case tests:

• Single number. ["42"] should return 42. The loop pushes it, no operators fire, and stack[0] returns it. Works fine.
• Negative numbers. Tokens like "-11" are valid. int("-11") correctly gives -11 in Python.
• Division truncation with negatives. ["7", "-3", "/"] should give -2 (truncate toward zero), not -3 (floor). This is the most common failure.
• Large expressions. The input can have up to 10,000 tokens. The stack-based approach handles this easily since everything is O(n).

The building blocks

This problem is built on one core building block:

Stack-based parsing

The pattern of walking through a sequence of tokens, pushing data onto a stack when you encounter values, and popping when you encounter operators or delimiters. The stack acts as a temporary storage area that automatically handles nesting and ordering.

In Evaluate Reverse Polish Notation, the "data" is numbers and the "operators" are arithmetic operators. But the same push-data, pop-on-trigger structure drives:

• Basic Calculator and Basic Calculator II: parsing infix expressions with precedence and parentheses by converting to RPN or using operator stacks
• Decode String (3[a2[bc]]): push the current string when you see [, pop and combine when you see ]
• Valid Parentheses: push openers, pop and validate when you see closers
• Min Stack: push with auxiliary tracking, pop with synchronized cleanup

Every time you see a problem where you process tokens left to right and need to "remember" recent values for a later operation, think stack. The stack calculator in this problem is one of the purest examples of that pattern.

Common mistakes

A few things that trip people up:

1. Swapping operand order. If you write a = stack.pop(); b = stack.pop() and then compute a - b, you get the operands backwards. The first pop is the right operand, the second pop is the left operand.

2. Using Python // for division. This gives wrong results for negative numbers. -7 // 2 is -4 in Python, but the correct answer is -3. Use int(a / b) instead.

3. Matching operators with == chains when in works. Not a correctness issue, but token in "+-*/" is cleaner than four separate if checks for identifying operators. Just be careful: this works because all operators are single characters.

4. Forgetting to convert tokens to integers. The input is a list of strings. If you push "2" instead of int("2"), your arithmetic will fail or produce string concatenation.

From understanding to recall

The RPN evaluator is short and sweet. The core loop is maybe 15 lines. But under interview pressure, small details trip people up. Which operand is a and which is b? Do I use // or int(a / b)? Do I push token or int(token)?

These are not conceptual gaps. They are recall gaps. You understand the algorithm perfectly right now, but producing the code from scratch in three weeks is a different skill.

Spaced repetition bridges that gap. You type the stack calculator from memory at increasing intervals. Each repetition reinforces the pop order, the division truncation trick, and the operator check. After a few cycles, the whole thing is automatic. You do not freeze on the details in an interview because you have already written this code a dozen times.

Related posts

• Valid Parentheses - The classic stack-based parsing problem, using the same push/pop pattern for bracket matching
• Min Stack - A design problem that extends the stack with O(1) minimum tracking, using synchronized auxiliary state

CodeBricks breaks the reverse polish notation stack calculator into its reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 150 or any expression evaluation problem shows up in an interview, the code flows without hesitation.