What is the brute force approach and complexity for Evaluate Reverse Polish Notation?

Find the first "num num op", replace it by its value, rescan from the start with time complexity O(N²) and space complexity O(N).

What is the optimal approach and complexity for Evaluate Reverse Polish Notation?

Push numbers; on an operator pop b, pop a, push a op b with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Evaluate Reverse Polish Notation?

Look for key signals in the prompt: "operator comes after its operands" indicates When an operator appears, its operands were the most recent values → take them from the top of a stack.; "operand can be the result of an earlier part" indicates A computed result must be usable later like a plain number → push it back.; "no brackets needed" indicates The order is already fixed by the token order, so there is no precedence logic at all..

Evaluate Reverse Polish Notation

Medium·LeetCode #150Basic Anchor

LeetCode

Jump:

30-Second Mental ModelStack — Expression evaluation (operand stack)

Complexity:O(N²)→O(N)

Key Insight

Read the tokens once from left to right. Every number is pushed on a stack, where it waits for its operator. An operator always uses the two most recent waiting numbers, which are the top two of the stack. Pop them, compute a op b, and push the result, because the result is now a waiting number too.

Core Validity Invariant

An operator always applies to the two most recent unused numbers, which are exactly the top two of the stack: b on top is the right side, a under it is the left side.

Problem

You are given an arithmetic expression written in Reverse Polish Notation (RPN), as a list of tokens. Return its value.

In RPN the operator comes after its two operands. So 3 4 + means 3 + 4, and 2 1 + 3 * means (2 + 1) * 3. There are no brackets, because the order of the tokens already says what gets computed first.

The operators are +, -, * and /.
Each operand is an integer, or the result of an earlier part of the expression.
Division between two integers truncates toward zero (7 / -2 = -3).
The expression is always valid and never divides by zero.

Input

A list of strings tokens. Each token is either one of "+", "-", "*", "/", or an integer like "42" or "-11".

Output

The integer value of the expression.

Example 1

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

Output: 9

2 1 + gives 3, then 3 3 * gives 9. In normal notation: (2 + 1) * 3.

Example 2

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

Output: 6

13 5 / gives 2 (13 / 5 = 2.6, cut to 2). Then 4 2 + gives 6. In normal notation: 4 + (13 / 5).

Example 3

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

Output: 22

In normal notation this is ((10 * (6 / ((9 + 3) * -11))) + 17) + 5. The inner part is 12 * -11 = -132, then 6 / -132 = 0, then 10 * 0 = 0, then 0 + 17 + 5 = 22.

Constraints

• 1 ≤ tokens.length ≤ 10^4
• Each token is an operator (`+ - * /`) or an integer in the range [−200, 200]
• The expression is valid, and every intermediate result fits in a 32-bit int

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
When I read an operator, which two numbers does it work on?
2.
Do I ever need a number again after an operator has used it?
3.
Once an operator produces a result, how should I treat that result for the operators that come later?
4.
For - and /, the order of the two operands matters. Which one is the left side?
5.
How can I tell the token "-" apart from the token "-11"?

Brute force approach

Idea

In valid RPN, the first operator always has two numbers right before it. So find the first "number, number, operator" triple, compute it, and replace those three tokens by one number. The list gets 2 shorter. Repeat until one number is left.

Thinking process

1
This is what you would do on paper: find something you can compute right now, compute it, write the result in its place.
2
The first operator in the list can always be computed, because nothing before it is an operator.
3
After replacing the triple, the list changed, so start scanning from the beginning again.
4
Each round removes one operator, and each round may scan and shift the whole list.

Visual

Each round scans from the start for the first operator, then collapses its triple.

Brute force rescanstokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]step 1/13

list

-11

▲i

Work

round: 1
triple: 9 3 +
value: 12
cells read this round: 5
total cells read: 5

Read 5 cells to find the first "num num op"

Round 1: scan from the start until the first operator with two numbers before it. 9 + 3 = 12.

Code & Implementation

brute.cpp

class Solution {
    bool isOp(const string& t) {
        // "-11" is a number, so an operator must be exactly one character.
        return t.size() == 1 && (t[0] == '+' || t[0] == '-' || t[0] == '*' || t[0] == '/');
    }

public:
    int evalRPN(vector<string>& tokens) {
        vector<string> list = tokens;
        // Keep collapsing until a single number is left.
        while (list.size() > 1) {
            // Scan from the start for the first "num num op" triple.
            for (int i = 2; i < (int)list.size(); i++) {
                if (isOp(list[i]) && !isOp(list[i - 1]) && !isOp(list[i - 2])) {
                    long long a = stoll(list[i - 2]);
                    long long b = stoll(list[i - 1]);
                    long long r;
                    if (list[i] == "+") r = a + b;
                    else if (list[i] == "-") r = a - b;
                    else if (list[i] == "*") r = a * b;
                    else r = a / b;   // C++ division already truncates toward zero

                    // Replace the three tokens by their value, then rescan from the start.
                    list[i - 2] = to_string(r);
                    list.erase(list.begin() + i - 1, list.begin() + i + 1);
                    break;
                }
            }
        }
        return (int)stoll(list[0]);
    }
};

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private boolean isOp(String t) {
        // "-11" is a number, so an operator must be exactly one character.
        return t.length() == 1 && (t.charAt(0) == '+' || t.charAt(0) == '-' || t.charAt(0) == '*' || t.charAt(0) == '/');
    }

    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        // Keep collapsing until a single number is left.
        while (list.size() > 1) {
            // Scan from the start for the first "num num op" triple.
            for (int i = 2; i < list.size(); i++) {
                if (isOp(list.get(i)) && !isOp(list.get(i - 1)) && !isOp(list.get(i - 2))) {
                    long a = Long.parseLong(list.get(i - 2));
                    long b = Long.parseLong(list.get(i - 1));
                    long r;
                    char op = list.get(i).charAt(0);
                    if (op == '+') r = a + b;
                    else if (op == '-') r = a - b;
                    else if (op == '*') r = a * b;
                    else r = a / b; // Java division truncates toward zero

                    // Replace the three tokens by their value, then rescan from the start.
                    list.set(i - 2, String.valueOf(r));
                    list.remove(i);
                    list.remove(i - 1);
                    break;
                }
            }
        }
        return (int) Long.parseLong(list.get(0));
    }
}

class Solution:
    def _is_op(self, t: str) -> bool:
        # "-11" is a number, so an operator must be exactly one character.
        return len(t) == 1 and t in ("+", "-", "*", "/")

    def evalRPN(self, tokens: list[str]) -> int:
        token_list = list(tokens)
        # Keep collapsing until a single number is left.
        while len(token_list) > 1:
            # Scan from the start for the first "num num op" triple.
            for i in range(2, len(token_list)):
                if (
                    self._is_op(token_list[i])
                    and not self._is_op(token_list[i - 1])
                    and not self._is_op(token_list[i - 2])
                ):
                    a = int(token_list[i - 2])
                    b = int(token_list[i - 1])
                    op = token_list[i]
                    if op == "+":
                        r = a + b
                    elif op == "-":
                        r = a - b
                    elif op == "*":
                        r = a * b
                    else:
                        r = int(a / b)  # truncates toward zero

                    # Replace the three tokens by their value, then rescan from the start.
                    token_list[i - 2] = str(r)
                    token_list.pop(i)
                    token_list.pop(i - 1)
                    break
        return int(token_list[0])

function isOp(t: string): boolean {
    // "-11" is a number, so an operator must be exactly one character.
    return t.length === 1 && (t === "+" || t === "-" || t === "*" || t === "/");
}

export function evalRPN(tokens: string[]): number {
    const list = [...tokens];
    // Keep collapsing until a single number is left.
    while (list.length > 1) {
        // Scan from the start for the first "num num op" triple.
        for (let i = 2; i < list.length; i++) {
            if (isOp(list[i]) && !isOp(list[i - 1]) && !isOp(list[i - 2])) {
                const a = parseInt(list[i - 2], 10);
                const b = parseInt(list[i - 1], 10);
                let r: number;
                if (list[i] === "+") r = a + b;
                else if (list[i] === "-") r = a - b;
                else if (list[i] === "*") r = a * b;
                else r = Math.trunc(a / b); // truncates toward zero

                // Replace the three tokens by their value, then rescan from the start.
                list[i - 2] = r.toString();
                list.splice(i - 1, 2);
                break;
            }
        }
    }
    return parseInt(list[0], 10);
}

Complexity

Time O(N²)Space O(N)

There are up to n / 2 operators, so up to n / 2 rounds. Each round scans from the start and erases from the middle of a vector, both O(n). With n = 10^4 that is around 10^8 simple steps, which is slow and wasteful.

Optimized approach

Idea

Start from brute force

Brute force looks for the first operator that has two numbers before it, computes that triple, and then scans the whole list again from the start.

Find the repeated work

Every round re-reads all the numbers at the front of the list that are still waiting for an operator. Nothing about them changed, we just forgot where we were.

Define the state — what variables do I need?

st: The numbers read so far that no operator has used yet, oldest at the bottom, newest on top.
a, b: When an operator arrives: `b` = the top (right operand), `a` = the one below it (left operand).

Define validity

An operator always applies to the two most recent unused numbers, which are exactly the top two of the stack: b on top is the right side, a under it is the left side.

Define the transitions — when does each pointer move, and why is it safe?

Token is a number (anything that is not a single `+ - * /`, so `"-11"` counts)

st.push(number)

Its operator has not appeared yet, so it has to wait. Newer numbers will be used before it.

Token is an operator

b = pop(); a = pop(); push(a op b)

RPN puts the operator right after its two operands, so they are the latest two unused values. The result replaces them as one new operand.

All tokens read

return st.top()

A valid expression leaves exactly one number: the value of the whole thing.

What does the current window add to the answer?

Each operator turns two waiting numbers into one. After the last token, every operator has been applied and one number remains.

Code & Implementation

optimal.cpp

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;   // numbers waiting for their operator
        for (const string& t : tokens) {
            // "-11" is a number, so an operator must be exactly one character.
            bool isOp = t.size() == 1 && (t[0] == '+' || t[0] == '-' || t[0] == '*' || t[0] == '/');
            if (!isOp) {
                st.push(stoll(t));
                continue;
            }
            // The top is the RIGHT operand, the one below it is the LEFT operand.
            long long b = st.top(); st.pop();
            long long a = st.top(); st.pop();
            if (t[0] == '+') st.push(a + b);
            else if (t[0] == '-') st.push(a - b);
            else if (t[0] == '*') st.push(a * b);
            else st.push(a / b);   // truncates toward zero, as required
        }
        return (int)st.top();
    }
};

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Long> st = new ArrayDeque<>(); // numbers waiting for their operator
        for (String t : tokens) {
            // "-11" is a number, so an operator must be exactly one character.
            boolean isOp = t.length() == 1 && (t.charAt(0) == '+' || t.charAt(0) == '-' || t.charAt(0) == '*' || t.charAt(0) == '/');
            if (!isOp) {
                st.push(Long.parseLong(t));
                continue;
            }
            // The top is the RIGHT operand, the one below it is the LEFT operand.
            long b = st.pop();
            long a = st.pop();
            char op = t.charAt(0);
            if (op == '+') st.push(a + b);
            else if (op == '-') st.push(a - b);
            else if (op == '*') st.push(a * b);
            else st.push(a / b); // truncates toward zero, as required
        }
        return st.pop().intValue();
    }
}

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        st: list[int] = []  # numbers waiting for their operator
        for t in tokens:
            # "-11" is a number, so an operator must be exactly one character.
            is_op = len(t) == 1 and t in ("+", "-", "*", "/")
            if not is_op:
                st.append(int(t))
                continue
            # The top is the RIGHT operand, the one below it is the LEFT operand.
            b = st.pop()
            a = st.pop()
            if t == "+":
                st.append(a + b)
            elif t == "-":
                st.append(a - b)
            elif t == "*":
                st.append(a * b)
            else:
                st.append(int(a / b))  # truncates toward zero, as required
        return st[0]

export function evalRPN(tokens: string[]): number {
    const st: number[] = []; // numbers waiting for their operator
    for (const t of tokens) {
        // "-11" is a number, so an operator must be exactly one character.
        const isOp = t.length === 1 && (t === "+" || t === "-" || t === "*" || t === "/");
        if (!isOp) {
            st.push(parseInt(t, 10));
            continue;
        }
        // The top is the RIGHT operand, the one below it is the LEFT operand.
        const b = st.pop()!;
        const a = st.pop()!;
        if (t === "+") st.push(a + b);
        else if (t === "-") st.push(a - b);
        else if (t === "*") st.push(a * b);
        else st.push(Math.trunc(a / b)); // truncates toward zero, as required
    }
    return st[0];
}

Complexity

Time O(N)Space O(N)

Each token is pushed or popped a constant number of times. The stack holds at most about n / 2 + 1 numbers.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Find the first "num num op", replace it by its value, rescan from the start	O(N²)	O(N)
Optimal	Push numbers; on an operator pop b, pop a, push a op b	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“operator comes after its operands”When an operator appears, its operands were the most recent values → take them from the top of a stack.
“operand can be the result of an earlier part”A computed result must be usable later like a plain number → push it back.
“no brackets needed”The order is already fixed by the token order, so there is no precedence logic at all.

Operator after its operands+latest unused values+result becomes a new operand→Stack — Expression evaluation (operand stack)

This is the anchor of the sub-pattern: numbers wait on a stack until their operator arrives. In RPN the operator always arrives right after its operands, so every operator can be applied immediately. In Basic Calculator II the operator comes between its operands and * / / beat + / -, so we must decide when a number is allowed to be combined. In Basic Calculator, brackets add a new level, and the stack saves the outer level's state instead of plain numbers.

Don't make this mistake

Popping the operands in the wrong order

✗ long long a = st.top(); st.pop(); long long b = st.top(); st.pop(); st.push(a - b);

✓ long long b = st.top(); st.pop(); // right side long long a = st.top(); st.pop(); // left side st.push(a - b);

3 5 - means 3 − 5 = −2. The top of the stack is the number pushed last, which is the right-hand side. Getting this wrong only shows up for - and /, so it can pass the first example and still be wrong.

Treating "-11" as the minus operator

✗ if (t[0] == '-') { /* operator */ }

✓ bool isOp = t.size() == 1 && (t[0] == '+' || t[0] == '-' || t[0] == '*' || t[0] == '/');

A negative number also starts with -. Only a token of length exactly 1 can be an operator.

Rounding division the wrong way

✗ st.push(floor((double)a / b));

✓ st.push(a / b); // C++ integer division truncates toward zero

The problem wants truncation toward zero: 7 / -2 = -3. floor gives −4. C++ / on integers already does the right thing, so don't convert to double.

Using int for intermediate values

✗ stack<int> st;

✓ stack<long long> st;

LeetCode promises every result fits in an int, so int passes. But in a general evaluator one * of two large values overflows silently. long long costs nothing here and makes the code safe.

Thinking about precedence (pattern confusion)

RPN has no precedence rules and no brackets. 2 1 + 3 * is (2 + 1) * 3 because + comes first in the token list, not because of any rule. If you start writing code that compares * with +, you are solving Basic Calculator II instead. Here every operator is applied the moment it is read.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Expression Parser & Interpreter Pattern

Abstract syntax tree evaluation and operator precedence parsing.

Explore Track

C++ Internals

Stack vs Heap Segments

Call stack frame layout, return addresses, and buffer overflow prevention.

Explore Track

Basic Calculator II