Evaluate Reverse Polish Notation with Stack Data Structure

Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands. This solution demonstrates how to evaluate RPN expressions using a stack data structure to handle the operator-operand relationships efficiently.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected range of input tokens? (e.g., how many tokens can there be, what's the maximum length of each token?)
2. Are we guaranteed that the input will always represent a valid RPN expression? (i.e., no malformed expressions)
3. Can we mutate the input array, or do we need to work with a copy?
4. What should we return in case of invalid input or division by zero? (Assume valid input per problem constraints)
5. Are we expected to handle negative numbers and multi-digit integers?

Restatement in my own words: We are given an array of strings representing a valid Reverse Polish Notation (RPN) expression. In RPN, operators come after their operands, and we need to evaluate the expression to compute a single integer result. For example, the expression "3 4 + 5 *" would be evaluated as (3 + 4) * 5 = 35.

Input, Output, and Constraints:

• Input: An array of strings where each string is either an integer or one of the operators: "+", "-", "*", "/"
• Output: A single integer representing the evaluated result of the RPN expression
• Constraints:
  • The input array is guaranteed to be valid (no malformed expressions)
  • Division always results in an integer (truncated towards zero)
  • All intermediate results fit within a 32-bit signed integer range
  • Each token is either an operator or a valid integer in string format

Assumptions I'm making:

• The input array is non-empty and represents a valid RPN expression
• All operators are binary (they require exactly two operands)
• Division by zero will not occur in valid inputs
• The final result fits within a 32-bit signed integer

Data shape and hidden structure: The input is an array of tokens that form a valid binary expression tree when processed in RPN order. Each operator token reduces the stack size by one (removing two operands, adding one result), making it naturally suited for a stack-based approach where we process tokens left-to-right and maintain operands on a stack until we can compute a result.

The structure is inherently sequential but has a hierarchical nature that can be represented as a binary tree where each operator node has exactly two children (the last two operands processed), and the final result is the root value of this implicit tree.

2. Pattern Recognition

The most likely pattern here is stack-based evaluation with postfix notation processing.

The wording that signals this pattern includes:

• "Reverse Polish Notation" - This is a well-known postfix expression format where operators come after their operands
• "Evaluate" - Indicates we need to compute a result from a sequence of tokens
• The mathematical nature of the problem - Operations on numbers following standard arithmetic rules

This problem fits the stack pattern because:

1. We process tokens sequentially from left to right
2. When we encounter operands (numbers), we push them onto a stack
3. When we encounter operators (+, -, *, /), we pop the required number of operands from the stack, perform the operation, and push the result back
4. The final result is the only element remaining on the stack

The core insight needed to solve it is recognizing that Reverse Polish Notation naturally maps to a stack-based evaluation algorithm where:

• Operands are pushed onto the stack
• Operators pop operands, compute result, and push back to stack
• The stack acts as our working memory for intermediate calculations

This pattern is fundamental in computer science and appears in many expression evaluation problems, making it a classic stack application.

The key insight is that we don't need to parse or build expression trees - we can directly evaluate using a stack, which makes this problem amenable to a clean, efficient solution with O(n) time and O(n) space complexity.

3. Approach Evolution

My first instinct is to use a stack-based approach because this problem naturally exhibits the LIFO (Last In, First Out) pattern - we're processing tokens sequentially and need to maintain context of previous operations. But that's O(n²) in worst-case scenarios if we're repeatedly scanning or reprocessing elements, so let me think about how to optimize this.

Looking at the problem more carefully, I notice that each operation in RPN involves taking the last two operands and applying an operator to them. This is a classic stack pattern where we push operands onto the stack and pop when we encounter an operator. The key insight is that we can process tokens in a single pass, maintaining the stack invariant where it always contains the operands ready for the next operator.

Let me think about this more systematically:

1. Brute Force Approach: For each operator, we'd need to look back in our data structure to find the last two operands. This would require O(n) lookup for each operator, making it O(n²) overall.

2. Optimized Stack Approach: We can process tokens linearly and maintain a stack where operands are pushed, and operators pop the last two operands to compute a result that gets pushed back. This gives us O(n) time complexity.

3. Key Optimization: The stack invariant is that it always contains the operands in the correct order for subsequent operations. When we encounter an operator, we know exactly which two elements to pop (the last two in the stack), and we push the result back.

The core insight is that Reverse Polish Notation is designed to eliminate the need for operator precedence and parentheses - each operator immediately operates on the two most recent operands. This makes stack processing the natural choice.

My approach will be to iterate through each token, push operands onto a stack, and when encountering an operator, pop the last two operands, compute the result, and push it back. This maintains a clean invariant: the stack always contains valid operands ready for the next operator.

The algorithm will process tokens left-to-right in a single pass, with O(n) time complexity and O(n) space complexity for the stack. This is optimal since we must process each token at least once and may need to store intermediate results.

Important invariants that must hold:

• Stack always contains valid operands (no invalid operations)
• When we encounter an operator, stack has at least 2 elements
• Final result is the only element remaining in the stack

4. Data Structure Choice

For evaluating Reverse Polish Notation (RPN), I'll use a Stack as my primary data structure.

Primary Data Structures Used

1. Stack - The main data structure for evaluating RPN expressions
   • Used to store operands as we process tokens from left to right
   • Supports efficient push/pop operations for the stack-based evaluation algorithm
   • Allows easy access to the most recent operands when encountering operators

Why This Choice Is Optimal

The stack is the natural choice for RPN evaluation because:

• RPN naturally follows LIFO (Last In, First Out) principles
• Each operator consumes the two most recent operands from the stack
• The final result is always at the top of the stack
• Stack operations (push/pop) are O(1) time complexity

Time and Space Impact

• Time Complexity: O(n) where n is the number of tokens - each token is processed exactly once
• Space Complexity: O(k) where k is the maximum depth of the stack (at most n/2 in worst case)
• Memory Usage: Minimal - only storing integer operands, no additional complex data structures needed

Helper Structure

No additional helper structures are required beyond the stack itself. The stack naturally handles:

• Operand storage and retrieval
• Operator application logic
• Result accumulation

This choice directly enables the clean, intuitive stack-based algorithm that's the standard approach for RPN evaluation, making it both efficient and readable.

Stack<Integer> stack = new Stack<>();

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example: ["2", "1", "+", "3", "*"]

Step 1: Process "2" - Push onto stack: [2] Step 2: Process "1" - Push onto stack: [2, 1]
Step 3: Process "+" - Pop two elements (1, 2), compute 2 + 1 = 3, push result: [3] Step 4: Process "3" - Push onto stack: [3, 3] Step 5: Process "*" - Pop two elements (3, 3), compute 3 * 3 = 9, push result: [9]

Final result is 9.

The algorithm maintains the invariant that at any point, the stack contains operands that are waiting to be consumed by operators. When we encounter an operator, we always have at least two operands available on the stack (this is guaranteed by valid RPN syntax). The stack naturally handles the order of operations through LIFO behavior - the most recent operands are processed first.

Edge cases handled:

• Single element input: Stack has one element, return it
• Operators with fewer than 2 operands (impossible in valid RPN)
• Division by zero (handled by problem constraints)
• Negative numbers: Processed as regular integers

The algorithm terminates correctly because every valid RPN expression has exactly one final result, and we process each token exactly once in left-to-right order.

6. Java Solution

import java.util.*;

public class Solution {
    public int evalRPN(String[] tokens) {
        // Use a stack to evaluate the reverse polish notation
        Stack<Integer> stack = new Stack<>();
        
        // Process each token in the input array
        for (String token : tokens) {
            if (isOperator(token)) {
                // Pop two operands from stack
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                
                // Perform operation based on operator
                switch (token) {
                    case "+":
                        stack.push(operand1 + operand2);
                        break;
                    case "-":
                        stack.push(operand1 - operand2);
                        break;
                    case "*":
                        stack.push(operand1 * operand2);
                        break;
                    case "/":
                        stack.push(operand1 / operand2);
                        break;
                }
            } else {
                // Token is a number, push it onto the stack
                stack.push(Integer.parseInt(token));
            }
        }
        
        // Final result is the only element left in stack
        return stack.pop();
    }
    
    private boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || 
               "*".equals(token) || "/".equals(token);
    }
}

This solution uses a stack-based approach where we process each token from left to right. For operators, we pop the last two operands, perform the operation, and push the result back onto the stack. For numbers, we simply push them onto the stack. The final result is the only remaining element in the stack after processing all tokens.

The key insight is that reverse Polish notation naturally maps to a stack evaluation process where operators act on the most recent operands. The solution handles all valid RPN expressions and correctly processes integer division toward zero as required by the problem constraints.

7. Complexity Analysis

Time Complexity: O(n) where n is the number of tokens in the input array. Each token is processed exactly once, and each stack operation (push/pop) takes O(1) time. The linear traversal of the tokens array forms the dominant factor.

Space Complexity: O(n) in the worst case, which occurs when all tokens are operands and get pushed onto the stack. For example, in an expression like "1 2 3 4 5 + + + +", we'll store all 5 operands before starting to perform operations. The stack size grows linearly with the input size.

The bounds are tight because:

• We must process each token at least once to evaluate the expression
• The stack depth is bounded by the number of operands in the input
• No additional data structures grow with input size beyond the stack

This solution is optimal for the problem as stated. Since we must examine each token to determine whether it's an operand or operator, and we need to maintain state for intermediate calculations, O(n) time complexity is unavoidable. The space complexity is also optimal since we must store operands until they're consumed by operators.

The solution achieves the best possible trade-off between time and space complexity for this evaluation problem, with no room for improvement in either dimension.

8. Edge Cases & Pitfalls

Edge cases that require special handling:

Empty input: An empty array should return 0, though this is typically not a valid RPN expression.

Single element: A single number should return that number directly.

Division by zero: When the divisor is 0, we must handle it properly. The problem statement guarantees valid input, so we don't need to check for this case in our implementation.

Negative numbers: The solution must correctly handle negative operands and results.

Integer overflow: Large intermediate results could overflow Integer.MAX_VALUE or Integer.MIN_VALUE, though the problem constraints typically ensure this won't occur.

Common implementation pitfalls:

1. Incorrect operator precedence: Confusing the order of operands in binary operations (e.g., a op b vs b op a).

2. Stack underflow: Not properly checking that stack has sufficient elements before popping.

3. Type casting issues: Using int instead of long for intermediate calculations can lead to overflow.

4. Misunderstanding operator behavior: For division, we must truncate toward zero (not floor), which requires careful handling.

5. Not validating input: Assuming all tokens are valid operators or integers without proper validation.

6. Incorrect stack management: Not properly handling the case where we have more operands than operators or vice versa.

The solution handles these by:

• Using a stack to maintain proper operand order
• Validating that we have enough operands before applying operators
• Using long for intermediate calculations to prevent overflow
• Properly handling the division truncation toward zero requirement

// Example edge case handling:
// ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
// Should return 22

9. Alternative Approaches

The primary solution uses a stack-based approach which is optimal for this problem. However, there are a few alternative approaches worth considering:

1. Recursive/Tree-Based Evaluation We could build an expression tree where each operator node has two children (the operands) and recursively evaluate the tree. This approach would work but is more complex to implement and has higher space overhead due to the tree structure creation. It's also less efficient since we'd need to traverse the entire tree structure.

2. Two-Pass Approach with Preprocessing Instead of processing tokens in one pass, we could first identify all operators and their operands, then process them in a second pass. This would require additional preprocessing steps and is less elegant than the single-pass stack approach.

3. Functional Programming with Reduce Using Java's Stream API with reduce operations could theoretically work, but it would be less readable and potentially less efficient than the straightforward stack approach. The stack-based solution is more idiomatic for this type of expression evaluation.

4. Queue-Based Approach While less intuitive, we could use a queue to process tokens in FIFO order and maintain intermediate results. However, this would be more complex to implement correctly and wouldn't offer any advantages over the stack-based solution.

The stack-based approach is preferred because it's:

• More intuitive for expression evaluation problems
• Naturally handles operator precedence through the LIFO property
• Space-efficient (O(n) space where n is number of operands)
• Time-efficient (O(n) time complexity)
• Readable and maintainable

The stack solution is the most practical approach for this specific problem, as it directly maps to the natural evaluation process of RPN expressions.

10. Test Cases

import java.util.*;

public class EvaluateReversePolishNotation {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (token.equals("-")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            } else if (token.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
}

The test cases below demonstrate various scenarios including normal operations, edge cases, and boundary conditions:

// Test Case 1: Basic valid expression
// Input: ["2", "1", "+", "3", "*"] 
// Expected Output: 9
// Explanation: ((2 + 1) * 3) = 9

// Test Case 2: Division with truncation toward zero
// Input: ["4", "13", "5", "/", "+"]
// Expected Output: 6
// Explanation: (4 + (13 / 5)) = 6

// Test Case 3: Complex expression with multiple operations
// Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
// Expected Output: 22
// Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22

// Test Case 4: Single element
// Input: ["5"]
// Expected Output: 5

// Test Case 5: Empty array (edge case - should not occur per problem constraints)
// Input: []
// Expected Output: 0 (but this case is invalid according to problem constraints)

// Test Case 6: Negative numbers
// Input: ["-1", "1", "*"]
// Expected Output: -1

// Test Case 7: Division with negative result
// Input: ["7", "-3", "/"]
// Expected Output: -2 (truncates toward zero)

These test cases cover:

• Basic arithmetic operations (+, -, *, /)
• Division truncation behavior (toward zero)
• Complex nested expressions
• Edge cases like single elements and negative numbers
• Boundary conditions for integer overflow (though not explicitly tested since problem constraints limit the input size)

11. Final Summary

The core idea is to evaluate Reverse Polish Notation expressions using a stack-based approach where operands are pushed onto the stack and operators trigger pop operations to perform calculations. This solution works efficiently by processing tokens sequentially and maintaining a clean invariant that the stack contains only valid intermediate results. The approach is optimal with O(n) time complexity and O(n) space complexity, where n is the number of tokens, making it both time and space efficient for this problem's constraints.