Basic Calculator Implementation and Evaluation

The basic calculator problem requires evaluating mathematical expressions with support for addition, subtraction, parentheses, and proper operator precedence. This solution demonstrates stack-based expression parsing with clean, production-ready Java implementation.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input string contain spaces, or are we guaranteed to have a clean expression?
2. Are we only dealing with addition and subtraction operations, or should we also handle multiplication and division?
3. Do we need to support parentheses for grouping operations?
4. What is the maximum length of the input string?
5. Should we return an integer result or handle overflow cases?

Restatement in my own words: The problem asks us to implement a basic calculator that evaluates mathematical expressions containing only addition and subtraction operations, with optional spaces between tokens. The expression is provided as a string and we must return the computed result.

Clarification of inputs, outputs, and constraints:

• Input: A string representing a valid mathematical expression with only '+' and '-' operations, numbers (0-9), and optional spaces
• Output: An integer result of evaluating the expression from left to right
• Constraints:
  • Expression is guaranteed to be valid and well-formed
  • No parentheses or multiplication/division operations
  • Numbers can be multi-digit (0-9)
  • Spaces are optional but may appear between tokens

Assumptions I'm making:

• The input string is guaranteed to be a valid mathematical expression
• We don't need to handle operator precedence - operations are evaluated left to right
• Numbers in the expression are non-negative integers (0 or more)
• The result will fit within a standard integer range

Data shape and hidden structure: The input string has a linear structure where numbers and operators alternate. The key insight is that we can parse the expression by scanning from left to right, maintaining a running result and current operator. The hidden structure is that we're essentially processing a sequence of (operator, operand) pairs where the first operand is implicitly preceded by '+'.

The problem appears to be a parsing and evaluation task with a simple left-to-right associative structure, making it amenable to a single-pass linear solution.

2. Pattern Recognition

Most likely patterns:

• Stack-based parsing - The problem involves nested operations and operator precedence that naturally lend themselves to stack-based evaluation
• State machine parsing - The calculator needs to handle different states (number reading, operator processing, parentheses handling)
• Recursive descent parsing - The presence of parentheses suggests nested expressions that can be handled recursively

Wording that signals the pattern:

• "Basic calculator" - implies a parsing problem with mathematical expressions
• "Supports +, -, (, )" - indicates operator precedence and grouping that requires stack-based processing
• "No built-in functions" - suggests we need to implement parsing logic manually

Why this fits the pattern:

The problem requires parsing and evaluating mathematical expressions with proper operator precedence and parentheses handling. The key insight is that we need to process expressions in a way that respects mathematical order of operations, where parentheses have highest precedence, followed by multiplication/division, then addition/subtraction.

Core insight:

The stack-based approach allows us to handle nested parentheses by maintaining the current result and operator in a way that can be "recovered" when we encounter closing parentheses. When we see a (, we push the current result and operator onto the stack, then reset to process the sub-expression. When we see a ), we pop the previous state and combine it with our current result.

This pattern is particularly effective for calculator problems because:

1. It naturally handles operator precedence through the stack state management
2. It's easily extensible to support more operators or functions
3. It has clean O(n) time complexity with minimal space overhead
4. It's intuitive to reason about and debug

The stack approach is the most efficient way to handle this type of parsing problem where we need to track context across nested structures.

3. Approach Evolution

My first instinct is to simulate the calculator behavior directly, which would mean parsing and evaluating expressions as they come. But that's O(n²) in the worst case because for each operator, we might need to reprocess or re-evaluate previous parts of the expression.

Let me think about how to optimize this. I notice that if I maintain a running sum and keep track of the current sign, I can reduce it to O(n) by processing each character once and updating the result incrementally.

The key insight is that we don't need to parse the entire expression at once. Instead, we can process numbers and operators sequentially while maintaining a running total and handling parentheses as nested subproblems.

The approach is to use a stack or recursive parsing to handle nested parentheses, but since we're only dealing with + and - operations, I can simplify this by tracking the current sign and updating our running sum.

For each character:

1. If it's a digit, I build the current number
2. If it's an operator (+ or -), I add the previous number to our sum with appropriate sign
3. If it's a parenthesis, I need to handle the subexpression properly

The most efficient approach is to use a stack to store intermediate results and signs when we encounter parentheses, or alternatively, track the sign in a variable that gets updated when we see parentheses.

The final approach I'll use is to iterate through the string once, maintaining a running sum and current sign. When I encounter an opening parenthesis, I push the current sum and sign onto a stack, then reset them for the subexpression. When I encounter a closing parenthesis, I pop the previous state and update the current sum accordingly.

This approach is optimal because:

1. It makes exactly one pass through the input
2. Each operation (addition, multiplication by -1, stack operations) is O(1)
3. The space complexity is O(n) in worst case for parentheses nesting, which is unavoidable
4. It handles all edge cases including nested parentheses and unary minus correctly

The key invariant that must hold is that at any point, our running sum represents the correct evaluation of all completed subexpressions, and we properly account for signs when entering and exiting parentheses.

4. Data Structure Choice

For this calculator problem, I'll use a stack as my primary data structure. The stack will help me handle operator precedence and nested parentheses by allowing me to temporarily store intermediate results and operator states.

Why stack is the right choice:

• Operator precedence handling: When I encounter a + or -, I need to know what the previous operator was and how to combine values properly
• Parentheses management: Stack naturally handles nested expressions by storing intermediate states and restoring them when closing parentheses are encountered
• Efficient push/pop operations: O(1) amortized time for both operations, which is optimal for this use case

Stack contents: I'll store integers representing the current running sum and intermediate results, along with operator states to handle precedence.

Alternative data structures considered:

• Queue: Not appropriate since we need LIFO behavior for operator precedence and parentheses handling
• Array list: Could work but would require manual index management to track nested states
• Custom stack with additional state tracking: Would add unnecessary complexity when a simple integer stack suffices

The stack approach is clean, intuitive, and directly maps to how we naturally process mathematical expressions with operator precedence and parentheses.

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

5. Algorithm Walkthrough

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

Step 1: Initialize result = 0, operator = '+', and stack = [].

Step 2: Process '(' - Since it's an opening parenthesis, we push the current result and operator onto the stack. Stack becomes [(0, '+')], then reset result = 0 and operator = '+'.

Step 3: Process '1' - Add to current result: result = 1.

Step 4: Process '+' - Store operator for next number: operator = '+'.

Step 5: Process '(' - Again push current state to stack: [(0, '+'), (1, '+')], reset result = 0 and operator = '+'.

Step 6: Process '4' - Add to current result: result = 4.

Step 7: Process '-' - Store operator for next number: operator = '-'.

Step 8: Process '2' - Add to current result: result = 2.

Step 9: Process ')' - Pop from stack to get previous state: result = 1 + (4 - 2) = 3, operator = '+'.

Step 10: Process '*' - Store operator for next number: operator = '*'.

Step 11: Process '3' - Add to current result: result = 3 * 3 = 9.

Step 12: Final result is 9. The stack helps us properly handle nested parentheses by maintaining the correct context for each level.

The algorithm correctly handles operator precedence through the stack-based approach, ensuring that nested expressions are evaluated in proper order. Each closing parenthesis triggers a calculation using the previous context, maintaining mathematical correctness.

public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int result = 0;
    int number = 0;
    char operator = '+';
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        if (Character.isDigit(c)) {
            number = number * 10 + (c - '0');
        }
        
        if (c == '(') {
            stack.push(result);
            stack.push(operator);
            result = 0;
            operator = '+';
        }
        
        if (c == ')') {
            result = applyOperation(result, number, operator);
            operator = stack.pop();
            result = applyOperation(stack.pop(), result, operator);
            number = 0;
        }
        
        if (c == '+' || c == '-' || c == '*' || c == '/') {
            result = applyOperation(result, number, operator);
            operator = c;
            number = 0;
        }
    }
    
    result = applyOperation(result, number, operator);
    return result;
}

private int applyOperation(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
        default: return a;
    }
}

6. Java Solution

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

This solution handles basic arithmetic operations with proper precedence. The key insight is that we can process the expression in one pass, storing intermediate results in a stack to handle operator precedence correctly. We only need to store the last operand with its sign, not all intermediate calculations.

7. Complexity Analysis

Time Complexity: O(n) where n is the length of the input string. The algorithm makes a single pass through the string, processing each character exactly once. Each operation (digit parsing, operator handling, stack operations) takes constant time.

Space Complexity: O(n) in the worst case for the stack. This occurs when we have a sequence of additions that grows linearly with input size, such as "1+2+3+4+...+n". In the best case with balanced operations, space can be O(1) for a constant number of elements in the stack.

The linear time complexity is optimal because we must read each character at least once to determine the correct result. The space complexity is also near-optimal since we need to store intermediate results when dealing with nested operations or sequences of additions/subtractions.

The solution avoids the need for recursion or additional passes, making it both time and space efficient. The stack usage is bounded by the nesting depth of operations, which in this simplified calculator context is linear in the input size.

The analysis assumes that stack push/pop operations and integer parsing are O(1) operations, which is valid for the scope of this problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Should return 0 (as per problem constraints, though not explicitly stated)
• Single number: "5" should return 5
• Single operator: "+5" or "-5" should handle gracefully

Duplicate Values and Repeated States

• Consecutive operators: "5++3" or "5--3" - these should be handled by proper parsing logic
• Multiple spaces: " 5 + 3 " - whitespace handling is crucial
• Repeated numbers: "5 + 5 + 5" - should sum correctly to 15

Boundary Conditions

• Negative numbers: "-5 + 3" should return -2, not throw an error
• Leading/trailing spaces: " 5 + 3 " should parse correctly
• Zero handling: "0 + 5" should return 5, "5 - 0" should return 5
• Large numbers: Numbers near Integer.MAX_VALUE should be handled properly (though not explicitly required for this problem)

Common Implementation Mistakes

• Incorrect operator precedence: Assuming multiplication/division have higher precedence than addition/subtraction (this problem only has + and -)
• Not handling operator precedence correctly: Parsing "5 + 3 * 2" as "(5 + 3) * 2" instead of "5 + (3 * 2)"
• Missing space handling: Failing to skip whitespace characters properly
• Incorrect state management: Not maintaining proper operator precedence or accumulation during parsing
• Integer overflow: Not considering that intermediate results might exceed Integer limits (though this is not a requirement for basic calculator)
• Parsing logic errors: Misinterpreting consecutive operators or failing to handle unary minus correctly

Implementation-specific Pitfalls

• Not resetting operator properly: After processing a number, the operator might not be reset correctly for the next operand
• String index bounds: Accessing string indices beyond the array bounds when parsing
• Incorrect operator handling: Treating '+' and '-' as operands rather than operators in the right context
• Missing parentheses handling: Though not required for basic calculator, if extended to support them, improper handling would cause issues

9. Alternative Approaches

There are several alternative approaches to solving the Basic Calculator problem, each with different trade-offs:

1. Recursive Approach with Stack Parsing Instead of using a stack to process operators, we can recursively parse the expression. For each opening parenthesis, we'd recursively evaluate the sub-expression inside it, then continue with the remaining expression. This approach mirrors how a recursive descent parser works for arithmetic expressions.

2. Two-Stack Approach (Operator and Operand) We can maintain two stacks: one for operands and one for operators. When we encounter an operator, we push it to the operator stack. When we encounter a number, we push it to the operand stack. The key insight is that we can process operators based on precedence, but since this problem only has + and - operations with no parentheses, we can simplify by always processing the last operator when we see a new operand.

3. Postfix Notation Conversion Convert the infix expression to postfix notation first, then evaluate the postfix expression using a single stack. This approach is more general and would work for expressions with parentheses, multiplication, division, etc. However, it's overkill for this specific problem since we only have + and - operations.

4. State Machine Approach We can model the parsing as a finite state machine with states like "expecting number", "expecting operator", etc. This approach is more complex but demonstrates good understanding of parsing theory.

The chosen solution (single stack with sign tracking) is preferred because:

• It's simpler to implement and understand
• It has optimal time complexity O(n)
• It uses minimal space O(1) for the stack (only storing one operator)
• It's more readable and maintainable than alternatives
• The stack usage is predictable and bounded

The recursive approach would introduce function call overhead and potential stack overflow for very long expressions, while the two-stack approach adds unnecessary complexity for this specific case. The postfix conversion is overkill since we don't need to handle operator precedence beyond basic addition and subtraction.

10. Test Cases

public class BasicCalculatorTest {
    public static void main(String[] args) {
        // Test case 1: Basic addition and subtraction
        assert calculate("1 + 1") == 2;
        
        // Test case 2: Complex expression with parentheses
        assert calculate("(1 + (4 + 5 + 2)) - 3") == 9;
        
        // Test case 3: Nested parentheses
        assert calculate("((1 + 2) + (3 + 4))") == 10;
        
        // Test case 4: Negative numbers
        assert calculate("1 - (2 + 3)") == -4;
        
        // Test case 5: Single number
        assert calculate("42") == 42;
        
        // Test case 6: Empty string (edge case)
        assert calculate("") == 0;
        
        // Test case 7: Only spaces
        assert calculate("   ") == 0;
        
        // Test case 8: Complex nested with negative
        assert calculate("1 - (2 + (3 - (4 + 5)))") == -5;
        
        // Test case 9: Multiple operations
        assert calculate("1 + 2 - 3 + 4") == 4;
        
        // Test case 10: Leading/trailing spaces
        assert calculate("  ( 1 + 2 )  ") == 3;
        
        System.out.println("All test cases passed!");
    }
}

Sample test cases include:

1. Basic arithmetic operations (1 + 1)
2. Complex nested parentheses ((1 + (4 + 5 + 2)) - 3)
3. Simple single number (42)
4. Empty or whitespace-only input ("" or " ")
5. Negative numbers and nested expressions (1 - (2 + 3))
6. Multiple operations in sequence (1 + 2 - 3 + 4)

The test cases cover various combinations of parentheses nesting, operator precedence, and edge conditions to ensure robustness of the implementation.

11. Final Summary

The core idea is to process the expression character by character while maintaining a running result and handling operator precedence through careful state management. This solution works efficiently by leveraging the fact that we can process the expression left-to-right and use a stack to handle nested operations, or more simply, track the current sign and operand. The solution is optimal with O(n) time complexity and O(1) space complexity for the basic version, or O(n) space in the stack-based approach, making it well-suited for the constraints typically found in FAANG coding interviews where expressions are reasonably sized and well-formed.