← ~/lc-grind/posts

#224 - Basic Calculator

October 23, 2025

Basic Calculator

Problem Description

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:


Input: s = "1 + 1"
Output: 2

Example 2:


Input: s = " 2-1 + 2 "
Output: 3

Example 3:


Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

Solution

1. Problem Deconstruction

Technical Restatement
Implement a deterministic finite-state machine that processes a token stream (digits, operators, parentheses) from left to right while maintaining:

  • Operator precedence (parentheses override default left-to-right evaluation)
  • Sign inheritance (unary ‘-’ propagates through parentheses)
  • State persistence across scope boundaries via stack-based context switching

Beginner-Friendly Version
Imagine you’re reading a math problem with numbers, plus/minus signs, and parentheses. You need to calculate the answer by:

  1. Solving everything inside parentheses first
  2. Remembering that minus signs can apply to entire groups like “-(2+3)”
  3. Combining numbers from left to right while respecting parentheses

Mathematical Formulation
Let E be the expression grammar:
E → E + T | E - T | T
T → (E) | number
where number ∈ ℤ (32-bit bounded)

Evaluation function f(s):
f(s) = ∑(signᵢ × valueᵢ) where signᵢ ∈ {-1,1} determined by:

  • Preceding operator sequence parity
  • Parenthetical context nesting depth

Constraint Analysis

  • 1 ≤ s.length ≤ 3×10⁵:
    → Linear time solution required (O(n) or O(n log n))
    → Character-by-character processing essential
  • Valid expression guarantee:
    → No input validation needed
    → Parentheses always balanced
  • ‘+’ not unary but ‘-’ can be unary:
    → State machine must track “expecting operand” vs “expecting operator”
    → “-” at expression start or after “(” triggers unary mode
  • No consecutive operators:
    → Simplified state transitions
    → No need to handle “–” → “+” transformations
  • 32-bit integer bounds:
    → No big integer handling
    → Intermediate calculations safe in 64-bit

2. Intuition Scaffolding

Real-World Metaphor
Imagine calculating a restaurant bill with:

  • Regular items (positive numbers)
  • Discounts (negative numbers)
  • Combo meals (parentheses grouping)
  • Coupons that apply to entire combos (unary minus)

Gaming Analogy
Like managing character stats in RPG:

  • Base stats (numbers)
  • Buffs/debuffs (signs)
  • Equipment sets (parentheses)
  • Curse spells that invert all bonuses (unary minus)

Math Analogy
Vector summation with dimension changes:

  • Numbers = vector magnitudes
  • Operators = direction changes
  • Parentheses = temporary coordinate system rotations
  • Unary minus = 180° phase shift

Common Pitfalls

  1. Naive left-to-right without parentheses handling:
    1-(2+3) → 1-2+3 = 2 ❌ (should be -4)
  2. Misidentifying unary minus:
    -1+2 → ❌ “Missing operand” error
  3. Overcomplicating with full operator precedence:
    Unnecessary for only +,- operators
  4. Stack overflow from deep recursion:
    → Iterative stack safer for 3×10⁵ input
  5. Number accumulation errors:
    Multi-digit numbers require base-10 parsing

3. Approach Encyclopedia

Brute Force (Theoretical)

def calculate(s):
    # Repeatedly evaluate innermost parentheses
    while '(' in s:
        i = s.rindex('(')
        j = s.index(')', i)
        s = s[:i] + str(calculate(s[i+1:j])) + s[j+1:]
    return eval(s.replace(' ',''))  # Violates constraint but illustrates

Time: O(n²) from repeated string slicing
Space: O(n) from recursion stack

Two-Stack Approach (Optimal)

def calculate(s):
    stack = []
    num = 0
    sign = 1
    result = 0
    
    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char in '+-':
            result += sign * num
            num = 0
            sign = 1 if char == '+' else -1
        elif char == '(':
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif char == ')':
            result += sign * num
            result *= stack.pop()  # sign
            result += stack.pop()  # previous result
            num = 0
    
    return result + sign * num

Complexity Proof

  • Time: O(n)
    Each character processed exactly once:
    Digit → O(1) arithmetic
    Operator → O(1) stack operations
    Parentheses → O(1) push/pop
    ∑(char_processing_time) = n × O(1) = O(n)

  • Space: O(d) where d = maximum parentheses depth
    Worst-case: (((...))) → O(n) stack space
    Expected: Balanced expressions → O(log n) depth

Visualization

Input: "1 + (2 - (3 + 4))"

Char  Stack       Result  Sign  Num
'1'   []          0       1     1
'+'   []          1       1     0
'('   [1,1]       0       1     0
'2'   [1,1]       0       1     2
'-'   [1,1]       2      -1     0
'('   [1,1,2,-1]  0       1     0
'3'   [1,1,2,-1]  0       1     3
'+'   [1,1,2,-1]  3       1     0
'4'   [1,1,2,-1]  3       1     4
')'   [1,1]       2+(-1*(3+4)) = -5
')'   []          1+(1*(-5)) = -4

4. Code Deep Dive

def calculate(s: str) -> int:
    stack = []          # Stores intermediate results and signs
    num = 0             # Accumulates multi-digit numbers
    sign = 1            # 1 for positive, -1 for negative
    result = 0          # Running total
    
    for char in s:
        if char.isdigit():
            # Number accumulation: "123" → 1→12→123
            num = num * 10 + int(char)
        
        elif char in '+-':
            # Finalize current number with previous sign
            result += sign * num
            num = 0  # Reset number accumulator
            # Update sign for next operand
            sign = 1 if char == '+' else -1
        
        elif char == '(':
            # Push current context before entering parentheses
            stack.append(result)
            stack.append(sign)
            # Reset for sub-expression evaluation
            result, sign = 0, 1
        
        elif char == ')':
            # Finalize sub-expression
            result += sign * num
            num = 0
            # Apply parentheses context: result = parent_sign * result + parent_value
            result *= stack.pop()  # Parentheses sign
            result += stack.pop()  # Previous running total
    
    # Handle trailing number without operator
    return result + sign * num

Edge Case Handling

  • Example 1 “1 + 1”:
    First ‘1’ → num=1, ‘+’ → result=1, sign=1
    Second ‘1’ → num=1, end → return 1 + 1*1 = 2 ✓

  • Example 2 " 2-1 + 2 ":
    Spaces skipped, ‘2’ → num=2, ‘-’ → result=2, sign=-1
    ‘1’ → num=1, ‘+’ → result=2+(-11)=1, sign=1
    ‘2’ → num=2, end → return 1 + 1    2 = 3 ✓

  • Example 3 “(1+(4+5+2)-3)+(6+8)”:
    Handles nested parentheses via stack pushes/pops
    Final stack state ensures correct sign propagation ✓

  • Unary minus “-1”:
    Initial sign=-1, num=1 → result=0 + (-1)*1 = -1 ✓

5. Complexity War Room

Hardware-Aware Analysis

  • 3×10⁵ characters ≈ 300KB string data
  • Stack depth ~100 in worst-case (theoretical maximum: 150,000 but practically limited)
  • L1 cache typically holds ~32KB → streaming processing optimal
  • Branch prediction friendly: 90%+ characters are digits/spaces

Industry Comparison Table

Approach Time Space Readability Interview Viability
Brute Force O(n²) O(n) 8/10 ❌ Fails large N
Recursive Descent O(n) O(n) 7/10 ⚠️ Stack overflow risk
Two-Stack O(n) O(d) 9/10 ✅ Optimal
Shunting Yard O(n) O(n) 6/10 ⚠️ Overkill for +,- only

6. Pro Mode Extras

Variants

  1. Add ×/÷ operators (LC 227):

    # Track last number and operator precedence
if last_operator in '*/':
     stack[-1] = stack[-1] * num if last_operator == '*' else stack[-1] // num

  2. Variables support (LC 770):

    # Use dictionary to track variable coefficients
{'x': 2, '': 3} represents 2x + 3

  3. Expression tree construction:

    # Build AST instead of evaluating
class Node:
     def __init__(self, val, left=None, right=None):
         self.val = val

Interview Cheat Sheet

  • First 2 minutes: Clarify operator set and unary minus behavior
  • Key insight: Parentheses = stack push/pop, Numbers = accumulate then apply sign
  • Testing strategy:
    1. Single number: “42”
    2. Sequential operations: “1-2+3”
    3. Deep nesting: “1-(2-(3-(4-5)))”
    4. Unary minus: “-1+(-2)”
  • Common feedback: Students often forget to reset num=0 after operator