Reverse Polish Notation LeetCode 150

LeetCode 150 — Evaluate Reverse Polish Notation — gives you an array of string tokens representing an arithmetic expression in Reverse Polish Notation (RPN), also called postfix notation. Your task is to evaluate the expression and return the result as an integer. The valid operators are +, -, *, and /. Each operand is guaranteed to be a valid integer.

Division between two integers must truncate toward zero, meaning -7 / 2 = -3 (not -4 as Python's floor division would give). The input is always a valid RPN expression, so you never need to handle malformed input or division by zero. The result and all intermediate values fit in a 32-bit signed integer.

LeetCode 150 is rated Medium and appears in the NeetCode 150 stack section. It is a direct, clean application of the postfix evaluation algorithm using a single stack. Understanding this problem builds intuition for expression parsing, compiler design, and more advanced stack-based problems like Basic Calculator.

Reverse Polish Notation is a mathematical notation where operands come before their operator. Instead of writing 2 + 3, you write 2 3 +. Instead of (2 + 1) * 3, you write 2 1 + 3 *. The expression is evaluated left to right: when you see an operator, the two most recently seen values are its operands. No parentheses are ever needed because the order of operations is already encoded in the token sequence.

RPN was popularized by Hewlett-Packard calculators in the 1970s and is used in stack-oriented virtual machines and postfix-stage compilers. The reason it maps so naturally to a stack is that operands appear in the order they are needed, and operators always consume exactly the two values on top of the stack. The result is pushed back and becomes available for the next operator.

Parsing "2 1 + 3 *": push 2, push 1, see + → pop 1 and 2, compute 2+1=3, push 3, push 3 (the literal), see * → pop 3 and 3, compute 3*3=9, push 9. Stack is now [9] — that is the answer. The nesting of (2+1)*3 is represented without parentheses purely through token order.

The algorithm iterates through tokens from left to right. For each token, it checks whether the token is a number or an operator. If it is a number (including negative numbers), it converts the string to an integer and pushes it onto the stack. If it is one of the four operators, it pops two values from the stack, applies the operator, and pushes the integer result back.

At the end of the token list, exactly one value remains on the stack. That value is the result of the entire expression. The stack never grows larger than the number of operands in the expression, and every token is processed exactly once, giving O(n) time complexity where n is the number of tokens. Stack space is also O(n) in the worst case (an expression of all numbers followed by all operators).

To check whether a token is a number, you can check if the last character is a digit (handling negative numbers like "-3" which start with a minus sign). Alternatively, use a try/except (Python) or attempt Integer.parseInt (Java) and treat a ValueError or NumberFormatException as an operator token. Most solutions use a set of operator strings {"+" , "-", "*", "/"} and treat everything not in the set as a number.

For addition and multiplication, operand order does not matter: a + b = b + a and a * b = b * a. But for subtraction and division, order is critical. In RPN, "4 2 -" means 4 minus 2 = 2, not 2 minus 4 = -2. When you pop from the stack, the top is the right operand and the second is the left operand.

The rule: pop b first (it was pushed last, so it is the right operand), then pop a (it was pushed earlier, so it is the left operand). Compute a op b. For "4 2 -": push 4, push 2, see - → pop b=2, pop a=4, compute 4-2=2, push 2. For "4 2 /": pop b=2, pop a=4, compute 4/2=2, push 2. If you accidentally compute b op a instead, subtraction and division will give wrong answers.

This is the single most common bug in first-time RPN implementations. A simple mnemonic: the element you pop second (deeper in the stack) is the one written first in the original expression. In "4 2 -", 4 was written first and pushed first, so it ends up deeper — and is therefore the left operand. The element pushed last (2) is on top and is the right operand.

The problem specifies that division truncates toward zero. This means the result is rounded toward zero (positive results round down, negative results round up). For positive dividends and divisors this is standard integer division: 7 / 2 = 3. For negative numbers it differs from Python's default floor division: in Python, -7 // 2 = -4 (floor toward negative infinity), but the problem expects -7 / 2 = -3 (truncation toward zero).

In Python, use int(a / b) instead of a // b. The expression int(a / b) performs true float division and then truncates toward zero with int(), which is the correct behavior. For example: int(-7 / 2) = int(-3.5) = -3. Using a // b gives -4 in Python, which is wrong for negative operands.

In Java, the / operator on integers already truncates toward zero by default — int division in Java is truncation, not floor. So -7 / 2 = -3 in Java without any special handling. This difference makes Python slightly more tricky for this problem. Always test your solution with the example ["10","6","9","3","+","-11","*","/","*","17","+","5","+""] which exercises complex nested operations.

Python solution: def evalRPN(tokens): stack = []; ops = {"+": lambda a,b: a+b, "-": lambda a,b: a-b, "*": lambda a,b: a*b, "/": lambda a,b: int(a/b)}; [stack.append(ops[t](stack.pop(), stack.pop())[::-1]) if t in ops else stack.append(int(t)) for t in tokens]; return stack[0]. More readably: use a dict mapping operator strings to lambda functions. For each token, if it is in ops dict, pop b then a (note: stack.pop() gives b first, then a — pass as ops[t](a, b) after assigning b=stack.pop(); a=stack.pop()), else push int(token). Time O(n), space O(n).

Java solution: public int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String t : tokens) { if (t.equals("+")) { int b=stack.pop(), a=stack.pop(); stack.push(a+b); } else if (t.equals("-")) { int b=stack.pop(), a=stack.pop(); stack.push(a-b); } else if (t.equals("*")) { int b=stack.pop(), a=stack.pop(); stack.push(a*b); } else if (t.equals("/")) { int b=stack.pop(), a=stack.pop(); stack.push(a/b); } else { stack.push(Integer.parseInt(t)); } } return stack.pop(); }. Java's a/b already truncates toward zero.

Both solutions are O(n) time and O(n) space where n is the number of tokens. The stack holds at most ceil(n/2) values at any time (for an expression of all numbers at the start). The Python lambda dict is elegant for operator dispatch; the Java if-else chain is explicit and clear. Either approach passes all LeetCode 150 test cases. The key correctness details are: pop b before a, use int(a/b) in Python for division, handle negative number strings (they contain a digit as the last character).

Basic Calculator (LeetCode 224) and Basic Calculator II (LeetCode 227) are the natural extensions of RPN evaluation. They require parsing infix expressions with parentheses (224) or operator precedence (227) and converting them to an evaluatable form. The stack-based evaluation skill from LeetCode 150 directly applies: once you convert infix to postfix (RPN), evaluation is identical to this problem.

Valid Parentheses (LeetCode 20) uses a stack to match opening and closing brackets — a simpler version of the expression parsing pattern. Daily Temperatures (LeetCode 739) and Online Stock Span (LeetCode 901) use monotonic stacks for range queries. Min Stack (LeetCode 155) augments a stack with O(1) minimum tracking. All of these share the same mental model: a stack as a way to defer decisions or maintain history for recent elements.

The expression evaluation family — LeetCode 150, 224, 227, 394 (Decode String), and 856 (Score of Parentheses) — all use stacks to handle nested or sequential structure. LeetCode 150 is the cleanest entry point because the input is already in postfix form. Mastering it gives you the foundation to tackle the harder infix parsing problems in this family, where the challenge is not evaluation but expression transformation.