150. Evaluate Reverse Polish Notation

150

MediumStack and Expression ProcessingStackOperand stack for postfix evaluation

Evaluate Reverse Polish Notation

Evaluate an arithmetic expression given in Reverse Polish (postfix) notation. tokens is a list where each entry is an integer or one of the operators '+', '-', '*', '/'. Each operator applies to the two most recent operands. Division truncates toward zero. Return the integer result.

Open official problem prompt ↗

In plain English

Compute the numeric value of an expression already written in postfix form.

Picture it like this

An old RPN calculator: you key in numbers that stack up, and pressing an operator instantly combines the last two entries into one.

Example

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Why: It encodes (2 + 1) * 3: '+' combines 2 and 1 into 3, then '*' multiplies 3 by 3 to get 9.

Constraints

1 <= tokens.length <= 10^4Each token is '+', '-', '*', '/' or an integer in [-200, 200]The expression is always a valid RPN expressionDivision between two integers truncates toward zero

Pattern lesson

See the pattern, then code

Operand stack for postfix evaluation

↗

Stack and Expression Processing

Nested structures, matching delimiters, undo behavior, or unresolved operations.. In postfix, when you meet an operator its two operands are already the top two items on the stack, so you pop them, combine, and push the result back.

New words, made simpleKnow these before the algorithm

Reverse Polish notation: Postfix form where the operator comes after its two operands, needing no parentheses.
Operand: A numeric value that an operator combines.
Truncate toward zero: Drop the fractional part toward 0, so 7/-2 becomes -3, not -4.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Convert to infix and parse

Extra conversion machinery for no benefit; postfix is already evaluation-ready.

Rebuild a fully parenthesized infix expression and evaluate that.

Time O(n)Space O(n)

Best choiceSingle operand stack

Direct, linear, and mirrors how postfix is defined.

Push numbers, and on each operator pop two, combine, and push the result.

Time O(n)Space O(n)

The rule we keep true

Invariant

The stack always holds the results of every fully evaluated sub-expression seen so far, in left-to-right order.

Why this is correct

Reasoning

A valid postfix expression guarantees that when an operator appears, its two operands are the two most recently produced values, which are exactly the top two stack entries. Popping them in order (second popped is the left operand) and pushing the result reduces the expression one operation at a time until a single value remains.

The algorithm in three movesSay these aloud before coding

1Scan tokens left to right

push 2, push 1 -> [2,1]

2Push every integer token

'+': pop 1,2 -> push 3 -> [3]

3On an operator, pop the top two (second popped is the left operand)

push 3 -> [3,3]

4Apply the operator with truncation toward zero for division

'*': pop 3,3 -> push 9 -> [9]

5Push the result; the final stack value is the answer

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read'2'

2 · AskNumber or operator?

3 · Update statestack = [2]

4 · ResultPush 2

Key takeaway

Operators consume the top two operands and push their result back onto the stack.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Pop operands in order
b is the right operand (popped first), a is the left operand; order matters for '-' and '/'.
2
Lines 9-16Apply the operator
Compute a op b and push the single result back onto the stack.
3
Lines 16Truncating division
int(a / b) truncates toward zero, matching the problem's rule, unlike Python's // which floors.
4
Lines 19Return the result
A valid expression leaves exactly one value, the answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single number token returns that number
Negative results from subtraction
Division that must truncate toward zero, e.g. int(-7 / 2) = -3
Negative operands like '-11'

Common beginner mistakes

Swapping operand order so a - b or a / b is computed backwards
Using Python // which floors negatives instead of int(a / b) which truncates toward zero
Forgetting to convert numeric tokens from string to int

Check your understanding

Why use int(a / b) instead of a // b?

PyPython 3 · solution.py

Optimal

1class Solution:2    def evalRPN(self, tokens: list[str]) -> int:3        stack: list[int] = []4        ops = {'+', '-', '*', '/'}5        for t in tokens:6            if t in ops:7                b = stack.pop()8                a = stack.pop()9                if t == '+':10                    stack.append(a + b)11                elif t == '-':12                    stack.append(a - b)13                elif t == '*':14                    stack.append(a * b)15                else:16                    stack.append(int(a / b))17            else:18                stack.append(int(t))19        return stack[0]

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonLinkedInGoogleMicrosoft

Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Stack and Expression Processing