MANG Problem #15: Basic Calculator II (Hard)

1. Problem Statement

Given a string s which represents an expression, evaluate this expression and return its value.

The expression string contains only non-negative integers, +, -, *, / operators, and empty spaces. The integer division should truncate toward zero.

Input: s = " 3+5 / 2 "
Output: 5

2. Approach: Single Stack & Operator Tracking

Mathematical expressions have Precedence: * and / must be evaluated before + and -.

Initialize: stack to store numbers, currentNumber = 0, and operation = '+'.
Iterate:
- If char is a digit, update currentNumber.
- If char is an operator or end of string:
  - If +: Push currentNumber to stack.
  - If -: Push -currentNumber to stack.
  - If *: Pop from stack, multiply with currentNumber, and push back result.
  - If /: Pop from stack, divide by currentNumber, and push back result.
- Reset currentNumber and update operation.
Sum: The result is the sum of all numbers in the stack.

3. Java Implementation

public int calculate(String s) {
    if (s == null || s.isEmpty()) return 0;
    int len = s.length();
    Stack<Integer> stack = new Stack<>();
    int currentNumber = 0;
    char operation = '+';
    
    for (int i = 0; i < len; i++) {
        char currentChar = s.charAt(i);
        if (Character.isDigit(currentChar)) {
            currentNumber = (currentNumber * 10) + (currentChar - '0');
        }
        if (!Character.isDigit(currentChar) && !Character.isSpaceChar(currentChar) || i == len - 1) {
            if (operation == '-') {
                stack.push(-currentNumber);
            } else if (operation == '+') {
                stack.push(currentNumber);
            } else if (operation == '*') {
                stack.push(stack.pop() * currentNumber);
            } else if (operation == '/') {
                stack.push(stack.pop() / currentNumber);
            }
            operation = currentChar;
            currentNumber = 0;
        }
    }
    
    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: We don't actually need to "wait" to calculate * or /. As soon as we see one, we can immediately apply it to the last number we pushed to the stack.
The Buffer: The operation variable stores the operator that preceded the current number. This is why we initialize it to +.
Space Efficiency: We use a stack to defer the additions and subtractions until the very end, once all high-precedence multiplication and division are resolved.

5. Interview Discussion

Interviewer: "Can we do this without a stack?"
You: "Yes, by maintaining a lastNumber variable. For + and -, we add lastNumber to the total result and update lastNumber. For * and /, we update lastNumber directly. This reduces space from O(N) to O(1)."
Interviewer: "How would you handle parentheses?"
You: "I would use Recursion. Whenever we see (, we call the function recursively to solve the sub-expression. This is the logic used in Basic Calculator III."