Expression Evaluation Algorithms and Techniques

Expression evaluation is a fundamental algorithmic problem that appears frequently in FAANG interviews, requiring robust handling of operator precedence, parentheses, and mathematical operations through stack-based data structures.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we evaluating arithmetic expressions with only basic operators (+, -, *, /) or do we need to handle parentheses and function calls?
2. What is the expected input size range? Will it be bounded or could it be very large?
3. Can we modify the input array/structure in-place, or must we preserve it?
4. Should we return a single numeric result or handle multiple expressions in one input?
5. Are there any specific constraints on operator precedence, such as requiring strict left-to-right evaluation instead of standard PEMDAS?

Restate the pattern or problem type in your own words: The expression evaluation pattern involves parsing and computing arithmetic expressions that contain numbers, operators (+, -, *, /), and potentially parentheses. The challenge lies in correctly handling operator precedence, associativity, and grouping through parentheses while maintaining proper evaluation order.

Clarify the signal words and constraint shape that point to it: Signal words include "evaluate", "compute", "expression", "arithmetic", "mathematical", and "parse". Constraint shapes typically involve:

• Input format: strings or arrays containing numbers and operators
• Operator precedence requirements (e.g., multiplication before addition)
• Parentheses for grouping that override normal precedence
• Need to handle multiple operations in sequence

Note any assumptions you are making: I'm assuming the input will be a valid arithmetic expression with numbers, basic operators (+, -, *, /), and parentheses. I'm also assuming standard operator precedence (PEMDAS/BODMAS) where multiplication/division bind more tightly than addition/subtraction, and parentheses have highest precedence.

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily suited for static scenarios where the complete expression is available upfront. It's not naturally designed for streaming input since we need to parse and understand the entire expression structure before evaluation. For online scenarios, we'd likely want to pre-process or cache parsed structures rather than re-parse each time.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• Explicit mention of mathematical expressions, arithmetic operations, or algebraic notation
• Problems asking to evaluate or parse expressions with operators like +, -, *, /, parentheses
• Requests for handling operator precedence and associativity rules
• Need to convert between infix, postfix, or prefix notation
• Problems involving tokenization of mathematical expressions

Why this pattern fits better than the most common alternatives:

• Unlike brute force parsing or recursive descent, expression evaluation leverages well-established stack-based algorithms that naturally handle operator precedence
• Compared to building custom parsers, the stack-based approach is more maintainable and less error-prone for standard arithmetic expressions
• It's more efficient than repeatedly re-parsing or using string manipulation for complex expressions

Conditions where a variation or related pattern applies instead:

• For very simple expressions without operator precedence (like RPN), stack-based evaluation is still appropriate but simpler
• When dealing with function calls or variables, a more sophisticated AST (Abstract Syntax Tree) approach might be needed
• For streaming input where expressions are built incrementally, a state machine or incremental parser would be more appropriate

The core insight that makes this pattern work: The key insight is that operator precedence can be naturally modeled using a stack-based approach where we process operators in order of increasing precedence, deferring higher-precedence operations until later. When encountering a new operator with lower or equal precedence, we can safely evaluate the previous operator before pushing the current one onto the stack. This creates a clean separation between operand and operator handling, making the algorithm both intuitive and efficient.

This pattern is particularly well-suited for problems where:

1. You're evaluating arithmetic expressions with standard operator precedence rules
2. The input is a well-formed mathematical expression string
3. You need to handle parentheses, unary operators, and mixed operator types
4. The solution should be efficient with O(n) time complexity

3. Approach Evolution

Interview communication script:

My first instinct is to think about how to evaluate expressions with different operators and precedence levels. The most straightforward approach would be to parse the expression character by character, but that's O(n²) in complexity because we'd need to repeatedly scan and restructure the expression as we handle different operator precedences.

Let me think about how to optimize this. I notice that if I maintain the invariant of processing operators in order of precedence, I can reduce it to O(n) time by using a stack-based approach. The key insight is that we can process the expression from left to right, and whenever we encounter an operator with lower precedence than what's already on our stack, we can evaluate the previous operations first.

I'm thinking of using a two-stack approach:

1. One stack for operands (numbers)
2. One stack for operators (+, -, *, /)

When I encounter an operator, I can compare its precedence with the operator at the top of the stack. If the current operator has lower or equal precedence, I can pop and evaluate the previous operation before pushing the current operator.

This approach handles operator precedence correctly, and it's efficient because each element is pushed and popped at most once.

Brute-force approach and why it is not ideal: The brute force approach would be to repeatedly scan the entire expression to find the highest precedence operator, evaluate it, and replace it with the result. This leads to O(n²) time complexity because for each operator we process, we might need to scan the entire remaining expression. Additionally, it's complex to implement because we'd need to manage string manipulations and handle the changing expression structure.

Improved approach and the key optimization: The improved approach uses a stack-based algorithm with operator precedence. The key optimization is that we only process each operator once and maintain a stack of operators in decreasing order of precedence. When we encounter an operator with lower precedence than the top of stack, we can immediately evaluate the previous operation. This ensures that each operator is pushed and popped at most once, giving us O(n) time complexity.

Final approach with step-by-step reasoning:

1. Process the expression from left to right character by character
2. When we encounter a number, push it onto the operand stack
3. When we encounter an operator:
   • While the operator stack is not empty and the top operator has higher or equal precedence, evaluate the previous operation
   • Push the current operator onto the operator stack
4. After processing all characters, evaluate any remaining operations in the stacks
5. The final result is on the operand stack

Important invariants that must hold:

• Operator precedence is maintained (higher precedence operators are evaluated first)
• The operator stack always contains operators in decreasing order of precedence
• Operand stack always contains valid numeric values that can be operated on
• Each operator is processed exactly once, ensuring O(n) time complexity

4. Data Structure Choice

For expression evaluation, I'll use a stack-based approach with two main data structures:

Primary Data Structures

1. Stack - for operands (numbers)

   • Why needed: Expression evaluation requires backtracking to compute intermediate results
   • Time/space impact: O(n) space where n is the number of operands, O(1) for push/pop operations
   • Essential for handling operator precedence and parentheses

2. Stack - for operators

   • Why needed: To manage operator precedence and handle nested parentheses
   • Time/space impact: O(n) space where n is the number of operators, O(1) for push/pop operations
   • Enables efficient operator ordering during evaluation

Helper Structures

3. HashMap<Character, Integer> - for operator precedence mapping
   • Why needed: To quickly determine which operator has higher precedence during evaluation
   • Time/space impact: O(1) lookup time, O(1) space (constant 4 operators)
   • Simplifies the logic for operator comparison

Why This Choice Works

The stack-based approach is optimal because:

• It naturally handles the LIFO (Last In, First Out) nature of expression evaluation
• Parentheses can be managed by pushing and popping operator stacks appropriately
• Operator precedence is naturally enforced through stack operations
• The solution is clean and avoids complex recursive parsing

Alternative approaches like using a queue or tree-based parsing would be more complex to implement and maintain, while stacks provide the perfect abstraction for this specific problem pattern.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example: "(2 + 6) * 3 - 1".

Step 1: Initialize stacks - operatorStack = [], operandStack = []

Step 2: Process '(' - Push to operator stack

• operatorStack = ['(']
• operandStack = []

Step 3: Process '2' - Push to operand stack

• operatorStack = ['(']
• operandStack = [2]

Step 4: Process '+' - Push to operator stack

• operatorStack = ['(', '+']
• operandStack = [2]

Step 5: Process '6' - Push to operand stack

• operatorStack = ['(', '+']
• operandStack = [2, 6]

Step 6: Process ')' - Evaluate the subexpression

• Pop +, 6, 2 from stacks
• Calculate 2 + 6 = 8
• Push 8 back to operand stack
• Pop '(' from operator stack (remove matching parenthesis)
• operatorStack = []
• operandStack = [8]

Step 7: Process '*' - Push to operator stack

• operatorStack = ['*']
• operandStack = [8]

Step 8: Process '3' - Push to operand stack

• operatorStack = ['*']
• operandStack = [8, 3]

Step 9: Process '-' - Process * operator first (higher precedence), then push -

• Pop '*', 3, 8 from stacks
• Calculate 8 * 3 = 24
• Push 24 back to operand stack
• Push '-' to operator stack
• operatorStack = ['-']
• operandStack = [24]

Step 10: Process '1' - Push to operand stack

• operatorStack = ['-']
• operandStack = [24, 1]

Step 11: Process end of string - Evaluate remaining operators

• Pop '-', 1, 24 from stacks
• Calculate 24 - 1 = 23
• Push 23 back to operand stack
• operatorStack = []
• operandStack = [23]

Final Result: Return the last value in operand stack: 23

The key insight is that we process operators based on precedence, handling parentheses as subexpressions that must be resolved before continuing. The algorithm maintains the invariant that operands are only evaluated when their operators have higher or equal precedence, and parentheses ensure proper grouping.

6. Java Solution

import java.util.*;

public class ExpressionEvaluator {
    
    public int calculate(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int num = 0;
        char operator = '+'; // Initialize to '+' to handle first number
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                // Build the current number
                num = num * 10 + (c - '0');
            }
            
            // Process when we encounter an operator or reach the end
            if (c == '+' || c == '-' || c == '*' || c == '/' || i == s.length() - 1) {
                // Apply the previous operator to the current number
                switch (operator) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    case '/':
                        stack.push(stack.pop() / num);
                        break;
                }
                
                // Reset for next number
                operator = c;
                num = 0;
            }
        }
        
        // Sum all values in the stack
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}

This solution uses a stack-based approach to handle operator precedence correctly. The key insight is that we can defer multiplication and division operations until we've processed the entire expression, while immediately applying addition and subtraction. When we encounter a multiplication or division operator, we pop the previous number from the stack, perform the operation, and push the result back. This ensures proper precedence handling without needing to parse the entire expression first.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input string.

The algorithm processes each character in the input string exactly once, performing constant-time operations for each character. The stack operations (push/pop) are O(1) amortized, and we never revisit or reprocess characters. The linear scan through the string dominates the time complexity.

Space Complexity: O(n) in the worst case for the stack.

In the worst case (e.g., all opening parentheses or operators), the stack may contain up to n/2 elements, where n is the length of the input string. This occurs when we have nested expressions or a long sequence of operators without matching closing brackets. The space complexity is linear with respect to input size.

Why these bounds are correct:

• Time: Each character is processed once, and all operations (stack push/pop, arithmetic) are constant time. The linear scan is the dominant factor.
• Space: The stack size is bounded by the number of unmatched opening parentheses or operators, which can be at most n/2 in pathological cases.

Optimality: This solution is optimal for the expression evaluation problem with parentheses and basic arithmetic operators. We must read each character at least once to determine the correct evaluation order, making O(n) time complexity unavoidable. The space complexity is also optimal since we need to store intermediate results in the stack for proper operator precedence handling.

The solution achieves the best possible complexity trade-off between time and space for this problem, avoiding any unnecessary operations or redundant data structures.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input: Should return 0 or handle gracefully depending on requirements
• Single operand: Should return that operand value
• Single operator: May be invalid input (e.g., just "+" or "-")

Duplicate Values and Repeated States

• Consecutive operators: Need to handle cases like "1++2" or "3--4"
• Repeated operands: Valid but must be processed correctly (e.g., "2+2+2" = 6)
• Multiple consecutive operators: Should either reject or handle with appropriate logic

Boundary Conditions

• Integer overflow: Large numbers can cause overflow in intermediate calculations
• Division by zero: Must handle when denominator is 0 (e.g., "5/0")
• Negative numbers: Must properly handle unary minus vs binary minus
• Leading/trailing whitespace: Should typically be ignored but must be handled consistently

Common Implementation Mistakes

• Incorrect operator precedence: Adding before multiplying when multiplication has higher precedence
• Not handling operator precedence properly: Using stack-based approach without proper precedence logic
• Missing parentheses handling: Failing to account for nested or grouped operations
• Improper stack management: Not maintaining proper state during expression parsing
• Integer overflow without bounds checking: Using int instead of long and not handling large intermediate results

Additional Considerations

• Invalid character handling: Non-numeric, non-operator characters should be handled gracefully
• Empty operator sequences: "1 + * 2" or "1 / / 3" should be detected and handled
• Unary vs binary operator ambiguity: "-" can be unary (negative) or binary (subtract)
• Floating point operations: If supporting decimals, must handle precision issues

9. Alternative Approaches

There are several alternative approaches to expression evaluation, each with different trade-offs:

Recursive Descent Parser: This approach builds a parse tree by recursively parsing the expression according to grammar rules. It's more intuitive for complex expressions with operator precedence and parentheses, but requires more code and can be less efficient due to function call overhead. The recursive structure makes it easier to extend for additional operators or functions.

Two-Stack Approach: Instead of using a single stack, we can maintain two stacks - one for operands and one for operators. This approach processes the expression left-to-right, pushing operands to the operand stack and operators to the operator stack. When we encounter an operator with lower precedence, we pop and evaluate from the stacks. This is more intuitive for some developers but requires careful handling of operator precedence and can be less efficient due to multiple stack operations.

Shunting Yard Algorithm: This classic algorithm converts infix notation to postfix (RPN) first, then evaluates the postfix expression. It's mathematically elegant and handles complex operator precedence rules well. However, it requires two passes through the input and additional memory for the output queue.

Direct Evaluation with Operator Precedence: For simple arithmetic expressions, we can implement direct evaluation by handling operator precedence explicitly in a single pass. This is the most efficient approach for basic arithmetic but becomes unwieldy with complex expressions or additional operators.

The chosen stack-based approach is preferred because it's clean, readable, and handles operator precedence naturally while maintaining O(n) time and space complexity. It's particularly well-suited for problems where we need to support multiple operator types and parentheses, making it more maintainable than the two-stack or recursive approaches for such cases.

10. Test Cases

public class ExpressionEvaluatorTestCases {
    // Basic arithmetic operations
    @Test
    public void testBasicOperations() {
        assertEquals(14, evaluate("2 + 3 * 4"));
        assertEquals(20, evaluate("(2 + 3) * 4"));
        assertEquals(10, evaluate("10 - 2 * 3 + 4"));
    }
    
    // Complex nested expressions
    @Test
    public void testNestedExpressions() {
        assertEquals(100, evaluate("((2 + 3) * 4) + (5 * 10)"));
        assertEquals(25, evaluate("((10 - 5) * (3 + 2))"));
    }
    
    // Division and modulo operations
    @Test
    public void testDivisionOperations() {
        assertEquals(5, evaluate("15 / 3"));
        assertEquals(2, evaluate("17 % 3"));
        assertEquals(4, evaluate("20 / (2 + 3)"));
    }
    
    // Negative numbers and unary minus
    @Test
    public void testNegativeNumbers() {
        assertEquals(-5, evaluate("-2 + -3"));
        assertEquals(10, evaluate("15 + -5"));
        assertEquals(-2, evaluate("-10 / 5"));
    }
    
    // Complex expression with mixed operators
    @Test
    public void testComplexMixedOperators() {
        assertEquals(14, evaluate("2 * 3 + 8 / 2"));
        assertEquals(15, evaluate("(2 + 3) * (4 - 1)"));
        assertEquals(7, evaluate("10 - 3 * 2 + 1"));
    }
    
    // Expression with only one number
    @Test
    public void testSingleNumber() {
        assertEquals(42, evaluate("42"));
        assertEquals(-15, evaluate("-15"));
    }
    
    // Expression with whitespace
    @Test
    public void testWhitespaceHandling() {
        assertEquals(10, evaluate(" 2 + 3 * 2 "));
        assertEquals(15, evaluate(" ( 2 + 3 ) * 3 "));
    }
    
    // Division by zero (should throw exception)
    @Test(expected = ArithmeticException.class)
    public void testDivisionByZero() {
        evaluate("10 / 0");
    }
    
    // Invalid expression (should throw exception)
    @Test(expected = IllegalArgumentException.class)
    public void testInvalidExpression() {
        evaluate("2 + * 3");
    }
}

11. Final Summary

The core idea is to evaluate mathematical expressions with proper operator precedence and parentheses handling using a stack-based approach that processes operators and operands in the correct order. This solution works efficiently by leveraging the stack's LIFO property to handle nested parentheses and operator precedence, making it optimal for expression evaluation problems with O(n) time complexity where n is the length of the input string. The key insight is that we can process expressions in a single pass while maintaining proper evaluation order through strategic stack operations and precedence checks.