DSA sheet · Stack · Expression evaluation pattern

Evaluate Reverse Polish Notation

The second problem of the expression evaluation pattern. Here the expression is written in a special order where the two numbers come first and the operator comes after them, like 2 1 + instead of 2 + 1. The teacher first solves it by editing the list in place (brute force, O(n²)), shows why a couple of plain variables are not enough, and then gives the stack solution, which is short and O(n). She even says it's simpler than Basic Calculator II from the previous video: in this notation there is no precedence to worry about at all.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks and postfix expressions from scratch
• Part A · Brute force: shrink the list in place
• Part B · Optimal: a stack of numbers
• Part C · Revision page

Part 0 · Stacks and postfix expressions from scratch

What is a stack?

A stack is like a pile of books. You add a book on the top (push) and you remove the book on the top (pop). Looking at the top book without removing it is peek. The last one in is the first one out: LIFO (Last In, First Out).

We draw stacks left = bottom, right = top. Popping or peeking an empty list raises IndexError, so normally you check if st: first. In this problem the input is guaranteed valid, which means there are always at least two numbers in the stack when an operator arrives (we rely on that).

Three ways to write the same expression

The nice thing about postfix: it needs no brackets and no precedence rules. The order of the tokens already tells you exactly what to compute first. Every time you meet an operator, you apply it to the two most recent numbers that are still unused, and the result becomes a new number.

The expression evaluation pattern (stack version)

• Keep a stack of numbers. A number token → push it.
• An operator token → pop two numbers, combine, push the result back.
• At the end, one number is left. That's the value.

Order matters: which popped number is the left one?

For + and × the order doesn't matter, but for − and ÷ it does. The first pop gives the number that came later (the right operand). The second pop gives the earlier one (the left operand).

  tokens: 13  5  /        stack [13, 5]      top → | 5  |  ← b = pop()  (right)
                                                   | 13 |  ← a = pop()  (left)
  answer = a / b = 13 / 5

Python trap: division must truncate toward zero

The problem says division truncates toward zero (drop the decimals). Python's // rounds down instead, which is different for negative results.

Always write int(a / b) here. Numbers in this problem can be negative (tokens like "-11"), so this really happens. LeetCode's third example breaks if you use //.

Part A · Brute force: shrink the list in place

LeetCode 150

1The question in simple words

You get a list of strings tokens. Each token is either a whole number (maybe negative) or one of + - * /. The tokens form a valid expression in Reverse Polish Notation. Return its value as an integer.

Read ex 1 like this: "2 and 1 have come; now a + arrives, so add them → 3. Then 3 comes; now a * arrives, so multiply the two latest → 3 × 3 = 9."

2What the constraints tell us

• 1 ≤ tokens.length ≤ 10⁴. The teacher reads the constraint to decide if brute force is good enough: O(n²) = 10⁸, which is right at the edge, so it'll be slow (not instant). That's the signal to look for something better.
• Each number is in [−200, 200], and every intermediate result fits in 32 bits → no overflow worries.
• Numbers can be negative, like "-11". So "-" alone is an operator, but "-11" is a number. Keep that in mind when you decide "is this an operator?".
• The expression is valid → every operator has two numbers available, and there is no division by zero.

3Intuition: why two variables are not enough

A first idea: walk through the tokens, keep the last two numbers in variables a and b, and when an operator comes, compute a op b. For ex 1 that works. But look at this input:

Three numbers arrive before the first operator. With only a and b, the 2 gets overwritten. The + gives 1 + 3 = 4, and then the * needs 4 and the 2, which we already lost. We need something that can hold any number of waiting numbers, without losing any.

The brute-force answer: don't store anything separately. Keep everything in the list itself and edit the list: when an operator is at index i, its two numbers are at i − 2 and i − 1. Replace those three tokens by one result.

4Building the logic

5Approach steps

1. Copy the tokens into a list we can edit.
2. While the list has more than one item:
3. Scan from i = 0. At the first operator, take a = lst[i-2], b = lst[i-1], compute a op b.
4. Put the result at i − 2, remove positions i − 1 and i, then break to restart the scan.
5. Return the single remaining value.

6Code (Python)

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        ops = {"+", "-", "*", "/"}
        lst = list(tokens)                    # a copy we are allowed to shrink
        while len(lst) > 1:                   # more than one item = not finished
            for i in range(len(lst)):
                t = lst[i]
                if t in ops:                  # the first operator we meet
                    a = int(lst[i - 2])       # left operand
                    b = int(lst[i - 1])       # right operand
                    if t == "+":
                        val = a + b
                    elif t == "-":
                        val = a - b
                    elif t == "*":
                        val = a * b
                    else:
                        val = int(a / b)      # truncate toward zero
                    lst[i - 2] = str(val)     # the result replaces the left operand
                    lst.pop(i)                # remove the operator
                    lst.pop(i - 1)            # remove the right operand
                    break                     # indexes changed: restart the scan
        return int(lst[0])

We pop index i before i − 1 so the second removal isn't shifted by the first. We store the result back as a string so the list stays all strings, like the input.

7Code line by line

8Dry run: ex 1, tokens = ["2", "1", "+", "3", "*"]

9Complexity & remember

• Each round scans from the start to find an operator → up to O(n).
• Each removal shifts the rest of the list one step left → another O(n). (Removing from the middle of a list is not O(1): every later item moves and gets a new index.)
• There are about n/2 operators, so about n/2 rounds → Time O(n²). With n = 10⁴ that's around 10⁸: it passed for the teacher, but the submission was clearly slow.
• Space O(n) for the copy of the list.

Part B · Optimal: a stack of numbers

1The question in simple words

Same question. Now we want one pass over the tokens and no list removals.

2What the constraints tell us

• n ≤ 10⁴ → O(n) is instant. The stack gives us O(n).
• Valid input → when an operator arrives, the stack always has at least two numbers, so the two pops are safe. At the end exactly one number remains.

3Intuition: a pile of waiting numbers

Look at what the brute force really did: it always used the two most recent unused numbers, and the result became the newest number. "Most recent first" is exactly what a stack gives us.

• A number → it has to wait for an operator → push it.
• An operator → its two numbers are the two on top of the stack → pop twice, compute, push the result (it may be used by a later operator).

Take the teacher's example 2 3 1 * +: push 2, push 3, push 1 → [2, 3, 1]. At *, pop 1 and 3 → 3 × 1 = 3 → push → [2, 3]. At +, pop 3 and 2 → 2 + 3 = 5 → push → [5]. Answer 5. Nothing gets lost (the 2 waited patiently at the bottom), and nothing is removed from the middle of any list.

4Building the logic

5Approach steps

1. Make an empty stack.
2. For each token: if it's one of + − * /, pop b, pop a, push a op b.
3. Otherwise push int(token).
4. Return the only item left: st[-1] (or st.pop()).

6Code (Python)

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        st = []
        for t in tokens:
            if t in ("+", "-", "*", "/"):
                b = st.pop()                  # right operand (came later)
                a = st.pop()                  # left operand (came earlier)
                if t == "+":
                    st.append(a + b)
                elif t == "-":
                    st.append(a - b)
                elif t == "*":
                    st.append(a * b)
                else:
                    st.append(int(a / b))     # truncate toward zero, NOT //
            else:
                st.append(int(t))             # a number waits on the stack
        return st[-1]

7Code line by line

8Dry run: ex 3

Step 7 is the trap: 6 // -132 in Python is −1, which would make step 8 give −10 and the final answer 12 ✗. With int(6 / -132) we get 0 and the correct 22.

The red box is the top. The bottom of each picture is the bottom of the stack.

Ex 1 in short: push 2, push 1 → [2, 1]; "+" → 3 → [3]; push 3 → [3, 3]; "*" → 9 → [9]. Answer 9.

9Complexity & remember

• Time O(n): each token is visited once, and each push and pop is O(1). No rescans, no shifting.
• Space O(n): in the worst case many numbers wait on the stack (about n/2 of them, e.g. all numbers first and all operators at the end). The teacher's point: this extra space is small, and going from O(n²) to O(n) time is well worth it.
• When she submits, the stack version is visibly faster than the brute force.

Part C · Revision page

s = Solution()
print(s.evalRPN(["2", "1", "+", "3", "*"]))     # 9
print(s.evalRPN(["4", "13", "5", "/", "+"]))    # 6
print(s.evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22
print(s.evalRPN(["2", "1", "3", "+", "*"]))     # 8
print(s.evalRPN(["-7", "2", "/"]))              # -3
print(s.evalRPN(["7"]))                         # 7

Based on this video: Evaluate Reverse Polish Notation