Evaluate Reverse Polish Notation

LeetCode 150: Evaluate Reverse Polish Notation Solution & Explanation

Problem Overview

TL;DR: Iterate through the tokens, pushing numbers onto a stack and popping the top two elements to perform operations whenever an operator is encountered.

The "Evaluate Reverse Polish Notation" problem requires us to compute the value of an arithmetic expression presented in Reverse Polish Notation (RPN), also known as postfix notation. In this format, operators follow their operands. For example, the expression 3 + 4 is written as 3 4 +. We are given an array of strings containing integers and the operators +, -, *, and /. We must return the final integer result, adhering to specific rules like truncation toward zero for division.

This is a classic LeetCode 150 solution often used in interviews to test understanding of stack data structures and expression parsing.

Brute Force Approach for Evaluate Reverse Polish Notation

While a stack is the standard solution, a naive or "brute force" mental model might involve repeated scanning of the array to resolve operations in place.

1. Algorithm: Scan the tokens array from left to right.
2. Find the first operator (e.g., +).
3. Look at the two immediate predecessors (the operands).
4. Perform the calculation.
5. Replace the triplet (operand, operand, operator) with the result in the array.
6. Repeat the scan from the beginning (or shift the array) until only one element remains.

Pseudo-code:

while length(tokens) > 1:
    find index i of first operator
    val = calculate(tokens[i-2], tokens[i-1], tokens[i])
    replace tokens[i-2...i] with val
    resize array
return tokens[0]

Complexity Analysis:

• Time Complexity: $O(N^2)$. In the worst case, finding the operator and shifting the array elements (removing the triplet and inserting the result) takes linear time relative to the current size of the array. Doing this for every operator results in quadratic time complexity.
• Why it fails: This approach involves heavy array manipulation (shifting elements), which is computationally expensive. For the constraint $N = 10^4$, an $O(N^2)$ solution performs roughly $10^8$ operations, which risks a Time Limit Exceeded (TLE) or simply demonstrates inefficient resource usage during an interview.

Algorithm Strategy: Stack Patterns

To implement the optimal solution for Evaluate Reverse Polish Notation:

1. Initialize an empty stack.
2. Iterate through each string token in the input array.
3. Check if the token is an operator:
   • If it is +, -, *, or /, pop the top two elements from the stack.
   • Crucial Step: The first element popped is the second operand ($b$). The second element popped is the first operand ($a$). This order matters for subtraction and division.
   • Perform the operation ($a \text{ op } b$).
   • Push the result back onto the stack.
4. If the token is a number:
   • Convert the string to an integer.
   • Push it onto the stack.
5. After processing all tokens, the stack will contain exactly one element, which is the final result.

Execution Flow

Let's trace the logic deterministically.

1. Initialization: Create stack = [].
2. Loop: token in tokens.
3. Case: Operand (Number)
   • Parse token to integer val.
   • stack.push(val).
4. Case: Operator
   • right_operand = stack.pop()
   • left_operand = stack.pop()
   • If +: result = left_operand + right_operand
   • If -: result = left_operand - right_operand
   • If *: result = left_operand * right_operand
   • If /: result = int(left_operand / right_operand) (ensure truncation towards zero).
   • stack.push(result)
5. Termination: Return stack.pop().

Proof of Correctness

The correctness relies on the definition of Reverse Polish Notation. In RPN, every operator is preceded by its operands. By using a stack, we guarantee that when an operator is encountered, the values at the top of the stack are precisely the operands associated with that operator. Since the problem guarantees a valid RPN expression, the stack will never underflow (attempt to pop from empty) during execution, and exactly one value will remain at the end representing the total evaluation.

Pattern Reuse Notes

The Stack - Expression Evaluation pattern is highly reusable. Understanding how to manage operands and operators with a stack is critical for the following problems:

• LeetCode 224: Basic Calculator - Requires handling parentheses and operator precedence (often by converting Infix to RPN or using two stacks).
• LeetCode 227: Basic Calculator II - Introduces operator precedence (*, / over +, -) without parentheses.
• LeetCode 772: Basic Calculator III - The most complex variation combining parentheses and all operators.

In all these cases, the core mechanic involves using a stack to defer operations until the necessary operands are available or until precedence rules dictate execution.

Reference Implementation

C++ Solution for LeetCode 150

1#include <vector>
2#include <string>
3#include <stack>
4#include <stdexcept>
5
6class Solution {
7public:
8    int evalRPN(std::vector<std::string>& tokens) {
9        std::stack<int> st;
10
11        for (const std::string& token : tokens) {
12            if (token == "+" || token == "-" || token == "*" || token == "/") {
13                // Pop operands. Order matters for - and /
14                int b = st.top(); st.pop();
15                int a = st.top(); st.pop();
16
17                if (token == "+") {
18                    st.push(a + b);
19                } else if (token == "-") {
20                    st.push(a - b);
21                } else if (token == "*") {
22                    st.push(a * b);
23                } else {
24                    // C++ integer division truncates toward zero automatically
25                    st.push(a / b);
26                }
27            } else {
28                // Token is a number
29                st.push(std::stoi(token));
30            }
31        }
32
33        return st.top();
34    }
35};

Java Solution for LeetCode 150

1import java.util.Stack;
2
3class Solution {
4    public int evalRPN(String[] tokens) {
5        Stack<Integer> stack = new Stack<>();
6
7        for (String token : tokens) {
8            if (isOperator(token)) {
9                int b = stack.pop();
10                int a = stack.pop();
11                
12                switch (token) {
13                    case "+":
14                        stack.push(a + b);
15                        break;
16                    case "-":
17                        stack.push(a - b);
18                        break;
19                    case "*":
20                        stack.push(a * b);
21                        break;
22                    case "/":
23                        // Java integer division truncates toward zero
24                        stack.push(a / b);
25                        break;
26                }
27            } else {
28                stack.push(Integer.parseInt(token));
29            }
30        }
31        
32        return stack.pop();
33    }
34
35    private boolean isOperator(String s) {
36        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
37    }
38}

Python Solution for LeetCode 150

1class Solution:
2    def evalRPN(self, tokens: list[str]) -> int:
3        stack = []
4        
5        for token in tokens:
6            if token in "+-*/":
7                b = stack.pop()
8                a = stack.pop()
9                
10                if token == "+":
11                    stack.append(a + b)
12                elif token == "-":
13                    stack.append(a - b)
14                elif token == "*":
15                    stack.append(a * b)
16                elif token == "/":
17                    # Python's // is floor division, not truncation toward zero.
18                    # We use int(a / b) to truncate correctly for negative results.
19                    stack.append(int(a / b))
20            else:
21                stack.append(int(token))
22                
23        return stack[0]