Skip to main content
CodePeetCodePeet
CodePeet 150

Evaluate Reverse Polish Notation

MEDIUMProblemSolveExternal Links

Description

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN), also known as postfix notation.

In RPN, operators come after their operands instead of between them. For example, the infix expression 2 + 1 is written as 2 1 + in RPN, and (2 + 1) * 3 becomes 2 1 + 3 *.

Evaluate the expression and return the resulting integer.

Rules:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or the result of another sub-expression.
  • Division between two integers always truncates toward zero (e.g., 6 / -132 = 0, not -1).
  • There will not be any division by zero.
  • The input always represents a valid arithmetic expression in RPN.
  • The answer and all intermediate calculations fit in a 32-bit integer.

Examples

Example 1

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

Output: 9

Explanation: In infix: (2 + 1) * 3 = 3 * 3 = 9.

Processing left to right:

  • 2, 1 are operands.
  • + operates on the previous two: 2 + 1 = 3.
  • 3 is an operand.
  • * operates on 3 and 3: 3 * 3 = 9.

Example 2

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

Output: 6

Explanation: In infix: 4 + (13 / 5) = 4 + 2 = 6.

Note: 13 / 5 = 2 (truncated toward zero, not rounded).

Example 3

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

Output: 22

Explanation: In infix:

((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= 17 + 5 = 22

Constraints

  • 1 ≤ tokens.length ≤ 10^4
  • tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200]
  • The input represents a valid arithmetic expression in Reverse Polish Notation
  • The answer and all intermediate calculations can be represented in a 32-bit integer

Editorial

Brute Force - Repeated Scan and Reduce

Intuition

The most direct way to evaluate an RPN expression is to mimic how a human would simplify it on paper: find the smallest evaluable sub-expression, compute it, replace it with the result, and repeat.

In any valid RPN expression, there must be at least one spot where two consecutive numbers are immediately followed by an operator — this is a complete sub-expression like 2 1 +. We can:

  1. Scan left to right to find the first operator
  2. The two tokens immediately before it are its operands
  3. Evaluate: apply the operator to those two operands
  4. Replace those three tokens (operand, operand, operator) with the single result
  5. Repeat until only one value remains

This is like repeatedly collapsing the simplest part of the expression until everything is resolved. It's simple and correct, but each full scan takes O(n) time, and we need O(n) scans — making it O(n²) overall.

Step-by-Step Explanation

Let's trace Example 1: tokens = ["2", "1", "+", "3", "*"].

Pass 1: Scan left to right looking for the first operator.

  • Index 0: "2" — number, continue.
  • Index 1: "1" — number, continue.
  • Index 2: "+" — operator found! Its operands are at indices 0 and 1: a=2, b=1.
  • Evaluate: 2 + 1 = 3.
  • Replace indices 0, 1, 2 with "3". Array becomes: ["3", "3", "*"].

Pass 2: Scan again from the start.

  • Index 0: "3" — number.
  • Index 1: "3" — number.
  • Index 2: "*" — operator! Operands: a=3, b=3.
  • Evaluate: 3 * 3 = 9.
  • Replace: ["9"].

Done: Single element "9". Return 9.

Each pass scans up to n elements, and each evaluation reduces the array by 2 elements. For k operators, we do k passes → O(n × k) ≈ O(n²).

Brute Force — Repeated Scan and Reduce — Watch how we repeatedly scan the tokens array to find the first evaluable sub-expression (number, number, operator), compute it, and replace those three tokens with the result.

Algorithm

  1. While the tokens array has more than 1 element:
    a. Scan left to right to find the first operator (+, -, *, /)
    b. The two tokens immediately before the operator are operands a and b
    c. Evaluate a op b (with division truncating toward zero)
    d. Replace the three tokens (a, b, operator) with the single result
  2. Return the remaining element as an integer

Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        while (tokens.size() > 1) {
            for (int i = 0; i < (int)tokens.size(); i++) {
                if (tokens[i] == "+" || tokens[i] == "-" ||
                    tokens[i] == "*" || tokens[i] == "/") {
                    int a = stoi(tokens[i - 2]);
                    int b = stoi(tokens[i - 1]);
                    int result;
                    if (tokens[i] == "+") result = a + b;
                    else if (tokens[i] == "-") result = a - b;
                    else if (tokens[i] == "*") result = a * b;
                    else result = a / b; // truncates toward zero in C++
                    tokens[i - 2] = to_string(result);
                    tokens.erase(tokens.begin() + i - 1,
                                 tokens.begin() + i + 1);
                    break;
                }
            }
        }
        return stoi(tokens[0]);
    }
};
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        ops = {'+', '-', '*', '/'}
        while len(tokens) > 1:
            for i in range(len(tokens)):
                if tokens[i] in ops:
                    a = int(tokens[i - 2])
                    b = int(tokens[i - 1])
                    if tokens[i] == '+': result = a + b
                    elif tokens[i] == '-': result = a - b
                    elif tokens[i] == '*': result = a * b
                    else: result = int(a / b)  # truncate toward zero
                    tokens[i - 2] = str(result)
                    tokens.pop(i)      # remove operator
                    tokens.pop(i - 1)  # remove second operand
                    break
        return int(tokens[0])
class Solution {
    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        Set<String> ops = Set.of("+", "-", "*", "/");
        while (list.size() > 1) {
            for (int i = 0; i < list.size(); i++) {
                if (ops.contains(list.get(i))) {
                    int a = Integer.parseInt(list.get(i - 2));
                    int b = Integer.parseInt(list.get(i - 1));
                    int result;
                    switch (list.get(i)) {
                        case "+": result = a + b; break;
                        case "-": result = a - b; break;
                        case "*": result = a * b; break;
                        default:  result = a / b; break;
                    }
                    list.set(i - 2, String.valueOf(result));
                    list.remove(i);
                    list.remove(i - 1);
                    break;
                }
            }
        }
        return Integer.parseInt(list.get(0));
    }
}

Complexity Analysis

Time Complexity: O(n²)

Each scan of the array takes O(n). Each evaluation reduces the array by 2 elements. With approximately n/2 operators, we need n/2 passes. Total: O(n × n/2) = O(n²). For n = 10^4, that's ~5×10^7 operations — borderline but not optimal.

Space Complexity: O(1) extra (if modifying in place) or O(n)

The algorithm modifies the tokens array in place without using additional data structures. If we count the input modification, it's O(n) for the mutable list copy.

Why This Approach Is Not Efficient

The brute force performs O(n²) work because it rescans the array from the beginning after every single evaluation. Each time we find and evaluate one sub-expression, we must scan again to find the next one.

But notice a pattern: in RPN, whenever we encounter an operator, its two operands are always the two most recent numbers we've seen. This is exactly what a stack is designed for — it gives us instant access to the most recently added elements.

Instead of scanning and rescanning the array, we can process tokens in a single left-to-right pass:

  • When we see a number, we "remember" it (push onto stack)
  • When we see an operator, the two numbers we need are the two most recently remembered ones (top of stack)

This eliminates all redundant scanning, reducing time from O(n²) to O(n).

Optimal Approach - Stack-Based Evaluation

Intuition

RPN was designed specifically to be evaluated with a stack. The fundamental property of RPN is:

When you encounter an operator, its two operands are always the two most recently seen values that haven't been consumed yet.

A stack perfectly models this "most recent first" behavior. Think of it like stacking plates:

  • Each number is a plate placed on top of the stack
  • Each operator takes the top two plates, combines them into one new plate, and puts it back
  • At the end, exactly one plate remains — the answer

The key insight: the order of popping matters. When we pop two values for an operation, the first popped value is the second operand (right), and the second popped value is the first operand (left). For addition and multiplication this doesn't matter (commutative), but for subtraction and division the order is critical: a b - means a - b, where a was pushed first and b was pushed second.

Step-by-Step Explanation

Let's trace Example 1: tokens = ["2", "1", "+", "3", "*"].

Step 1: Token "2" — a number. Push 2 onto stack.

  • Stack: [2]

Step 2: Token "1" — a number. Push 1.

  • Stack: [2, 1]

Step 3: Token "+" — an operator! Pop two values: b = 1 (top), a = 2 (next). Compute a + b = 2 + 1 = 3. Push 3.

  • Stack: [3]

Step 4: Token "3" — a number. Push 3.

  • Stack: [3, 3]

Step 5: Token "*" — operator. Pop: b = 3, a = 3. Compute 3 * 3 = 9. Push 9.

  • Stack: [9]

Done: All tokens processed. Stack has one element: 9.

Notice how natural this is — the stack automatically handled the precedence encoded in the RPN expression. We never needed to search for anything; each token was processed exactly once in a single pass.

Optimal — Stack-Based Evaluation — Watch how a stack naturally evaluates RPN: numbers get pushed, operators pop two values, compute, and push the result. Each token is processed exactly once.

Algorithm

  1. Initialize an empty stack
  2. For each token in the tokens array (left to right):
    • If the token is a number: push it onto the stack
    • If the token is an operator (+, -, *, /):
      a. Pop the top value → this is b (second operand)
      b. Pop the next value → this is a (first operand)
      c. Compute a op b (for /, truncate toward zero)
      d. Push the result onto the stack
  3. The single remaining element on the stack is the answer

Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& token : tokens) {
            if (token == "+" || token == "-" ||
                token == "*" || token == "/") {
                int b = st.top(); st.pop();
                int a = st.top(); st.pop();
                if (token == "+")      st.push(a + b);
                else if (token == "-") st.push(a - b);
                else if (token == "*") st.push(a * b);
                else                   st.push(a / b);
            } else {
                st.push(stoi(token));
            }
        }
        return st.top();
    }
};
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        ops = {'+', '-', '*', '/'}
        for token in tokens:
            if token in ops:
                b = stack.pop()
                a = stack.pop()
                if token == '+':   stack.append(a + b)
                elif token == '-': stack.append(a - b)
                elif token == '*': stack.append(a * b)
                else:              stack.append(int(a / b))
            else:
                stack.append(int(token))
        return stack[0]
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        Set<String> ops = Set.of("+", "-", "*", "/");
        for (String token : tokens) {
            if (ops.contains(token)) {
                int b = stack.pop();
                int a = stack.pop();
                switch (token) {
                    case "+": stack.push(a + b); break;
                    case "-": stack.push(a - b); break;
                    case "*": stack.push(a * b); break;
                    case "/": stack.push(a / b); break;
                }
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.peek();
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the tokens array exactly once. Each token involves at most one push and/or one pop operation, both O(1). Total: O(n) where n is the number of tokens.

Space Complexity: O(n)

In the worst case, the stack holds approximately n/2 elements (when all numbers come first, followed by all operators — e.g., 1 2 3 4 + + +). Since each operator consumes two and produces one, the maximum stack depth is bounded by the number of operands, which is at most (n+1)/2. This is O(n).