227. Basic Calculator II

Problem¶

Evaluate a valid expression containing non-negative integers, spaces, and the operators +, -, *, and /. Apply normal precedence and truncate division toward zero without using eval().

Input:  s = "3 + 5 / 2"
State:  5 / 2 -> 2, then 3 + 2
Output: 5

Key trick¶

Keep the last term separate: immediately apply * and / to it, but commit it to the total only when encountering + or -.

Trap¶

Python's // rounds toward negative infinity, not toward zero.
Converting division through float can lose precision.
Spaces may appear on either side of an operator.
Applying every operator immediately ignores multiplication and division precedence.

Why is it interesting?¶

It reduces expression parsing with precedence to one pass and constant extra space, without requiring a full parser or stack.

Python solution¶

class Solution:
    def calculate(self, s: str) -> int:
        total = 0
        last = 0
        num = 0
        op = "+"
        n = len(s)

        # The extra iteration acts as a final operator, flushing `num`.
        for i in range(n + 1):
            ch = s[i] if i < n else "+"

            if ch.isdigit():
                num = num * 10 + int(ch)
                continue

            if ch == " ":
                continue

            if op == "+":
                total += last
                last = num
            elif op == "-":
                total += last
                last = -num
            elif op == "*":
                last *= num
            else:
                # Integer-only division truncated toward zero.
                sign = -1 if last < 0 else 1
                last = sign * (abs(last) // num)

            op = ch
            num = 0

        return total + last

Time complexity: \(O(n)\).

Space complexity: \(O(1)\).

Comment on my solution¶

The precedence idea is correct: resolve * and / before addition.
It fails when spaces follow subtraction, because parsing - immediately expects a digit. For example, 3 - 2 attempts to convert "-" to an integer.
The subtraction block is unreachable because - is converted into + with a negative operand and is never added to ops.
int(left / right) uses floating-point division and should be replaced with integer-only truncation.
The solution is still \(O(n)\) time, but the two stacks require \(O(n)\) space and add unnecessary complexity.

# Ideas
# - the difficulty comes from priority between operatator

# WORKS but slow
class Solution:
    def calculate(self, s: str) -> int:
        # "2+3-4" -> 1
        # "2*2+3" -> 7
        # "3+2*2" -> 7
        # "11+2" -> 13
        # " 3/2 " -> 1
        # " 3+5 / 2 " -> 5
        nums = []
        ops = []
        total = 0
        i = 0
        while i < len(s):
            if s[i] == " ":
                i += 1
            elif s[i] in {"+", "*", "/"}:
                ops.append(s[i])
                i += 1
            else:
                parts = []
                if s[i] == "-":
                    parts.append("-")
                    ops.append("+")
                    i += 1
                while i < len(s) and "0" <= s[i] <= "9":
                    parts.append(s[i])
                    i += 1
                nums.append(int("".join(parts)))
                if len(nums) >= 2 and ops and ops[-1] in {"*", "/"}:
                    right = nums.pop()
                    left = nums.pop()
                    op = ops.pop()
                    if op == "*":
                        nums.append(left * right)
                    else:
                        nums.append(int(left / right))
            if len(nums) >= 2 and ops and ops[-1] == "-":
                right = nums.pop()
                left = nums.pop()
                ops.pop()
                nums.append(left - right)
        while len(nums) >= 2 and ops:
            right = nums.pop()
            left = nums.pop()
            ops.pop()
            nums.append(left + right)
        return nums[0]