Basic Calculator I, II, III — Complete Expression Evaluation Guide

The Basic Calculator series is a progression of expression evaluation problems. Each level adds complexity:

Problem	Operations	Parentheses	LeetCode
Calculator I	+, -	Yes	224
Calculator II	+, -, *, /	No	227
Calculator III	+, -, *, /	Yes	772

Calculator I: + and - with Parentheses

Evaluate expressions like "(1+(4+5+2)-3)+(6+8)".

The key insight: parentheses change the sign of everything inside them. Track the current sign, and use a stack to save/restore it when entering/leaving parentheses.

def calculate_i(s: str) -> int:
    """
    Basic Calculator I — LeetCode 224.
    Handles: +, -, (, ), spaces, non-negative integers.
    Time: O(n), Space: O(n)
    """
    stack = []
    result = 0
    num = 0
    sign = 1  # 1 for positive, -1 for negative

    for char in s:
        if char.isdigit():
            num = num * 10 + int(char)
        elif char == '+':
            result += sign * num
            num = 0
            sign = 1
        elif char == '-':
            result += sign * num
            num = 0
            sign = -1
        elif char == '(':
            # Save current result and sign
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
        elif char == ')':
            result += sign * num
            num = 0
            # Apply saved sign and add to saved result
            result *= stack.pop()  # saved sign
            result += stack.pop()  # saved result

    return result + sign * num

Trace: "(1+(4+5+2)-3)+(6+8)"

(  → stack=[0, 1], result=0, sign=1
1  → num=1
+  → result=1, sign=1
(  → stack=[0, 1, 1, 1], result=0, sign=1
4  → num=4
+  → result=4, sign=1
5  → result=9, sign=1
+  → result=9, sign=1
2  → num=2
)  → result=11, pop sign=1, pop saved=1 → result=1+11=12
-  → result=12, sign=-1
3  → num=3
)  → result=12-3=9, pop sign=1, pop saved=0 → result=0+9=9
+  → result=9, sign=1
(  → stack=[9, 1], result=0, sign=1
6  → num=6
+  → result=6, sign=1
8  → num=8
)  → result=14, pop sign=1, pop saved=9 → result=9+14=23

Answer: 23 ✓

Calculator II: Four Operations, No Parentheses

Evaluate "3+2*2" → 7. The challenge is operator precedence: * and / bind tighter than + and -.

Strategy: process * and / immediately. Defer + and - by pushing values to a stack.

def calculate_ii(s: str) -> int:
    """
    Basic Calculator II — LeetCode 227.
    Handles: +, -, *, /, spaces, non-negative integers.
    Time: O(n), Space: O(n)
    """
    stack = []
    num = 0
    prev_op = '+'

    for i, char in enumerate(s):
        if char.isdigit():
            num = num * 10 + int(char)

        if (not char.isdigit() and char != ' ') or i == len(s) - 1:
            if prev_op == '+':
                stack.append(num)
            elif prev_op == '-':
                stack.append(-num)
            elif prev_op == '*':
                stack.append(stack.pop() * num)
            elif prev_op == '/':
                # Truncate toward zero (Python gotcha!)
                stack.append(int(stack.pop() / num))
            prev_op = char
            num = 0

    return sum(stack)

Python Division Gotcha

Python’s // truncates toward negative infinity, but this problem requires truncation toward zero:

# Python // behavior
-7 // 2    # = -4 (toward -infinity)

# What we need (toward zero)
int(-7 / 2)  # = -3 ✓

Trace: "3+2*2-1"

prev_op='+', scan:
  '3' → num=3
  '+' → prev_op='+', push 3     stack=[3], prev_op='+'
  '2' → num=2
  '*' → prev_op='+', push 2     stack=[3,2], prev_op='*'
  '2' → num=2
  '-' → prev_op='*', push 2*2=4 stack=[3,4], prev_op='-'
  '1' → num=1
  end → prev_op='-', push -1    stack=[3,4,-1]

sum([3,4,-1]) = 6 ✓

Calculator III: Everything Combined

This is the boss level. Handle +, -, *, / and parentheses. LeetCode 772 (Premium).

Use recursion: when we see (, recursively evaluate until ).

def calculate_iii(s: str) -> int:
    """
    Basic Calculator III — LeetCode 772.
    Handles: +, -, *, /, (, ), spaces.
    Time: O(n), Space: O(n)
    """
    def helper(s, idx):
        stack = []
        num = 0
        prev_op = '+'

        while idx < len(s):
            char = s[idx]

            if char.isdigit():
                num = num * 10 + int(char)

            if char == '(':
                # Recursively evaluate subexpression
                num, idx = helper(s, idx + 1)

            if (not char.isdigit() and char != ' ' and char != '(') \
               or idx == len(s) - 1:
                if prev_op == '+':
                    stack.append(num)
                elif prev_op == '-':
                    stack.append(-num)
                elif prev_op == '*':
                    stack.append(stack.pop() * num)
                elif prev_op == '/':
                    stack.append(int(stack.pop() / num))
                prev_op = char
                num = 0

            if char == ')':
                return sum(stack), idx

            idx += 1

        return sum(stack), idx

    result, _ = helper(s, 0)
    return result

Trace: "2*(3+4)-1"

helper(s, 0):
  '2'  → num=2
  '*'  → push 2, prev_op='*'
  '('  → recurse helper(s, 4)
    helper(s, 4):
      '3' → num=3
      '+' → push 3, prev_op='+'
      '4' → num=4
      ')' → push 4, return (7, 8)
  num=7, prev_op='*' → push 2*7=14    stack=[14]
  '-'  → prev_op='-'
  '1'  → num=1
  end  → push -1                       stack=[14,-1]

sum([14,-1]) = 13 ✓

Complexity Summary

Problem	Time	Space	Key Technique
Calculator I	O(n)	O(n)	Sign tracking with stack
Calculator II	O(n)	O(n)	Immediate * and /, deferred + and -
Calculator III	O(n)	O(n)	Recursion for parentheses + Calculator II logic

Edge Cases

# Single number
assert calculate_i("42") == 42

# Spaces everywhere
assert calculate_ii(" 3 + 2 * 2 ") == 7

# Leading negative (Calculator I)
# Note: "-(1+2)" → result = -(3) = -3

# Division truncation toward zero
assert calculate_ii("14-3/2") == 13  # 14 - 1 = 13

# Nested parentheses
assert calculate_iii("((2+3)*4)") == 20

# Empty parentheses edge
assert calculate_iii("1+(2*3)") == 7

When to Use This Pattern

• Expression evaluation: Parsing mathematical or logical expressions
• Compiler design: The tokenize-evaluate pattern is fundamental to parsers
• Spreadsheet engines: Cell formula evaluation uses this exact approach
• Configuration languages: Evaluating expressions in config files

Common Interview Tips

1. Always clarify which operators and features are supported
2. Handle spaces explicitly — skip them during parsing
3. Watch for Python’s integer division behavior
4. Test with single numbers, nested parens, and negative results

Related Problems

• Evaluate Reverse Polish Notation — postfix evaluation
• Expression Evaluation — infix to postfix conversion
• Decode String — nested bracket evaluation