Evaluate Reverse Polish Notation

35 min · evalRPN()

A calculator doesn't need parentheses when every operator arrives after the values it uses. That ordering is the whole trick behind this problem.

Reverse Polish Notation (RPN) is an expression format where an operator comes after its two operands. You're given one valid RPN expression as an array of string tokens. Each token is an integer or one of +, -, *, and /.

Evaluate the expression and return its integer result.

A few ground rules:

Each operator consumes the two most recent unfinished values: the earlier value is the left operand, and the later value is the right operand.
Integer division truncates toward zero, so both 7 / -3 and -7 / 3 become -2.
The expression is always valid, and division by zero never occurs.

Constraints

1 <= tokens.length <= 10_000
Each token is +, -, *, /, or an integer in [-10_000, 10_000].
Every intermediate value and the final result fit a signed 32-bit integer.
The tokens form a valid RPN expression, and no division uses zero as its divisor.

Hints

Reduce what is ready

In a valid RPN expression, the first operator you encounter has two completed values immediately before it. Replace those three tokens with their result and repeat.

Keep unfinished values

A stack is a last-in, first-out collection. Push number tokens. When an operator arrives, pop the right operand first, then the left operand, and push their result.

Subtraction exposes the order

For the tokens 8 3 -, the two pops produce right = 3 and left = 8. Reversing them computes 3 - 8, which is a different expression.

Follow-up

Could you evaluate the expression as a stream, without storing tokens you've already processed?

Visible cases

Examples

Example 1

ready

Input: tokens = [ "2", "1", "+", "3", "*" ]
Expected: 9
Why: 2 + 1 becomes 3, then 3 × 3 becomes 9

Example 2

ready

Input: tokens = [ "4", "13", "5", "/", "+" ]
Expected: 6
Why: 13 / 5 truncates to 2, then 4 + 2 = 6

Example 3

ready

Input: tokens = [ "7", "-3", "/" ]
Expected: -2
Why: -2.333... truncates toward zero to -2

Interview signal

Asked at

AmazonGoogleLinkedIn

Repeated reduction

The first operator in an RPN expression always has two completed number tokens directly before it. Find that operator, replace the three-token group with its result, and keep going until one number remains.

def eval_rpn(tokens: list[str]) -> int:
    expression: list[int | str] = [
        token if token in "+-*/" else int(token)
        for token in tokens
    ]
 
    while len(expression) > 1:
        for i, token in enumerate(expression):
            if isinstance(token, str):
                left = expression[i - 2]
                right = expression[i - 1]
                assert isinstance(left, int) and isinstance(right, int)
 
                if token == "+":
                    value = left + right
                elif token == "-":
                    value = left - right
                elif token == "*":
                    value = left * right
                else:
                    value = abs(left) // abs(right)
                    if (left < 0) != (right < 0):
                        value = -value
 
                expression[i - 2:i + 1] = [value]
                break
 
    return int(expression[0])

Searching for operators and shifting the remaining list after each replacement repeats work that the token order already settled.

Time O(n²) in the worst case. Space O(n) for the mutable expression copy.

Operand stack

Scan once and store unfinished values in a stack. A number starts a value, so push it. An operator finishes the two values on top: pop right, pop left, compute left operator right, and push the result.

def eval_rpn(tokens: list[str]) -> int:
    values: list[int] = []
 
    for token in tokens:
        if token not in "+-*/":
            values.append(int(token))
            continue
 
        right = values.pop()
        left = values.pop()
        if token == "+":
            values.append(left + right)
        elif token == "-":
            values.append(left - right)
        elif token == "*":
            values.append(left * right)
        else:
            quotient = abs(left) // abs(right)
            values.append(-quotient if (left < 0) != (right < 0) else quotient)
 
    return values[0]

Using absolute values for division makes the rounding rule explicit. Floor division alone is wrong for negative results because Python rounds down, while this problem asks you to truncate toward zero.

Time O(n) — every token is handled once. Space O(n) for the largest unfinished operand stack.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraytokens: string[]

Expected

Run: visible + custom · Submit: full suite