Basic Calculator

Basic Calculator asks you to evaluate a string like "1+(2-3)" by hand — no eval. It is the classic test of whether you can use a stack to handle nesting, the same skill behind matching brackets and parsing.

The slow way first

You might reach for recursion: every time you hit (, recurse on the inner string and splice the value back in. That works, but finding the matching ) for each ( means re-scanning, and the bookkeeping for where each sub-string starts and ends gets fiddly fast.

The question to ask: when I dive into a parenthesis, what do I need to come back to? I need the result I had built so far and the sign that sits in front of the parenthesis. That is exactly two values — perfect for a stack.

The idea: a running result, a sign, and a stack

Scan the string once. Keep a running result, a current sign (+1 or -1), and a number being built. For each character:

• a digit extends the current number;
• + or - flushes the number into result and sets sign;
• ( pushes the current result and sign onto the stack, then resets them for the inner expression;
• ) pops the saved sign and result back and folds the inner value in: result = saved_res + saved_sign * result.

The key insight: the stack lets each level of nesting remember the context it left behind, so when the parenthesis closes we resume exactly where we paused.

Walk through it

Step through the animation. The scan pointer moves over "1+(2-3)". At ( we push (1, +1) and reset to 0; inside we compute 2 - 3 = -1; at ) we pop and fold: 1 + (+1)·(-1) = 0.

Pseudocode

result = 0, sign = +1, num = 0, empty stack
for each char ch in s:
    if ch is a digit:
        num = num * 10 + ch          # build multi-digit numbers
    else:
        if num: result += sign * num # flush the pending number
        if ch is '+': sign = +1
        if ch is '-': sign = -1
        if ch is '(':                # save the outside, start fresh
            push result, push sign
            result = 0, sign = +1
        if ch is ')':                # restore and fold inner value in
            saved_sign = pop, saved_res = pop
            result = saved_res + saved_sign * result
return result + sign * num           # flush any trailing number

The Python solution

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

• result is the value accumulated at the current nesting level; sign is what to multiply the next number by.
• num builds multi-digit numbers — num * 10 + int(ch) shifts left and adds the new digit.
• On any non-digit we first flush the pending num into result, then act on the character.
• On ( we push result and sign, then reset — the inner expression starts clean.
• On ) we pop the saved sign and result and combine them: saved_res + saved_sign * result.
• The final return flushes any number still being built (spaces and the loop end leave it pending).

Complexity

We pass over the string once. The stack can hold up to O(n) values when the expression is deeply nested, so extra space is O(n).

When this pattern shows up

Practice