LeetCode 150: Evaluate Reverse Polish Notation

Problem Restatement

We are given an array of strings representing an arithmetic expression in Reverse Polish Notation (RPN).

Evaluate the expression and return the integer result.

Valid operators are:

Each operand may be an integer or another expression.

Division truncates toward zero.

LeetCode guarantees that:

• the input is always valid
• there is no division by zero
• the final answer fits in a 32-bit signed integer

(leetcode.com)

What Is Reverse Polish Notation?

Normal arithmetic writes operators between operands:

2 + 3

Reverse Polish Notation writes the operator after the operands:

2 3 +

More examples:

RPN removes the need for parentheses because the order of evaluation is encoded directly in the token order.

Examples

Example 1:

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

Evaluation:

2 + 1 = 3
3 * 3 = 9

Output:

9

Example 2:

tokens = ["4", "13", "5", "/", "+"]

Evaluation:

13 / 5 = 2
4 + 2 = 6

Output:

6

Example 3:

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

Output:

22

Input and Output

Function shape:

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        ...

Key Insight

RPN evaluation naturally fits a stack.

Why?

When we see a number:

store it for later

When we see an operator:

combine the most recent operands

The “most recent unresolved values” behavior is exactly what a stack provides.

Stack Process

For each token:

At the end, the stack contains one value:

the final answer

Important Operand Order

Suppose the stack contains:

[5, 2]

and the operator is:

-

We pop:

right = 2
left = 5

Then compute:

5 - 2

not:

2 - 5

So the order matters.

The second popped value is the left operand.

Example Walkthrough

Consider:

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

Start:

stack = []

Read "2":

stack = [2]

Read "1":

stack = [2, 1]

Read "+":

pop 1
pop 2
compute 2 + 1 = 3
push 3

Now:

stack = [3]

Read "3":

stack = [3, 3]

Read "*":

pop 3
pop 3
compute 3 * 3 = 9
push 9

Final stack:

[9]

Answer:

9

Division Behavior

LeetCode requires:

truncate toward zero

This matters for negative division.

Example:

-7 / 2

Mathematical result:

-3.5

Truncate toward zero:

-3

In Python:

-7 // 2

gives:

-4

because floor division rounds downward.

So we must use:

int(a / b)

instead.

Algorithm

Create an empty stack.

For each token:

1. If it is a number:
   • push it onto the stack
2. Otherwise:
   • pop right operand
   • pop left operand
   • apply operator
   • push result

At the end:

stack[0]

is the answer.

Correctness

The stack always contains the values of fully evaluated subexpressions whose operators have not yet been applied to later expressions.

When a number token appears, pushing it onto the stack correctly stores it as a new operand.

When an operator appears, Reverse Polish Notation guarantees that the two most recent unresolved values are exactly the operands for that operator. The algorithm pops those two operands in the correct order, evaluates the operation, and pushes the resulting subexpression value back onto the stack.

Thus, after processing each token, the stack correctly represents all partially evaluated expressions up to that point.

Since the expression is valid, processing all tokens leaves exactly one value on the stack, which is the value of the entire expression.

Therefore, the algorithm correctly evaluates the Reverse Polish Notation expression.

Complexity

Let:

Implementation

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []

        for token in tokens:
            if token not in {"+", "-", "*", "/"}:
                stack.append(int(token))
                continue

            right = stack.pop()
            left = stack.pop()

            if token == "+":
                stack.append(left + right)

            elif token == "-":
                stack.append(left - right)

            elif token == "*":
                stack.append(left * right)

            else:
                stack.append(int(left / right))

        return stack[0]

Code Explanation

The stack stores intermediate values:

stack = []

If the token is a number:

stack.append(int(token))

push it onto the stack.

Otherwise, it is an operator.

Pop operands:

right = stack.pop()
left = stack.pop()

Order matters.

Apply the operator:

left op right

For division:

int(left / right)

ensures truncation toward zero.

Finally:

return stack[0]

returns the evaluated expression.

Alternative Operator Table

We can avoid long if chains by using a dictionary of functions.

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []

        operators = {
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: int(a / b),
        }

        for token in tokens:
            if token not in operators:
                stack.append(int(token))
                continue

            right = stack.pop()
            left = stack.pop()

            stack.append(
                operators[token](left, right)
            )

        return stack[0]

This version is shorter and easier to extend.

Testing

def run_tests():
    s = Solution()

    assert s.evalRPN([
        "2", "1", "+", "3", "*"
    ]) == 9

    assert s.evalRPN([
        "4", "13", "5", "/", "+"
    ]) == 6

    assert s.evalRPN([
        "10", "6", "9", "3", "+", "-11",
        "*", "/", "*", "17", "+", "5", "+"
    ]) == 22

    assert s.evalRPN([
        "3", "-4", "+"
    ]) == -1

    assert s.evalRPN([
        "-7", "2", "/"
    ]) == -3

    assert s.evalRPN([
        "5"
    ]) == 5

    print("all tests passed")

run_tests()

Test meaning: