150. Evaluate Reverse Polish Notation

Problem¶

Given an RPN expression as a list of strings, evaluate it and return the integer result, where division truncates toward zero.

Example: ["4","13","5","/","+"] -> 6
Meaning: 4 + (13 / 5) = 4 + 2 = 6

Key trick¶

Use a stack:

Push numbers.
On an operator, pop right then left, compute left op right, and push back.
For division, truncate toward zero, not floor.

Trap¶

Common mistakes:

Popping in the wrong order for - and /.
Using Python // directly for negative division, because it floors instead of truncating toward zero.
Forgetting that negative numbers like "-11" are operands, not the - operator.

Why is it interesting?¶

It tests stack simulation, careful operand order, and language-specific division behavior in a very small problem.

Python solution¶

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:
                # Python // floors, but the problem wants truncation toward zero.
                stack.append(int(left / right))

        return stack[-1]

Time: \(O(n)\)
Space: \(O(n)\)

Comment on my solution¶

Your solution is correct and interview-good.

Good:
- Clear stack approach.
- Correct left/right operand order.
- Correct truncation toward zero.
Simplification:
- The division can be written more simply as:

stack.append(int(left / right))

Minor style note:
- return stack[-1] is a bit more idiomatic than stack[0], though both work here.

# WORKS
class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        # ["2","1","+","3","*"] -> ((2 + 1) * 3)
        # ["4","13","5","/","+"] -> (4 + (13 / 5))

        operators = {"+", "-", "*", "/"}
        stack = []

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

            operator = token
            right = stack.pop()
            left = stack.pop()
            if operator == "+":
                stack.append(left + right)
            elif operator == "-":
                stack.append(left - right)
            elif operator == "*":
                stack.append(left * right)
            else:
                sign = -1 if left * right < 0 else 1
                right = abs(right)
                left = abs(left)
                stack.append(sign * (left // right))

        return stack[0]