Basic Calculator II

Parse the string into a flat token list of numbers and operators, ignoring spaces. Then, repeatedly, scan for the first * or /, replace that operator and its two operands with their value, and start over. Re-scanning from scratch matters: multiplication and division associate left to right, so folding a*b*c one operator at a time preserves the correct order. Once no * or / remains, only + and - are left and they evaluate left to right, which addition and subtraction always allow.

Each collapse is correct because it replaces a strict subexpression with its already-computed value, which cannot change the overall result. It is slow because of how often it restarts: there can be O(n) high-precedence operators, and every collapse walks the current token list (O(n)) and splices the result back in (O(n)).

class Solution:
    def calculate(self, s: str) -> int:
        # Tokenize into a flat list of numbers and operators.
        tokens = []
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch in "+-*/":
                tokens.append(num)
                tokens.append(ch)
                num = 0
        tokens.append(num)

        def trunc_div(a: int, b: int) -> int:
            # Truncate toward zero (not floor): floor on abs, restore sign.
            q = abs(a) // abs(b)
            return -q if (a < 0) != (b < 0) else q

        # Collapse the first * or / and restart. Each round removes two
        # tokens, so there can be O(n) rounds, each scanning O(n).
        changed = True
        while changed:
            changed = False
            for i, tok in enumerate(tokens):
                if tok == "*" or tok == "/":
                    a, b = tokens[i - 1], tokens[i + 1]
                    value = a * b if tok == "*" else trunc_div(a, b)
                    tokens[i - 1 : i + 2] = [value]
                    changed = True
                    break

        # Only + and - remain; fold left to right.
        total = tokens[0]
        i = 1
        while i < len(tokens):
            if tokens[i] == "+":
                total += tokens[i + 1]
            else:
                total -= tokens[i + 1]
            i += 2
        return total

Why it is quadratic: each collapse is O(n) work, and up to O(n) high-precedence operators each force a fresh full scan and a list splice, so the worst case is O(n²). The token list itself costs O(n) space.

Scan once, accumulating each number from consecutive digits. Keep two pieces of state: a running sign (the operator that precedes the current number, starting as +) and a stack of finalized signed terms. Whenever a number ends — at a new operator, or at the end of the string — use sign to file it away:

• + → push the number;
• - → push its negation;
• * → pop the top and push top * num;
• / → pop the top and push top / num, truncating toward zero.

Then reset num, update sign to the operator just read, and move on. When the string is exhausted, the stack holds every term with its sign already folded in, so the answer is sum(stack).

This works because the only pending decision when a number finishes is its own operator — and the decision for * and / only ever needs the single preceding factor, which is exactly the stack top. Conversely, + and - never need to look ahead: the terms they collect are combined only at the end, in any order, since addition and subtraction are left-associative operations done one term at a time.

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        sign = "+"
        n = len(s)
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            # A number ends at an operator, or at the end of the string.
            if i == n - 1 or ch in "+-*/":
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop() * num)
                else:
                    top = stack.pop()
                    # Truncate toward zero (not floor): floor on abs, restore sign.
                    q = abs(top) // num
                    stack.append(-q if top < 0 else q)
                sign = ch
                num = 0
        return sum(stack)

Watch the pending sign decide each number — push a new term for + and -, fold into the top for * and / — and note that the final sum is only computed after every term is on the stack:

The same mechanism on a division example, where the top of the stack is divided and truncated toward zero:

Why it is linear: each character is visited once and each stack entry is pushed exactly once, so the total work is O(n). Because * and / replace the top rather than grow the stack, the stack never holds more than the number of +/- terms, bounded by O(n) space in the worst case (e.g. an expression of alternating + terms).