Problem 15 · Stacks

Basic Calculator II

MediumClassic DSA & systems

01Problem

Evaluate a string expression with non-negative integers, + - * / and spaces; integer division truncates toward zero.

02Key insight

Defer + and - by pushing signed terms on a stack, but apply * and / immediately to the top, which encodes precedence in one pass. Truncate toward zero with int(a / b), not //.

03Solution

solution.pypython17 lines

def calculate(s: str) -> int:
    stack: list[int] = []
    num, op = 0, "+"
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != " ") or i == len(s) - 1:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(int(stack.pop() / num))  # truncate toward zero
            op, num = ch, 0
    return sum(stack)

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert calculate("3+2*2") == 7
assert calculate(" 3/2 ") == 1
assert calculate(" 3+5 / 2 ") == 5
assert calculate("14-3/2") == 13

04Staff-level follow-up

Add parentheses and unary minus? Recurse on '(' (or push state onto a stack), or move to a proper tokenizer plus Pratt/shunting-yard parser, which is how a SQL engine's expression evaluator is built.