Evaluate Reverse Polish Notation

You are given an arithmetic expression in Reverse Polish Notation (postfix), split into a list of string tokens. In this notation each operator comes after its two operands, so 3 + 4 is written ["3", "4", "+"], and no parentheses are ever needed.

Each token is either an integer (possibly negative, like "-7") or one of the operators +, -, * and /. Evaluate the expression and return its integer value.

Division between two integers truncates toward zero (so -7 / 2 is -3). The expression is always valid, never divides by zero, and every intermediate result fits in a 32-bit signed integer.

Example 1

Example 2

Example 3

Constraints

• 1 <= tokens.length <= 104
• Each token is an operator + - * / or an integer in the range [-200, 200].
• The expression is valid and contains no division by zero.
• All intermediate results fit in a 32-bit signed integer.

Pattern Path · Stacks · problem 43 of 169

Start simple

Repeatedly scan the list for the first operator, replace it and its two operands with the result, and rescan: O(n²) time.

The key idea

In postfix notation an operator always applies to the two values produced most recently that have not been consumed yet. "Most recent first" is exactly what a stack provides.

Read the tokens left to right. A number is simply pushed. An operator pops two values: the first one popped is the right operand and the second is the left operand, because the left one was pushed earlier. Apply the operator and push the result, which may itself become an operand of a later operator. When all tokens are processed, a valid expression leaves exactly one value on the stack: the answer.

Two details trip people up. Operand order matters for - and /. And division must truncate toward zero: Python's // rounds toward negative infinity (-7 // 2 == -4), so use int(a / b) there, and in JavaScript use Math.trunc(a / b). Also recognise operators by exact match, because a token like "-7" starts with a minus sign but is a number.

Complexity

• Time: O(n)
• Space: O(n) for the stack

Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in ("+", "-", "*", "/"):
                stack.append(int(token))  # a number, possibly negative
                continue
            right = stack.pop()  # pushed last, so it is the right operand
            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))  # truncate toward zero, unlike //
        return stack[0]

JavaScript

var evalRPN = function(tokens) {
  const stack = [];
  for (const token of tokens) {
    if (!["+", "-", "*", "/"].includes(token)) {
      stack.push(Number(token)); // a number, possibly negative
      continue;
    }
    const right = stack.pop(); // pushed last, so it is the right operand
    const left = stack.pop();
    switch (token) {
      case "+": stack.push(left + right); break;
      case "-": stack.push(left - right); break;
      case "*": stack.push(left * right); break;
      case "/": stack.push(Math.trunc(left / right)); break; // toward zero
    }
  }
  return stack[0];
};

What the interviewer is checking

It checks that you see the natural fit between postfix evaluation and a stack, and that you are careful about operand order and integer division semantics.

Mistakes to avoid

• Popping operands in the wrong order, which breaks subtraction and division.
• Using floor division (// in Python) for negative results.
• Treating any token that starts with - as an operator, which misreads negative numbers.
• Leaving the result as a float in JavaScript instead of truncating it.

Follow-ups to expect

• How do you convert an infix expression to RPN? (Shunting-yard with an operator stack.)
• Evaluate infix with parentheses directly? (Two stacks: values and operators.)
• Support unary operators or functions? (Track arity per operator.)

In real software

Stack-based virtual machines (the JVM, Python bytecode, WebAssembly), HP calculators and compilers that evaluate expression trees all execute postfix code with an operand stack.

Practice next