Evaluate 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 known as postfix notation. Evaluate the expression and return the result as an integer.

In RPN, operators follow their operands. "3 4 +" means 3 + 4 = 7. "4 13 5 / +" means 13 / 5 = 2 (truncated), then 4 + 2 = 6. The expression is guaranteed to be valid — no division by zero, and there is always exactly one result.

RPN eliminates the need for parentheses and operator precedence rules. A stack naturally evaluates it: numbers are pushed, and operators consume the top two stack elements. This is how calculators and compilers process expressions internally.

Initialize an empty stack. Process tokens left to right. If the token is a number, push it onto the stack. If the token is an operator (+, -, *, /), pop the top two elements: the first pop is the right operand (b), the second pop is the left operand (a). Compute a op b and push the result.

The order of popping matters: since a stack is LIFO, the second operand (right) is on top. For subtraction and division, the order is significant: a - b is not b - a. Always pop b first, then a, and compute a op b.

After processing all tokens, the stack contains exactly one element — the final result. Return it. If the stack has more or fewer elements, the expression was invalid (but the problem guarantees validity).

The problem specifies that division truncates toward zero, not toward negative infinity (which is what Python's // operator does). For positive results, both are the same: 7 / 2 = 3. For negative results, they differ: -7 / 2 should be -3 (truncate toward zero), not -4 (floor).

In Python, use int(a / b) instead of a // b. The float division a / b gives -3.5, and int() truncates toward zero giving -3. In Java, the / operator on integers already truncates toward zero, so no special handling is needed.

This subtlety is a common source of wrong answers in Python. Always test with negative numbers: -6 / 132 should be 0, and 6 / -132 should also be 0. Python's // would give -1 for both, which is incorrect.

Consider tokens = ["2","1","+","3","*"]. Stack: push 2 → [2]. Push 1 → [2, 1]. Token "+": pop 1 (b) and 2 (a), compute 2+1=3, push → [3]. Push 3 → [3, 3]. Token "*": pop 3 (b) and 3 (a), compute 3*3=9, push → [9]. Return 9.

Consider tokens = ["4","13","5","/","+"]. Push 4 → [4]. Push 13 → [4, 13]. Push 5 → [4, 13, 5]. Token "/": pop 5 (b) and 13 (a), compute 13/5=2 (truncated), push → [4, 2]. Token "+": pop 2 and 4, compute 4+2=6, push → [6]. Return 6.

Consider tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]. This longer expression evaluates to 22. Each operator consumes two operands and produces one result, gradually reducing the stack until one value remains.

Python: stack = []. For token in tokens: if token in "+-*/": b, a = stack.pop(), stack.pop(). If token == "+": stack.append(a+b). Elif "-": stack.append(a-b). Elif "*": stack.append(a*b). Else: stack.append(int(a/b)). Else: stack.append(int(token)). Return stack[0].

A cleaner Python approach uses a dictionary of lambda functions: ops = {"+": lambda a,b: a+b, "-": lambda a,b: a-b, "*": lambda a,b: a*b, "/": lambda a,b: int(a/b)}. If token in ops: b, a = stack.pop(), stack.pop(); stack.append(ops[token](a, b)).

Java: use a Deque<Integer> stack. Check if token is an operator with a switch statement. For division, Java's / already truncates toward zero. Parse numbers with Integer.parseInt(). Return stack.pop().

Time complexity is O(n) where n is the number of tokens. Each token is processed exactly once with O(1) work (push, pop, or arithmetic operation). No nested loops or repeated scanning.

Space complexity is O(n) for the stack. In the worst case (all operands first, then operators), the stack holds n/2 + 1 elements. In the best case (alternating operands and operators), the stack stays small.

This is optimal — we must read every token at least once, and the stack-based evaluation processes each token in constant time. No more efficient algorithm exists for general RPN evaluation.

Basic Calculator (LeetCode 224) and Basic Calculator II (LeetCode 227) evaluate infix expressions with parentheses and operator precedence. They are harder because they require parsing precedence, which RPN eliminates.

Valid Parentheses (LeetCode 20) uses a stack for matching brackets — the simplest stack problem. RPN evaluation adds arithmetic on top of the same stack mechanics. Together they build stack proficiency.

Decode String (LeetCode 394) uses a stack to handle nested encoded strings like "3[a2[c]]". The push-on-open, pop-on-close pattern is analogous to push-on-operand, pop-on-operator in RPN evaluation.