DSA Basic Calculator

The problem

A basic calculator evaluates an arithmetic string. The string holds digits, the four operators, parentheses, unary minus and spaces. The answer is one integer.

Multiplication and division bind tighter than addition and subtraction. Parentheses override that order. Division truncates toward zero, so 10 / 4 gives 2 and -7 / 2 gives -3.

tests = [
    ("1 + 1", 2),
    ("2-(1+2)", -1),
    ("2+3*4", 14),
    ("14-3/2", 13),
    ("(1+(4+5+2)-3)+(6+8)", 23),
    ("-(2+3)*4+10/4", -18),
    (" 42 - 3 * (8 - 5) ", 33),
]
for text, expected in tests:
    print(repr(text), "=", expected)

The fifth case nests parentheses three levels deep. The sixth opens with a unary minus on a whole bracket. The last case pads everything with spaces.

Intuition: work strictly left to right

The first idea reads the string once and applies each operator as it arrives. Parentheses are skipped as decoration. The idea is simple, fast and wrong.

def trunc_div(a, b):
    whole = abs(a) // abs(b)
    if (a < 0) == (b < 0):
        return whole
    return -whole


def left_to_right(text):
    tokens = []
    num = None
    for ch in text:
        if ch.isdigit():
            num = (num or 0) * 10 + int(ch)
        elif ch in "+-*/":
            if num is not None:
                tokens.append(num)
                num = None
            tokens.append(ch)
    if num is not None:
        tokens.append(num)
    total = tokens[0]
    i = 1
    while i < len(tokens):
        op = tokens[i]
        value = tokens[i + 1]
        if op == "+":
            total = total + value
        elif op == "-":
            total = total - value
        elif op == "*":
            total = total * value
        else:
            total = trunc_div(total, value)
        i += 2
    return total

print("2+3*4 left to right:", left_to_right("2+3*4"), " correct:", 14)
print("2-(1+2) left to right:", left_to_right("2-(1+2)"), " correct:", -1)

Both answers are wrong. The first adds before multiplying. The second subtracts before the bracket groups its values. Order is the whole problem, and a single left-to-right pass has nowhere to keep it.

Brute force: collapse the brackets, then fold in two passes

The brute force removes one pair of parentheses at a time. It finds the innermost bracket, evaluates the flat text inside it, and writes the number back into the string. The work repeats until no brackets remain.

A flat string is evaluated in two passes. The first pass folds multiplication and division into single values. The second pass folds addition and subtraction. A sign in front of a number folds into that number, which is how unary minus is handled.

def trunc_div(a, b):
    whole = abs(a) // abs(b)
    if (a < 0) == (b < 0):
        return whole
    return -whole


def flat_eval(text, counter):
    counter[0] += len(text)
    tokens = []
    i = 0
    expect_num = True
    while i < len(text):
        ch = text[i]
        if ch == " ":
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(text) and text[j].isdigit():
                j += 1
            tokens.append(int(text[i:j]))
            i = j
            expect_num = False
        elif ch in "+-" and expect_num:
            sign = 1
            while i < len(text) and text[i] in "+-":
                if text[i] == "-":
                    sign = -sign
                i += 1
            while i < len(text) and text[i] == " ":
                i += 1
            j = i
            while j < len(text) and text[j].isdigit():
                j += 1
            tokens.append(sign * int(text[i:j]))
            i = j
            expect_num = False
        else:
            tokens.append(ch)
            i += 1
            expect_num = True
    folded = [tokens[0]]
    i = 1
    while i < len(tokens):
        op = tokens[i]
        value = tokens[i + 1]
        if op == "*":
            folded[-1] = folded[-1] * value
        elif op == "/":
            folded[-1] = trunc_div(folded[-1], value)
        else:
            folded.extend([op, value])
        i += 2
    total = folded[0]
    i = 1
    while i < len(folded):
        if folded[i] == "+":
            total = total + folded[i + 1]
        else:
            total = total - folded[i + 1]
        i += 2
    return total


def evaluate_slow(text):
    counter = [0]
    rounds = 0
    while "(" in text:
        rounds += 1
        counter[0] += len(text)
        opening = text.rfind("(")
        closing = text.index(")", opening)
        inner = text[opening + 1:closing]
        value = flat_eval(inner, counter)
        text = text[:opening] + str(value) + text[closing + 1:]
    return flat_eval(text, counter), rounds, counter[0]

for text in ["2+3*4", "(1+(4+5+2)-3)+(6+8)", "-(2+3)*4+10/4"]:
    result, rounds, scanned = evaluate_slow(text)
    print(repr(text), "=", result, " collapse rounds:", rounds, " characters scanned:", scanned)

The answers are right. The cost is the rescanning. Every collapse round reads the whole string again, and the flat evaluation reads its piece again on top of that.

The optimal solution: one pass with a stack of frames

A frame is one level of parentheses with its own stack, its own running sign and its own pending operator, and a single left-to-right pass over a stack of frames evaluates the whole string. That one structure is the whole method.

The running sign is the plus or minus waiting for the next value. A minus with no value before it is unary, and it flips the running sign instead of starting a subtraction. Multiplication and division fold into the top stack value at once, which is what makes them bind tighter.

An opening bracket pushes the current frame and starts a fresh one. A closing bracket sums its frame and feeds that total into the parent frame as one value, under the parent's waiting sign and operator.

def evaluate(text):
    def feed(frame, value):
        stack, sign, op = frame
        factor = sign * value
        if op == "*":
            stack[-1] = stack[-1] * factor
        elif op == "/":
            stack[-1] = int(stack[-1] / factor)
        else:
            stack.append(factor)
        frame[1] = 1
        frame[2] = None

    frames = []
    frame = [[], 1, None]
    num = 0
    has_num = False
    operand_done = False
    for ch in text + "=":
        if ch.isdigit():
            num = num * 10 + int(ch)
            has_num = True
        elif ch in "+-*/()= ":
            if ch == " ":
                continue
            if has_num:
                feed(frame, num)
                num = 0
                has_num = False
                operand_done = True
            if ch == "+":
                if operand_done:
                    frame[1] = 1
                operand_done = False
            elif ch == "-":
                if operand_done:
                    frame[1] = -1
                else:
                    frame[1] = -frame[1]
                operand_done = False
            elif ch in "*/":
                frame[2] = ch
                operand_done = False
            elif ch == "(":
                frames.append(frame)
                frame = [[], 1, None]
                operand_done = False
            elif ch == ")":
                value = sum(frame[0])
                frame = frames.pop()
                feed(frame, value)
                operand_done = True
    return sum(frame[0])

tests = [
    ("1 + 1", 2),
    ("2-(1+2)", -1),
    ("2+3*4", 14),
    ("14-3/2", 13),
    ("(1+(4+5+2)-3)+(6+8)", 23),
    ("-(2+3)*4+10/4", -18),
    (" 42 - 3 * (8 - 5) ", 33),
]
for text, expected in tests:
    result = evaluate(text)
    print(repr(text), "=", result, "expected:", expected, "match:", result == expected)

All seven cases pass in one pass each. A sentinel equals sign at the end flushes the final number through the same feed path as every other value.

Walkthrough: evaluating 2-(1+2)

The trace prints each feed and each bracket event. A feed writes one signed value into the current frame's stack, or folds it into the top value when an operator waits.

def traced_evaluate(text):
    def feed(frame, value):
        stack, sign, op = frame
        factor = sign * value
        if op == "*":
            stack[-1] = stack[-1] * factor
        elif op == "/":
            stack[-1] = int(stack[-1] / factor)
        else:
            stack.append(factor)
        frame[1] = 1
        frame[2] = None
        print("feed", value, "with sign", sign, "-> stack:", stack)

    frames = []
    frame = [[], 1, None]
    num = 0
    has_num = False
    operand_done = False
    for ch in text + "=":
        if ch.isdigit():
            num = num * 10 + int(ch)
            has_num = True
        elif ch in "+-*/()= ":
            if ch == " ":
                continue
            if has_num:
                feed(frame, num)
                num = 0
                has_num = False
                operand_done = True
            if ch == "+":
                if operand_done:
                    frame[1] = 1
                operand_done = False
            elif ch == "-":
                if operand_done:
                    frame[1] = -1
                    print("minus after a value: running sign is now -1")
                else:
                    frame[1] = -frame[1]
                operand_done = False
            elif ch in "*/":
                frame[2] = ch
                operand_done = False
            elif ch == "(":
                frames.append(frame)
                frame = [[], 1, None]
                operand_done = False
                print("open bracket: fresh frame pushed")
            elif ch == ")":
                value = sum(frame[0])
                frame = frames.pop()
                print("close bracket: frame total", value, "returns to the parent")
                feed(frame, value)
                operand_done = True
    return sum(frame[0])

print("answer:", traced_evaluate("2-(1+2)"))

The bracket total of 3 returns to a parent whose running sign is -1, so it lands as -3 beside the 2. The final sum reads -1 straight off the parent stack. Nesting is just more frames on the same pile.

Complexity

The collapsing evaluator scans the whole string once per bracket round and again per flat evaluation, so its character visits grow with the product of length and nesting depth. The frame evaluator visits each character once, so its time is O(n) in the string length.

The frame stack holds one frame per open bracket, so its extra space is O(d) in the nesting depth. The counts below build strings of growing depth and compare characters scanned against characters in the string.

def trunc_div(a, b):
    whole = abs(a) // abs(b)
    if (a < 0) == (b < 0):
        return whole
    return -whole


def flat_eval(text, counter):
    counter[0] += len(text)
    tokens = []
    i = 0
    expect_num = True
    while i < len(text):
        ch = text[i]
        if ch == " ":
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(text) and text[j].isdigit():
                j += 1
            tokens.append(int(text[i:j]))
            i = j
            expect_num = False
        elif ch in "+-" and expect_num:
            sign = 1
            while i < len(text) and text[i] in "+-":
                if text[i] == "-":
                    sign = -sign
                i += 1
            while i < len(text) and text[i] == " ":
                i += 1
            j = i
            while j < len(text) and text[j].isdigit():
                j += 1
            tokens.append(sign * int(text[i:j]))
            i = j
            expect_num = False
        else:
            tokens.append(ch)
            i += 1
            expect_num = True
    folded = [tokens[0]]
    i = 1
    while i < len(tokens):
        op = tokens[i]
        value = tokens[i + 1]
        if op == "*":
            folded[-1] = folded[-1] * value
        elif op == "/":
            folded[-1] = trunc_div(folded[-1], value)
        else:
            folded.extend([op, value])
        i += 2
    total = folded[0]
    i = 1
    while i < len(folded):
        if folded[i] == "+":
            total = total + folded[i + 1]
        else:
            total = total - folded[i + 1]
        i += 2
    return total


def slow_scans(text):
    counter = [0]
    while "(" in text:
        counter[0] += len(text)
        opening = text.rfind("(")
        closing = text.index(")", opening)
        value = flat_eval(text[opening + 1:closing], counter)
        text = text[:opening] + str(value) + text[closing + 1:]
    flat_eval(text, counter)
    return counter[0]

for depth in [1, 2, 4, 8, 16]:
    text = "1+(" * depth + "2" + ")" * depth
    print("nesting depth:", depth, "characters:", len(text), "slow scans:", slow_scans(text), " one pass visits:", len(text))

At depth 16 the collapsing evaluator scans about ten characters for every character in the string. The ratio keeps growing with depth. One pass never revisits anything.

Edge cases and pitfalls

A bare number evaluates to itself. Doubled minuses cancel, because each unary minus flips the sign once. Deep nesting is only more frames, and spaces may appear anywhere.

def evaluate(text):
    def feed(frame, value):
        stack, sign, op = frame
        factor = sign * value
        if op == "*":
            stack[-1] = stack[-1] * factor
        elif op == "/":
            stack[-1] = int(stack[-1] / factor)
        else:
            stack.append(factor)
        frame[1] = 1
        frame[2] = None

    frames = []
    frame = [[], 1, None]
    num = 0
    has_num = False
    operand_done = False
    for ch in text + "=":
        if ch.isdigit():
            num = num * 10 + int(ch)
            has_num = True
        elif ch in "+-*/()= ":
            if ch == " ":
                continue
            if has_num:
                feed(frame, num)
                num = 0
                has_num = False
                operand_done = True
            if ch == "+":
                if operand_done:
                    frame[1] = 1
                operand_done = False
            elif ch == "-":
                if operand_done:
                    frame[1] = -1
                else:
                    frame[1] = -frame[1]
                operand_done = False
            elif ch in "*/":
                frame[2] = ch
                operand_done = False
            elif ch == "(":
                frames.append(frame)
                frame = [[], 1, None]
                operand_done = False
            elif ch == ")":
                value = sum(frame[0])
                frame = frames.pop()
                feed(frame, value)
                operand_done = True
    return sum(frame[0])

print("bare number:", evaluate("42"))
print("zero:", evaluate("0"))
print("doubled minus:", evaluate("--5"))
print("negated bracket of a negative:", evaluate("-(-3)"))
print("deep nesting:", evaluate("(((((1)))))"))
print("spaces everywhere:", evaluate("  12  +  8 "))
print("calculator division -7 / 2:", evaluate("-7/2"))
print("python floor division -7 // 2:", -7 // 2)

The last two lines show the division pitfall. Python's // operator floors, which sends -7 // 2 down to -4. The calculator's rule truncates toward zero and gives -3. Any evaluator built on // alone fails exactly the negative divisions.