Evaluate Reverse Polish Notation: stack as the implicit expression tree

Reverse Polish Notation is old — it was the default input method on HP scientific calculators for decades, and most compiler backends still reduce arithmetic expressions to it internally. The reason it persists is that it eliminates operator precedence rules entirely. There are no parentheses to track, no * binding tighter than +. The expression encodes evaluation order by construction.

Given tokens = ["2","1","+","3","*"], the answer is 9. As a sanity check: (2 + 1) * 3. The + comes right after its two operands; the * comes after both of its two operands (one of which is the result of the addition). The order of evaluation is baked into the order of the tokens.

What the constraints actually force

Input length is at most 10,000 tokens. Each token is either one of the four operators ("+", "-", "*", "/") or an integer in [-200, 200]. The problem guarantees the expression is valid and there is no division by zero.

Two things follow from this directly. First, the answer and all intermediate calculations fit in a 32-bit integer — [-200, 200] operands composited through the allowed operations can never overflow int. No overflow protection needed. Second, there is no ambiguity in distinguishing operators from numbers: a number token can start with a minus sign followed by digits (like "-11"), but "-" alone is always the subtraction operator. A simple membership test against the four operator strings is sufficient — no regex, no try/except on int() conversion.

The 10,000 token limit means O(n) is fine and O(n²) would be borderline. But the constraint is almost irrelevant here because there is only one meaningful algorithm for this problem, and it is O(n) by default.

Why a stack, and only a stack

The insight is that RPN is a serialized post-order traversal of an expression tree. ["2","1","+","3","*"] corresponds to this tree:

A post-order traversal visits: left child, right child, root. That is: 2, 1, +, 3, * — exactly the token order. Every number is a leaf; every operator is an internal node that consumes its two children.

When you evaluate a post-order traversal, you need somewhere to hold completed subtree results while waiting for the rest of the expression. That is the stack. Each time you hit an operator, you fold two children into one result and push it back. The stack is the expression tree collapsed into one linear structure — you never build the tree explicitly. The stack is the tree, expressed differently.

There is no brute force alternative. Any approach that tries to scan for operators and resolve them in-place is a reimplementation of a stack with worse bookkeeping. The stack-based algorithm is both the obvious solution and the optimal one. When the problem structure is a post-order sequence, a stack is not a choice — it is the shape of the problem.

The algorithm

One pass. One rule.

• Token is a number -> push it.
• Token is an operator -> pop two, apply the operator, push the result.

At the end, the stack has exactly one element. That is your answer.

The order of pops matters. The first pop gives you the right operand; the second pop gives you the left operand. This only matters for subtraction and division — left - right and right - left are different things — but it is the kind of mistake that fails silently on commutative examples and then breaks on ["4","3","-"].

from typing import List
 
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token in ('+', '-', '*', '/'):
                right = stack.pop()
                left = stack.pop()
                if token == '+':
                    stack.append(left + right)
                elif token == '-':
                    stack.append(left - right)
                elif token == '*':
                    stack.append(left * right)
                elif token == '/':
                    stack.append(int(left / right))
            else:
                stack.append(int(token))
        return stack[0]

public class Solution {
    public int EvalRPN(string[] tokens) {
        var stack = new Stack<int>();
        foreach (var token in tokens) {
            if (token is "+" or "-" or "*" or "/") {
                int right = stack.Pop();
                int left = stack.Pop();
                int result = token switch {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    "/" => left / right,
                    _ => throw new InvalidOperationException()
                };
                stack.Push(result);
            } else {
                stack.Push(int.Parse(token));
            }
        }
        return stack.Peek();
    }
}

Both are O(n) time and O(n) space. The stack holds at most roughly half the tokens at any point — the worst case is when every number appears before every operator, giving you n/2 elements in the stack before the operators start firing. You cannot do better than O(n) time because you must read every token at least once.

Complexity

No other approach exists. Any reimplementation of "walk through tokens and resolve operators" is just a disguised stack.

The Python division trap

This is the only real gotcha in the problem, and it bites Python specifically.

Python's // operator is floor division: it rounds toward negative infinity. -7 // 2 gives -4 in Python, not -3. The problem statement requires truncation toward zero, which is what integer division does in C, C++, Java, and C# by default.

The fix is int(left / right). int() on a float truncates toward zero unconditionally. int(-7 / 2) gives -3. This is not a Python curiosity — it is the IEEE 754 truncation direction, and it is what you want here.

You could also write math.trunc(left / right), which is more explicit. I use int() because it is shorter and the intent is clear in context. Either works. Just do not use //.

C# does truncation toward zero natively for integer division, so there is nothing special to do there.

A step-by-step trace through the simple example

tokens = ["2","1","+","3","*"]

token "2":  push 2              stack = [2]
token "1":  push 1              stack = [2, 1]
token "+":  right=1, left=2
            2 + 1 = 3, push 3   stack = [3]
token "3":  push 3              stack = [3, 3]
token "*":  right=3, left=3
            3 * 3 = 9, push 9   stack = [9]

return stack[0] = 9

The + fires and collapses both of its operands into a single 3. That 3 stays on the stack until * needs it as its left operand alongside the next 3. The stack mirrors the tree: it held the pending + subtree result (3) while waiting for the right child of * to arrive.

The second example, ["4","13","5","/","+"], corresponds to 4 + (13 / 5). Division fires first, giving int(13/5) = 2 (truncation toward zero). Then addition: 4 + 2 = 6.

A trace through the hard example

tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

This one looks intimidating. Walk it step by step:

token "10":  push 10                           stack = [10]
token "6":   push 6                            stack = [10, 6]
token "9":   push 9                            stack = [10, 6, 9]
token "3":   push 3                            stack = [10, 6, 9, 3]
token "+":   right=3, left=9, 9+3=12          stack = [10, 6, 12]
token "-11": push -11                          stack = [10, 6, 12, -11]
token "*":   right=-11, left=12, 12*-11=-132  stack = [10, 6, -132]
token "/":   right=-132, left=6, int(6/-132)=0  stack = [10, 0]
token "*":   right=0, left=10, 10*0=0         stack = [0]
token "17":  push 17                           stack = [0, 17]
token "+":   right=17, left=0, 0+17=17        stack = [17]
token "5":   push 5                            stack = [17, 5]
token "+":   right=5, left=17, 17+5=22        stack = [22]

return 22

The key moment is int(6 / -132). 6 / -132 is approximately -0.0454, and int() truncates that to 0 — not -1. Floor division would give -1 here. That zero then wipes out everything multiplied against 10, which is why most of the expression collapses to nothing before the +17 and +5 at the end.

Edge cases worth knowing

Single token ["42"]. The number pushes onto the stack, no operator ever fires, and stack[0] returns it directly. The algorithm handles this without any special case — there is no minimum token count before the loop works correctly.

Negative number tokens like "-11". They start with a minus sign but are not the "-" operator. The membership check token in ('+', '-', '*', '/') correctly identifies "-11" as a non-operator (it is five characters, not one), so it falls through to int(token) which parses the negative integer correctly. This is why a set membership test beats a try: int(token) approach — the negative number case would accidentally parse as int with either method, but the operator-set check is cleaner and explicit.

Operand order for subtraction. ["4","3","-"] should give 1, not -1. Always: first pop is right, second pop is left. This is the mistake most people make in a contest because the pop order feels backward.

Division with negative operands. ["6","-132","/"] must give 0, not -1. Python's // fails this; int(left / right) gets it right. Worth testing explicitly before submitting.

Pattern recognition

Reach for a stack whenever you see:

• "evaluate expression" with a non-standard format
• operators that resolve the two most recently seen operands
• parentheses or grouping where earlier context needs to "wait"
• any serial structure where a LIFO ordering matches the evaluation order

RPN is the textbook example of all four. If you see "postfix expression" or "Reverse Polish Notation" in a problem statement, the stack solution is immediate. The same mental model applies to Valid Parentheses, Basic Calculator, and any grammar that has a post-order evaluation structure. I'd ship this exact code to production — it is already the simplest correct implementation of the evaluation rule, and there is no cleverer version to find.

Related problems

Valid Parentheses (20) — the simplest stack problem. Every opener pushes; every closer checks the top and pops. If you have done it, you have already used the same mental model: the stack tracks context that needs resolution, and an event (operator / closer) resolves the most recent unresolved item.

Basic Calculator (224) — the inverse direction. Given a standard infix expression with parentheses and +/-, evaluate it. One approach shunts the infix tokens into RPN using the operator-precedence shunting-yard algorithm, then evaluates the result with exactly the algorithm above. The stack appears in both phases.

Basic Calculator II (227) — infix without parentheses, but with all four operators. Precedence matters here (* before +), and the stack is used to defer lower-precedence operators while higher-precedence ones resolve first. The twist: you can no longer process each operator the moment you see it.

Basic Calculator III (772) — combines both: parentheses and full operator precedence. The hardest of the series. RPN evaluation is still the core, but the shunting-yard conversion is non-trivial. If you can do 150 cleanly and explain the post-order structure, you have the foundation for all three.