Basic Calculator III

Basic Calculator III is the boss level of the calculator series. It mixes +, −, *, / and parentheses — so you have to respect operator precedence and nesting. The clean way to do it is a single left-to-right scan with a number stack and one pending operator.

The slow way first

You could try to fully parse the string into an expression tree, or strip parentheses with repeated passes, or convert to postfix (Shunting-yard) and evaluate. Those all work, but they are fiddly and easy to get wrong under interview pressure — multiple passes, extra data structures, careful bracket matching.

The question to ask: can I handle precedence in one pass? The trick is that * and / bind tighter than + and −, so we can resolve them the moment we see them while deferring the additions and subtractions to a stack.

The idea: stack of terms + a pending sign

Walk the string once, building up the current number num. Keep a stack of terms and a pending operator sign (start at +). When you hit an operator (or the end), you flush num using the previous sign:

• + → push +num
• − → push −num
• * → pop the top, push top * num (applied immediately)
• / → pop the top, push top / num (truncated)

Then set sign to the new operator and reset num. A ( means a sub-expression, so recurse; the recursive call returns a single number that becomes the next num. At the very end, the answer is just sum(stack).

Because * and / pop-and-combine immediately, the stack only ever holds finished terms that get added. Precedence falls out for free.

Walk through it

Step through the animation for 2*(3+4). We read 2, then * flushes +2 onto the stack and sets the pending sign to *. The ( triggers a recursion that returns 7. Closing the parenthesis flushes 7 with the pending *: we pop 2 and push 2*7 = 14. Nothing is left, so we sum the stack and get 14.

Pseudocode

helper(iterator over chars):
    stack = empty
    num = 0
    sign = '+'
    loop forever:
        ch = next char, or ')' if the string ran out
        if ch is a digit:  num = num*10 + digit
        else if ch == '(':  num = helper(iterator)   # recurse, reuse result as num
        else if ch is one of + - * / ):
            apply the PREVIOUS sign to num:
                '+'  -> push num
                '-'  -> push -num
                '*'  -> push (pop * num)
                '/'  -> push trunc(pop / num)
            sign = ch ;  num = 0
            if ch == ')': break
    return sum(stack)
answer = helper(iterator over s with spaces removed)

The Python solution

def calculate(s):
    def helper(it):
        stack = []
        num = 0
        sign = '+'
        while True:
            ch = next(it, ')')
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == '(':
                num = helper(it)
            elif ch in '+-*/)':
                if sign == '+': stack.append(num)
                elif sign == '-': stack.append(-num)
                elif sign == '*': stack.append(stack.pop() * num)
                else: stack.append(int(stack.pop() / num))
                sign, num = ch, 0
                if ch == ')': break
        return sum(stack)
    return helper(iter(s.replace(' ', '')))

• it is a single character iterator, so the recursion and the parent share one cursor through the string — next(it, ')') returns the sentinel ')' when the outer call runs out.
• num accumulates a multi-digit number with num*10 + int(ch).
• A ( recurses; the returned value becomes the current num, treated like any other operand.
• The operator branch flushes num using the previous sign: push for +/−, pop-and-combine for *//.
• int(stack.pop() / num) truncates toward zero, matching the required integer-division rule (plain // would round toward negative infinity for negatives).
• After flushing, sign, num = ch, 0 records the new operator; a ) breaks out and the call returns sum(stack).

Complexity

We touch every character exactly once, so time is O(n). The stack and the recursion call frames use O(n) space in the worst case (deeply nested or addition-heavy expressions).

When this pattern shows up

Practice