Skip to content

Volume ITechnology

4.8.3 — Evaluate Reverse Polish Notation ​

LeetCode 150 · Medium

The problem ​

You are given a list of strings called tokens. Together they form a sum written in Reverse Polish Notation, or RPN. In RPN, each operator comes after the two numbers it works on. So 2 + 1 is written as 2 1 +. Work out the value of the whole expression and return it.

tokens = ["2", "1", "+", "3", "*"]     →  9     means (2 + 1) × 3
tokens = ["4", "13", "5", "/", "+"]    →  6     means 4 + (13 / 5) = 4 + 2

The operators are +, -, * and /. Division keeps only the whole-number part, rounding toward zero. So 13 / 5 = 2.6 becomes 2, and -13 / 5 = -2.6 becomes −2 (not −3).

There are up to 10,000 tokens. Each number is between −200 and 200. The expression is always valid, and there is never a division by zero.

What the problem is really asking ​

In normal writing, 2 + 3 * 4 needs rules to tell you that * goes first. You need brackets to change that order: (2 + 3) * 4. RPN needs neither. The order of the tokens already decides the order of the work. That is why it exists.

Here is how to read RPN by hand. Go left to right. When you meet an operator, it works on the two most recent numbers that have not been used yet. Replace those two numbers and the operator with the result, and carry on.

"The two most recent" is the clue. A structure that always hands back the most recent item first is a stack, a pile where you only add to and take from the top.

The brute force, and where it wastes work ​

Do exactly what you would do by hand on paper. Find the first operator, combine the two numbers just before it, put the result in their place, and start scanning again from the beginning.

python
def evalRPN(tokens):
    tokens = tokens[:]
    while len(tokens) > 1:
        for i, t in enumerate(tokens):
            if t in "+-*/" and len(t) == 1:
                a, b = int(tokens[i - 2]), int(tokens[i - 1])
                r = {"+": a + b, "-": a - b, "*": a * b, "/": int(a / b)}[t]
                tokens[i - 2:i + 1] = [str(r)]      # three tokens become one
                break
    return int(tokens[0])

Each step rebuilds the list and rescans from the start. With 10,000 tokens that is O(n^2).

The waste in one sentence: after every operation it rescans from the beginning, when the two numbers it needs next are always the two most recent ones.

The idea ​

Walk the tokens once, with a stack.

  • A number is pushed onto the stack.
  • An operator pops the top two numbers, combines them, and pushes the result back.

At the end, the stack holds exactly one number: the answer.

Which popped number is which matters. The first number you pop is the one pushed last, so it is the right-hand number. For 13 5 / you pop 5 first, then 13, and compute 13 / 5, not 5 / 13. For + and * the order does not matter, which is why getting it wrong passes half the tests and fails the rest.

The solution ​

python
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        ops = {                                        # (1)
            "+": lambda a, b: a + b,
            "-": lambda a, b: a - b,
            "*": lambda a, b: a * b,
            "/": lambda a, b: int(a / b),              # (2)
        }
        stack = []                                     # (3)

        for t in tokens:                               # (4)
            if t in ops:                               # (5)
                b = stack.pop()                        # (6)
                a = stack.pop()
                stack.append(ops[t](a, b))             # (7)
            else:
                stack.append(int(t))                   # (8)

        return stack[0]                                # (9)
ts
function evalRPN(tokens: string[]): number {
  const ops: Record<string, (a: number, b: number) => number> = {   // (1)
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),                               // (2)
  };
  const stack: number[] = [];                                       // (3)

  for (const t of tokens) {                                         // (4)
    if (t in ops) {                                                 // (5)
      const b = stack.pop()!;                                       // (6)
      const a = stack.pop()!;
      stack.push(ops[t](a, b));                                     // (7)
    } else {
      stack.push(Number(t));                                        // (8)
    }
  }

  return stack[0];                                                  // (9)
}

Line by line ​

(1) A table from each operator to what it does. Each value is a small function written with lambda, which is Python's way of writing a one-line function without a name. lambda a, b: a + b means "a function that takes a and b and returns their sum".

A table like this is called a dispatch table. It replaces a chain of if/elif checks. Adding a new operator is one new line in the table, not a new branch in the loop. It is the smallest form of the Strategy pattern from 9.4.12.

(2) Division that rounds toward zero. This line is where most wrong answers to this problem go wrong.

Python's // operator rounds down, toward negative infinity. So -13 // 5 is −3. But the problem wants rounding toward zero, which gives −2. The fix is int(a / b). a / b gives the decimal -2.6, and int() in Python simply drops the decimal part, giving −2.

For positive numbers the two methods agree. That is why this bug hides until a test uses a negative number.

ExpressionPython //int(a / b)Correct here
13 / 5222
−13 / 5−3−2−2

JavaScript has the same trap in a different spot. / gives a decimal, and Math.floor(-2.6) is −3. Math.trunc drops the decimal part, which rounds toward zero.

(3) The stack of numbers waiting to be used.

(4) Walk the tokens once, left to right.

(5) Is this token an operator? We check whether it is one of the table's keys. This is safer than checking whether the token "looks like a number". The token "-4" starts with a minus sign, but it is a number, not the operator -. Checking against the table avoids that confusion.

(6) Pop the two numbers, right-hand one first. b is popped first because it was pushed last, so it is the right-hand number. a is the left-hand number.

(7) Combine them and push the result. ops[t] looks up the function for this operator, and (a, b) calls it. The result goes back on the stack, ready to be used by a later operator.

(8) A number. int(t) turns the text "13" into the number 13, and we push it.

(9) The answer. The expression is valid, so exactly one number is left.

Trace ​

Take tokens = ["4", "13", "5", "/", "+"].

TokenKindActionStack after
"4"numberpush 4[4]
"13"numberpush 13[4, 13]
"5"numberpush 5[4, 13, 5]
"/"operatorpop b = 5, pop a = 13, push int(13 / 5) = 2[4, 2]
"+"operatorpop b = 2, pop a = 4, push 4 + 2 = 6[6]

The answer is 6.

Complexity, derived ​

Time. We visit each of the n tokens once. A number costs one conversion and one push. An operator costs two pops, one arithmetic step and one push. Each of those is constant time. So the total is O(n).

Space. In the worst case, many numbers come before the operators, like ["1", "2", "3", "4", "+", "+", "+"]. Then about half the tokens sit on the stack at once. That is O(n).

Edge cases ​

  • Negative numbers as tokens, like "-11". Not a key in the table, so line (8) pushes −11.
  • A single number, like ["18"]. It is pushed and returned.
  • Negative division, like ["-13", "5", "/"]. Line (2) gives −2, not −3.
  • Long chains, like five numbers followed by four +s. The stack grows to five and then shrinks one step at a time.

Variations you will meet ​

RPN is not just a puzzle. It is the form that sums take inside computers.

  • Turning normal notation into RPN. The shunting-yard algorithm reads 2 + 3 * 4 and writes 2 3 4 * +, using a second stack to hold operators until it knows their order. Run this page's code on the result, and you have a full calculator.
  • Stack machines. Many programming languages compile your code into simple instructions for a "stack machine". An instruction like "add" pops two numbers and pushes their sum, exactly like line (7). Java and WebAssembly both work this way.
  • Basic Calculator (LeetCode 224 and 227). Work out a normal sum with brackets and * before +, directly from the string. Harder, and it uses the same stack ideas.

The general lesson: when each operation uses the most recent results, use a stack.

What the interviewer will push on ​

"Which popped number is the left one?" The second one popped. Say it before you write the lines.

"Why not // in Python?" It rounds down, not toward zero. Give −13 / 5 as the example.

"How would you handle normal notation, like 2 + 3 * 4?" The shunting-yard algorithm: one list for output, one stack for operators. Before pushing an operator, pop any operators already on the stack that should happen first.

"What if the input could be invalid?" An operator could find fewer than two numbers on the stack, or more than one number could be left at the end. A real calculator checks both and reports where the error is.

"Why a table instead of if/elif?" Adding an operator is one line. For example, a power operator is "^": lambda a, b: a ** b. The loop itself never changes.

One thing to volunteer: mention that stack machines inside real programming languages run their instructions exactly like this. It turns the puzzle into something real.

Next: 4.8.4 Generate Parentheses. Despite its place in this group, it is not a stack problem. It is the first backtracking problem in the book.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet