069. Basic Calculator with Parentheses

Why this mechanism works

Within one parenthesis context, keep a committed result, a pending sign and the current number. An opening parenthesis saves the parent's committed result and sign, then starts a fresh context. A closing parenthesis turns the completed child result into one signed value in its parent.

State and boundaries

result is the sum of committed terms in the active context. sign applies to number or the next parenthesized group. stack holds suspended (result,sign) contexts.

Protocol

1. Accumulate decimal digits.
2. On + or -, commit the current signed number and set the next sign.
3. On '(' save context and reset.
4. On ')' finish the child and combine with its saved parent.
5. Commit any final number.

Visualization

1 + (2 - (3 - 4))
inner: 3-4=-1
middle: 2-(-1)=3
outer: 1+3=4

Python implementation

def calculate(expression):
    result = number = 0
    sign = 1
    stack = []
    for char in expression:
        if char.isdigit():
            number = number * 10 + int(char)
        elif char in '+-':
            result += sign * number
            number = 0
            sign = 1 if char == '+' else -1
        elif char == '(':
            stack.append((result, sign))
            result, number, sign = 0, 0, 1
        elif char == ')':
            result += sign * number
            parent, parent_sign = stack.pop()
            result = parent + parent_sign * result
            number = 0
    return result + sign * number

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 calculate: result = number = 0
expression='1+(2-(3-4))'; result=0; number=0

L3 calculate: sign = 1
expression='1+(2-(3-4))'; result=0; number=0; sign=1

L4 calculate: stack = []
expression='1+(2-(3-4))'; result=0; number=0; sign=1; stack=[]

L5 calculate: for char in expression:
expression='1+(2-(3-4))'; result=0; number=0; sign=1; stack=[]; char='1'

L7 calculate: number = number * 10 + int(char)
expression='1+(2-(3-4))'; result=0; number=1; sign=1; stack=[]; char='1'

L5 calculate: for char in expression:
expression='1+(2-(3-4))'; result=0; number=1; sign=1; stack=[]; char='+'

L9 calculate: result += sign * number
expression='1+(2-(3-4))'; result=1; number=1; sign=1; stack=[]; char='+'

L10 calculate: number = 0
expression='1+(2-(3-4))'; result=1; number=0; sign=1; stack=[]; char='+'

... 23 intermediate state changes omitted ...

L18 calculate: result = parent + parent_sign * result
expression='1+(2-(3-4))'; result=3; number=4; sign=-1; stack=[(1, 1)]; char=')'; parent=2; parent_sign=-1

L19 calculate: number = 0
expression='1+(2-(3-4))'; result=3; number=0; sign=-1; stack=[(1, 1)]; char=')'; parent=2; parent_sign=-1

L17 calculate: parent, parent_sign = stack.pop()
expression='1+(2-(3-4))'; result=3; number=0; sign=-1; stack=[]; char=')'; parent=1; parent_sign=1

L18 calculate: result = parent + parent_sign * result
expression='1+(2-(3-4))'; result=4; number=0; sign=-1; stack=[]; char=')'; parent=1; parent_sign=1

L2 calculate: result = number = 0
expression='-(2+3)+4'; result=0; number=0

L3 calculate: sign = 1
expression='-(2+3)+4'; result=0; number=0; sign=1

L4 calculate: stack = []
expression='-(2+3)+4'; result=0; number=0; sign=1; stack=[]

L5 calculate: for char in expression:
expression='-(2+3)+4'; result=0; number=0; sign=1; stack=[]; char='-'

L11 calculate: sign = 1 if char == '+' else -1
expression='-(2+3)+4'; result=0; number=0; sign=-1; stack=[]; char='-'

L5 calculate: for char in expression:
expression='-(2+3)+4'; result=0; number=0; sign=-1; stack=[]; char='('

L13 calculate: stack.append((result, sign))
expression='-(2+3)+4'; result=0; number=0; sign=-1; stack=[(0, -1)]; char='('

L14 calculate: result, number, sign = 0, 0, 1
expression='-(2+3)+4'; result=0; number=0; sign=1; stack=[(0, -1)]; char='('

... 11 intermediate state changes omitted ...

L19 calculate: number = 0
expression='-(2+3)+4'; result=-5; number=0; sign=1; stack=[]; char=')'; parent=0; parent_sign=-1

L5 calculate: for char in expression:
expression='-(2+3)+4'; result=-5; number=0; sign=1; stack=[]; char='+'; parent=0; parent_sign=-1

L5 calculate: for char in expression:
expression='-(2+3)+4'; result=-5; number=0; sign=1; stack=[]; char='4'; parent=0; parent_sign=-1

L7 calculate: number = number * 10 + int(char)
expression='-(2+3)+4'; result=-5; number=4; sign=1; stack=[]; char='4'; parent=0; parent_sign=-1

Why the solution is correct

Within each context, terms are added exactly once with their pending sign. Saving a parent preserves the sign that applies to the whole child expression. Closing evaluates that child before combining it, matching parenthesis semantics recursively without recursive calls.

Time and space

O(n) arithmetic operations and O(d) context space for nesting depth d; integer bit costs are additional.

Common mistakes

Subtracting only the first term of a parenthesized expression ignores the group's sign. This simple parser does not promise arbitrary consecutive unary operators.

Reasoning card

Transfer exercise

Extend the grammar to multiplication and division. Identify why the current single-level sign state cannot express precedence by itself.