Framework Thinking - Neetcode 150 - Evaluate Reverse Polish Notation

Here is the problem for Evaluate Reverse Polish Notation.

1. Understand the Problem

You are given a list of strings representing an expression in Reverse Polish Notation, where:

Operands (numbers) appear before their operators.
Supported operators are: +, -, *, /.
Division should truncate toward zero (i.e., int(a / b) in Python works).
You need to evaluate the expression and return one integer.

2. Clarify contraints

Can it have negative number ?

May include negative numbers (e.g., “-11”).

Is input always valid?

Yes, operations are valid and expression reduces to one number.
Example 1: [2,”+”]

if len(stack) < 2:
    raise ValueError("Insufficient operands for operator '{}'".format(token))

Example 2: [0,2,”/”]

if token == "/" and b == 0:
    raise ZeroDivisionError("Division by zero is not allowed.")

Example 3: [2,2,2,2,”+”]

if len(stack) != 1:
    raise ValueError("Invalid expression: too many operands.")

Division behavior?

Truncate toward zero.
Example 1: -3 / 2 → -1.5 => -1.
Example 2: -2/3 => -0.666 => 0.

3. Brainstorm 2-3 solutions

3.1. Brute force - O(N^2) by copy array

Idea: when find “+-*/” => calculate nums[i - 2] / nums[i - 1] => append result + nums[i + 1]
Note: Idea about in-place and copy string.

tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]

In-place: O(1) => address[0] + k * len(size_char)
Copy new: O(N)
Time: O(N^2) (because copy new array)
Space: O(N).

3.2. Doubly Linked List - O(N) in-place

Idea: inplace calculate to make it O(N)
Time: O(N) - in-place replacement.
Space: O(N).

3.3. Recursion

Idea: because you traverse all the array O(N).
Loop from the end, and calculate backward => Each item 1 return.

=> Always think that we do not have easy 1,1,1,+ near to each other => but must be 1,*,1,2,+.

Time: O(N).
Space: O(N).

3.4. Stack

Idea: similar to recursion but easier to implement.
Time: O(N).
Space: O(N).

4. Implement solutions

4.1. Brute Force - O(N^2).

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        while len(tokens) > 1:
            for i in range(len(tokens)):
                if tokens[i] in "+-*/":
                    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
                    elif tokens[i] == '/':
                        result = int(a / b)
                    tokens = tokens[:i-2] + [str(result)] + tokens[i+1:]
                    break
        return int(tokens[0])

Time: O(N^2).
Space: O(N).

4.2. Doubly Linked List - O(N)

class DoublyLinkedList:
    def __init__(self, val, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        head = DoublyLinkedList(tokens[0])
        curr = head

        for i in range(1, len(tokens)):
            curr.next = DoublyLinkedList(tokens[i], prev=curr)
            curr = curr.next

        while head is not None:
            if head.val in "+-*/":
                l = int(head.prev.prev.val)
                r = int(head.prev.val)
                if head.val == '+':
                    res = l + r
                elif head.val == '-':
                    res = l - r
                elif head.val == '*':
                    res = l * r
                else:
                    res = int(l / r)

                head.val = str(res)
                head.prev = head.prev.prev.prev
                if head.prev is not None:
                    head.prev.next = head

            ans = int(head.val)
            head = head.next

        return ans

Time: O(N).
Space: O(N).

4.3. Recursion - O(N), each item 1 return.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        def dfs():
            token = tokens.pop()
            if token not in "+-*/":
                return int(token)

            right = dfs()
            left = dfs()

            if token == '+':
                return left + right
            elif token == '-':
                return left - right
            elif token == '*':
                return left * right
            elif token == '/':
                return int(left / right)

        return dfs()

Time: O(N).
Space: O(N).

4.4. Stack - O(N), easy implement than recursion

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(float(b) / a))
            else:
                stack.append(int(c))
        return stack[0]

Time: O(N).
Space: O(N).

5. Dry run examples

input = ["2","1","+","3","*"]

Token	Action	Stack
`"2"`	push 2	`[2]`
`"1"`	push 1	`[2, 1]`
`"+"`	pop → 2 + 1 = 3	`[3]`
`"3"`	push 3	`[3, 3]`
`"*"`	pop → 3 × 3 = 9	`[9]`

November 25, 2025