Basic Calculator

LeetCode 224: Basic Calculator Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a stack to save the current calculation state (running sum and sign) whenever a parenthesis is encountered, allowing the algorithm to handle nested expressions linearly.

The LeetCode 224 problem, titled "Basic Calculator," asks us to evaluate a mathematical expression string containing non-negative integers, +, -, (, ), and empty spaces. Unlike simple arithmetic, the presence of parentheses introduces changes in precedence and scope that must be handled correctly. The problem explicitly forbids the use of built-in evaluation functions like eval().

This is a popular interview question because it tests a candidate's ability to manage state and parsing logic simultaneously, a core requirement for building parsers or compilers.

Brute Force Approach for Basic Calculator

A naive or brute force approach typically relies on string manipulation to handle parentheses. The algorithm would search for the innermost pair of parentheses, evaluate the sub-expression inside them, and replace the substring with the calculated result. This process repeats until no parentheses remain, reducing the problem to a simple linear scan of additions and subtractions.

Pseudo-code:

while string contains '(':
    find last occurrence of '('
    find first occurrence of ')' after that '('
    extract substring between them
    calculate value of substring (simple + and -)
    replace substring in original string with value
calculate final string

Why it fails: While logically correct, this approach is highly inefficient.

1. String Immutability/Cost: In languages like Java or Python, strings are immutable. Creating a new string for every parenthesis replacement is costly.
2. Time Complexity: Finding the innermost parentheses takes $O(N)$. Shifting characters to replace the substring also takes $O(N)$. Doing this for every pair of nested parentheses results in a time complexity of roughly $O(N^2)$.
3. Result: This will likely trigger a Time Limit Exceeded (TLE) error on large inputs where the string length can go up to $3 \times 10^5$.

Algorithm Strategy: Stack Patterns

We will implement a linear-pass algorithm using a stack and a few variables to track state.

State Variables:

1. stack: Stores the result and sign calculated before encountering a (.
2. current_result: The running total of the expression at the current level of parentheses.
3. current_sign: Represents the sign of the next number (1 for positive, -1 for negative).
4. operand: Used to build multi-digit numbers from the character stream.

The Strategy:

1. Iterate through the string character by character.
2. Digit: If the character is a digit, build the operand. Since numbers can have multiple digits, we multiply the existing operand by 10 and add the new digit.
3. Operator (+ or -):
   • Add the current operand * current_sign to current_result.
   • Reset operand to 0.
   • Update current_sign (1 if +, -1 if -).
4. Open Parenthesis (:
   • Add the current operand * current_sign to current_result (handle any pending number).
   • Push current_result and current_sign onto the stack.
   • Reset current_result to 0 and current_sign to 1. This prepares the state for the new sub-expression.
5. Close Parenthesis ):
   • Add the last operand * current_sign to current_result (finish the sub-expression).
   • Pop the saved sign from the stack and multiply it by current_result.
   • Pop the saved result from the stack and add it to current_result.
   • Reset operand to 0.

Execution Flow

Let's trace s = "1 - (2 + 3)":

1. Init: stack=[], res=0, sign=1, operand=0.
2. Char '1': operand becomes 1.
3. Char ' ': Ignored.
4. Char '-':
   • res += operand * sign $\rightarrow$ res = 0 + 1 * 1 = 1.
   • operand reset to 0.
   • sign becomes -1.
5. Char ' ': Ignored.
6. Char '(':
   • Push: stack.push(res=1), stack.push(sign=-1). (Stack is [1, -1]).
   • Reset: res = 0, sign = 1.
7. Char '2': operand becomes 2.
8. Char ' ': Ignored.
9. Char '+':
   • res += operand * sign $\rightarrow$ res = 0 + 2 * 1 = 2.
   • operand reset to 0.
   • sign becomes 1.
10. Char '3': operand becomes 3.
11. Char ')':
    • res += operand * sign $\rightarrow$ res = 2 + 3 * 1 = 5. (Inner result is 5).
    • Pop Sign: prev_sign = -1. res = res * -1 $\rightarrow$ res = -5.
    • Pop Result: prev_res = 1. res = res + prev_res $\rightarrow$ res = -5 + 1 = -4.
    • operand reset to 0.
12. End: Return res (-4).

Proof of Correctness

The algorithm's correctness relies on the invariant that current_result always holds the evaluated sum of the expression at the current parenthesis depth, excluding the pending operand.

1. Base Case: For simple expressions like A + B, the algorithm adds A to current_result when + is seen, and adds B when the string ends (or another operator appears).
2. Inductive Step (Parentheses): When ( is encountered, the current context (outer sum and sign) is pushed to the stack. The algorithm recursively solves the sub-problem inside the parentheses (which is just another valid expression).
3. Resolution: When ) is encountered, the sub-problem is effectively reduced to a single scalar value. The stack pop operation mathematically performs OuterSum + (OuterSign * InnerSum), which is the algebraic equivalent of distributing the sign and adding the result.

Since the stack depth corresponds to the parenthesis nesting depth, and operations are performed linearly, the final current_result is the correct evaluation of the entire string.

Pattern Reuse Notes

The Stack - Expression Evaluation pattern is highly reusable. Understanding how to manage state (pre-parenthesis vs. inner-parenthesis) is key to solving harder variations.

• LeetCode 150: Evaluate Reverse Polish Notation: Simpler than Basic Calculator because the order of operations is explicit (postfix). You only need a stack for operands, not operators.
• LeetCode 227: Basic Calculator II: Introduces multiplication * and division /. This requires handling operator precedence. You generally push intermediate terms to the stack and sum them up at the end.
• LeetCode 772: Basic Calculator III: Combines everything—parentheses from LC 224 and precedence (*, /) from LC 227. This is the most complex variation and usually requires two stacks (one for operands, one for operators) or recursion.

Reference Implementation

C++ Solution for LeetCode 224

1class Solution {
2public:
3    int calculate(string s) {
4        stack<int> st;
5        int result = 0;
6        int current_val = 0;
7        int sign = 1; // 1 for positive, -1 for negative
8        
9        for (char c : s) {
10            if (isdigit(c)) {
11                // Build the number if it has multiple digits
12                // Check for overflow safety if necessary, though problem says it fits in int
13                if (current_val > INT_MAX / 10 || (current_val == INT_MAX / 10 && (c - '0') > 7)) {
14                     // Handle overflow case if constraints were stricter
15                }
16                current_val = current_val * 10 + (c - '0');
17            } else if (c == '+') {
18                result += sign * current_val;
19                current_val = 0;
20                sign = 1;
21            } else if (c == '-') {
22                result += sign * current_val;
23                current_val = 0;
24                sign = -1;
25            } else if (c == '(') {
26                // Push the result and sign calculated so far onto the stack
27                st.push(result);
28                st.push(sign);
29                // Reset for the inner expression
30                result = 0;
31                sign = 1;
32            } else if (c == ')') {
33                result += sign * current_val;
34                current_val = 0;
35                
36                // Pop the sign before the parenthesis
37                result *= st.top(); 
38                st.pop();
39                
40                // Pop the result calculated before the parenthesis
41                result += st.top();
42                st.pop();
43            }
44        }
45        
46        // Add the last pending value
47        result += sign * current_val;
48        
49        return result;
50    }
51};

Java Solution for LeetCode 224

1class Solution {
2    public int calculate(String s) {
3        Stack<Integer> stack = new Stack<>();
4        int result = 0;
5        int operand = 0;
6        int sign = 1; // 1 means positive, -1 means negative
7
8        for (int i = 0; i < s.length(); i++) {
9            char ch = s.charAt(i);
10
11            if (Character.isDigit(ch)) {
12                // Build the operand (number)
13                operand = operand * 10 + (ch - '0');
14            } else if (ch == '+') {
15                // Evaluate the expression to the left
16                result += sign * operand;
17                sign = 1;
18                operand = 0;
19            } else if (ch == '-') {
20                result += sign * operand;
21                sign = -1;
22                operand = 0;
23            } else if (ch == '(') {
24                // Push the result and sign onto the stack for later
25                stack.push(result);
26                stack.push(sign);
27                // Reset result and sign for the new sub-expression
28                sign = 1;
29                result = 0;
30            } else if (ch == ')') {
31                // Finish the current sub-expression
32                result += sign * operand;
33                
34                // The result inside the () is multiplied by the sign before the (
35                result *= stack.pop();
36                
37                // Then add to the result calculated before the (
38                result += stack.pop();
39                
40                operand = 0;
41            }
42        }
43        
44        // Add the final operand if any
45        return result + (sign * operand);
46    }
47}

Python Solution for LeetCode 224

1class Solution:
2    def calculate(self, s: str) -> int:
3        stack = []
4        current_result = 0
5        operand = 0
6        sign = 1  # 1 for positive, -1 for negative
7        
8        for char in s:
9            if char.isdigit():
10                operand = operand * 10 + int(char)
11            elif char == '+':
12                current_result += sign * operand
13                sign = 1
14                operand = 0
15            elif char == '-':
16                current_result += sign * operand
17                sign = -1
18                operand = 0
19            elif char == '(':
20                # Push the current result and the sign onto the stack
21                stack.append(current_result)
22                stack.append(sign)
23                # Reset the result and sign for the inner expression
24                current_result = 0
25                sign = 1
26            elif char == ')':
27                current_result += sign * operand
28                # Pop sign and multiply with current result
29                current_result *= stack.pop()
30                # Pop the previous result and add
31                current_result += stack.pop()
32                operand = 0
33        
34        return current_result + (sign * operand)