Leetcode - 150. Evaluate Reverse Polish Notation

Medium

Dec 22, 2025

#stack

#math

150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

1 <= tokens.length <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Constraints:

Notes

Intuition

Reverse Polish Notation places operators after their operands. A stack naturally handles this—operands accumulate until an operator consumes them, and intermediate results stay on the stack for future operations.

Implementation

Iterate through tokens. If it's a number, push to stack. If it's an operator, pop the top two values, apply the operation, and push the result back. The final answer is the single value remaining on the stack.

Edge-cases

Python's integer division // rounds toward negative infinity, not toward zero. Use int(b / a) for truncation toward zero. Also remember operand order matters for subtraction and division—the second popped value is the left operand (b - a, int(b / a)).

Time: O(n) — single pass through tokens
Space: O(n) — stack holds intermediate values

Complexity

Solution

from typing import List

class Solution:
    def evaluate(self, operator: str, a: int, b: int) -> int:
        if operator == "+":
            return a + b
        if operator == "*":
            return a * b
        if operator == "-":
            return b - a
        if operator == "/":
            return int(b / a)
        
        raise ValueError(f"invalid operator: '{operator}'")

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token == "+" or token == "-" or token == "*" or token == "/":
                a = stack.pop()
                b = stack.pop()
                stack.append(self.evaluate(token, a, b))
            else:
                stack.append(int(token))
        return stack[-1]
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()