150. Evaluate Reverse Polish Notation - Explanation

Description

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation.

Return the integer that represents the evaluation of the expression.

The operands may be integers or the results of other operations.
The operators include '+', '-', '*', and '/'.
Assume that division between integers always truncates toward zero.

Example 1:

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

Output: 5

Explanation: ((1 + 2) * 3) - 4 = 5

Constraints:

1 <= tokens.length <= 1000.
tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100].

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.

Hint 1

A brute force solution would involve repeatedly finding an operator + - * / in the array and modifying the array by computing the result for that operator and two operands to its left. This would be an O(n^2) solution. Can you think of a better way? Maybe we can use a data structure to handle operations efficiently.

Hint 2

We can use a stack. We iterate through the array, and if we encounter a number, we push it onto the stack. If we encounter an operator, we pop two elements from the stack, treat them as operands, and solve the equation using the current operator. Then, we push the result back onto the stack. Why does this work?

Hint 3

As the array has postfix expression, stack helps us to maintain the correct order of operations by ensuring that we always use the most recent operands (those closest to the operator) when performing the operation. After the iteration, the final result is left in the stack.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

Reverse Polish Notation (RPN) evaluates expressions without parentheses by applying each operator to the two most recent numbers.
The brute-force idea is to repeatedly scan the list until we find an operator.
When we do, we take the two numbers before it, compute the result, and replace all three tokens with the result.
We continue compressing the list this way until only one value remains—the final answer.
This approach works but is slow because we repeatedly rebuild and rescan the list.

Algorithm

While more than one token exists:
- Scan the list from left to right.
- When an operator is found:
  - Take the two numbers immediately before it.
  - Apply the operator to compute a result.
  - Replace the pattern [number, number, operator] with the computed value.
  - Restart scanning.
When only one token is left, return it as the final result.

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 & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Doubly Linked List

Intuition

In Reverse Polish Notation, every operator works on the two most recent numbers before it.
A doubly linked list lets us move both left and right easily, so when we find an operator, we can quickly reach the two numbers before it.

The idea is:

Build a doubly linked list of all tokens (numbers and operators).
Walk through the list:
- When we see an operator, we look at the previous two nodes (the two operands),
  compute the result, and replace those three nodes (left operand, right operand, operator)
  with a single node containing the result.
We keep doing this until we’ve processed all operators and are left with just one value.

This behaves like the usual RPN evaluation but uses linked list navigation instead of a stack.

Algorithm

Create a doubly linked list from the tokens in order.
Set a pointer curr to the head of the list.
While the list still needs evaluation:
- If curr is an operator:
  - Let the two nodes before curr be the left and right operands.
  - Compute the result of left (op) right.
  - Replace the three nodes (left, right, operator) with a single node holding the result:
    - Relink the prev and next pointers around them.
    - Set curr to this result node.
- Move curr to the next node and continue.
When only one node with a number remains, return its value as the final result.

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 & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Recursion

Intuition

Reverse Polish Notation works naturally with recursion because every operator applies to the two most recent values that come before it.
If we process the expression from the end, every time we see:

a number → it is simply returned as a value
an operator → we recursively evaluate the two values that belong to it

This creates a natural evaluation tree:

Each operator becomes a recursive call,
Each number becomes a base case,
And the final return value is the fully evaluated expression.

This approach is clean, elegant, and mirrors the structure of RPN itself.

Algorithm

Start from the end of the token list.
Recursively:
- Pop a token.
- If it is a number, return it.
- If it is an operator:
  - Recursively compute the right operand.
  - Recursively compute the left operand.
  - Apply the operator to both results.
  - Return the computed value.
The first completed call returns the final answer.

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 & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Stack

Intuition

A stack fits Reverse Polish Notation perfectly because the most recent numbers are always the ones used next.
As we scan the tokens:

When we see a number, we push it onto the stack.
When we see an operator, we pop the top two numbers, apply the operation, and push the result back.

This way, the stack always holds the intermediate results, and the final remaining value is the answer.
It is clean, efficient, and directly follows how RPN is meant to be evaluated.

Algorithm

Create an empty stack.
For each token:
- If it is a number, convert it to an integer and push it onto the stack.
- If it is an operator:
  - Pop the top two numbers.
  - Apply the operator in the correct order.
  - Push the result back onto the stack.
After processing all tokens, the stack contains exactly one value — return it.

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 & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$