Basic Calculator II

Intuition

Addition and subtraction can always wait until the very end, because their result does not depend on what comes after them. Multiplication and division, however, must combine with the value directly next to them before any addition happens. To respect this, we keep a stack that holds each additive term as a signed number. Whenever we finish reading a number, we look at the operator that came before it: a plus pushes the number, a minus pushes its negation, and a times or divide pops the previous term and folds the new number into it right away. Once the whole string is scanned, every remaining stack entry is an independent additive term, so summing them produces the answer.

Algorithm walkthrough

1. 1Track the current number being built, and remember the operator seen just before it (initialize this operator to '+').
2. 2Walk through each character, multiplying the running number by ten and adding each digit so multi-digit numbers accumulate correctly.
3. 3When you reach a non-space operator, or the last character of the string, resolve the previously stored operator against the current number.
4. 4For '+' push the number, for '-' push its negative, and for '*' or '/' pop the stack top and push the product or truncated quotient.
5. 5Update the stored operator to the current character and reset the running number to zero before continuing.
6. 6After the scan completes, add together everything left on the stack and return that total.

Implementation

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        num = 0
        op = '+'
        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)
                elif op == '/':
                    stack.append(int(stack.pop() / num))
                op = ch
                num = 0
        return sum(stack)