DSA Basic Calculator II

The problem

Basic Calculator II evaluates a string holding numbers and the operators +, -, * and /. Precedence is the rule that multiplication and division bind tighter than addition and subtraction. Division drops the part after the decimal point toward zero.

The string holds no parentheses. Numbers may hold several digits. The cases below are the ones this article uses throughout.

cases = [
    ("3+2*2", 7),
    ("3/2", 1),
    ("3+5/2", 5),
    ("14-3/2", 13),
    ("42", 42),
]
for text, expected in cases:
    print("expression", text, "-> value:", expected)

Read one row at a time. The first row is the precedence test in miniature. The 2 times 2 must resolve before the addition, or the answer comes out wrong.

Intuition: work left to right, and precedence breaks it

The first idea reads the expression left to right and applies each operator as it arrives. The idea needs no extra structure. It also ignores precedence completely.

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

print("3+2*2 left to right:", left_to_right("3+2*2"), " correct value: 7")
print("14-3/2 left to right:", left_to_right("14-3/2"), " correct value: 13")

Both rows fail. The first adds 3 and 2 before the multiplication ever runs. The fix must let multiplication and division resolve first while addition and subtraction wait.

Brute force: two passes over the tokens

The straightforward fix splits the work by precedence. A first pass walks the tokens and collapses every multiplication and division into a single value. A second pass then folds the remaining additions and subtractions from the left.

The method is correct and easy to check. Its cost is structural. The token list is built once and then walked twice, and the first pass builds a second list of the same order of size.

def calculate_two_pass(text):
    tokens = []
    number = 0
    for ch in text:
        if ch.isdigit():
            number = number * 10 + int(ch)
        else:
            tokens.append(number)
            tokens.append(ch)
            number = 0
    tokens.append(number)
    collapsed = [tokens[0]]
    i = 1
    while i < len(tokens):
        op, value = tokens[i], tokens[i + 1]
        if op == "*":
            collapsed[-1] = collapsed[-1] * value
        elif op == "/":
            collapsed[-1] = int(collapsed[-1] / value)
        else:
            collapsed.append(op)
            collapsed.append(value)
        i += 2
    result = collapsed[0]
    i = 1
    while i < len(collapsed):
        op, value = collapsed[i], collapsed[i + 1]
        if op == "+":
            result += value
        else:
            result -= value
        i += 2
    return result

for text in ("3+2*2", "3/2", "3+5/2", "14-3/2", "42"):
    print(text, "=", calculate_two_pass(text))

Every case matches the expected values from section 1. The stack solution below reaches the same answers in a single pass, with no token list at all.

The optimal solution: signed values on a stack, settled by the previous sign

One pass builds each number digit by digit, and each operator settles the number before it using the previous sign, pushing a signed value for + and - and rewriting the top of the stack for * and /. That one sentence is the whole method.

A running number is built digit by digit until an operator appears. Each digit shifts the running number one place in base ten and adds the new digit. The sign variable always holds the operator seen just before the current number.

Signed values go on the stack, so the final step is one plain sum. A final plus sign is appended to the string so the last number is settled by the same rule as every other number. The stack never holds an operator.

def calculate(text):
    stack = []
    number = 0
    sign = "+"
    for ch in text + "+":
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch in "+-*/":
            if sign == "+":
                stack.append(number)
            elif sign == "-":
                stack.append(-number)
            elif sign == "*":
                stack.append(stack.pop() * number)
            else:
                stack.append(int(stack.pop() / number))
            sign = ch
            number = 0
    return sum(stack)

cases = [
    ("3+2*2", 7),
    ("3/2", 1),
    ("3+5/2", 5),
    ("14-3/2", 13),
    ("42", 42),
]
for text, expected in cases:
    result = calculate(text)
    print("expression", text, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. Multiplication and division rewrite the top value at once, so precedence is handled at the moment the operator arrives. Addition and subtraction defer safely, because their signed values sum correctly in any order.

Walkthrough: settling 3+2*2 step by step

The walk runs the main case with the stack printed after each settlement. A settlement happens when an operator, or the appended final plus, closes the number before it.

text = "3+2*2"
stack = []
number = 0
sign = "+"
for ch in text + "+":
    if ch.isdigit():
        number = number * 10 + int(ch)
    elif ch in "+-*/":
        if sign == "+":
            stack.append(number)
        elif sign == "-":
            stack.append(-number)
        elif sign == "*":
            stack.append(stack.pop() * number)
        else:
            stack.append(int(stack.pop() / number))
        print("operator", ch, "settled", number, "- stack:", stack)
        sign = ch
        number = 0
print("sum of stack:", sum(stack))

The multiplication settles last and rewrites the 2 on top into 4. The final stack holds 3 and 4. Their sum is the answer, and no operator was ever stored.

Complexity

Both methods do a fixed amount of work per character, so both run in O(n) time for a string of n characters. The difference is in passes and space, not in the growth rate.

The two-pass method stores the full token list and a collapsed list, so its space is O(n). The stack holds at most one value per number in the string, so its space is also O(n), with no second list and only one pass over the input.

def touches_two_pass(text):
    tokens = []
    number = 0
    for ch in text:
        if ch.isdigit():
            number = number * 10 + int(ch)
        else:
            tokens.append(number)
            tokens.append(ch)
            number = 0
    tokens.append(number)
    return len(tokens) + len(tokens)

def touches_one_pass(text):
    touches = 0
    for ch in text + "+":
        touches += 1
    return touches

for k in (1, 2, 4):
    text = "+".join(["1+2*3"] * k)
    print("numbers:", 3 * k, "- two-pass token touches:", touches_two_pass(text), " one-pass char touches:", touches_one_pass(text))

The counts show the shape of the saving. The two-pass method touches every token twice. The one-pass method touches every character once, plus the single appended sign.

Edge cases and pitfalls

Division toward zero is the classic trap. Python's // operator rounds downward, which gives -4 for -7 divided by 2. This problem drops the fraction toward zero, which gives -3, and int on the quotient performs exactly that drop.

Forgetting the final settlement is the second trap. Without the appended sign, the last number is never pushed and the answer silently drops it. A single-number string would answer 0 instead of the number itself.

def calculate(text):
    stack = []
    number = 0
    sign = "+"
    for ch in text + "+":
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch in "+-*/":
            if sign == "+":
                stack.append(number)
            elif sign == "-":
                stack.append(-number)
            elif sign == "*":
                stack.append(stack.pop() * number)
            else:
                stack.append(int(stack.pop() / number))
            sign = ch
            number = 0
    return sum(stack)

print("single number:", calculate("42"))
print("negative division:", calculate("0-7/2"), " floor division would give:", -7 // 2)
print("division chain:", calculate("100/10/2"))
print("multiplication chain:", calculate("2*3*4"))
print("plus and minus chain:", calculate("1-1+1"))
print("multi-digit numbers:", calculate("247+3"))

The division chain resolves from the left, so 100 divided by 10 divided by 2 gives 5. The multiplication chain works the same way, one top-of-stack rewrite at a time.