Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The input is a valid arithmetic expression containing non-negative integers, spaces, and the four operators +, -, *, and /. The task is to evaluate it without using eval or a similar built-in expression evaluator. Multiplication and division must happen before addition and subtraction, and integer division must truncate toward zero.

The main challenge is precedence. Reading from left to right and applying every operator immediately fails on an expression such as 3 + 2 * 2: committing the addition before seeing the multiplication loses the fact that 2 * 2 is one higher-priority term.

Deriving the one-pass solution

An expression using these four operators can be viewed as a sum of signed terms. Addition and subtraction separate the terms, while multiplication and division only extend the most recent term. That observation means the evaluator never needs to keep the whole expression or a full stack.

Maintain two values:

  • completed_sum contains all additive terms that are definitely finished.
  • pending_term contains the newest term, which may still be changed by a following multiplication or division.

When + or - is reached, the previous pending_term is finished, so it moves into completed_sum. The newly parsed number becomes the next positive or negative pending term. When * or / is reached, only pending_term changes. At the end, adding the final pending term to the completed sum gives the answer.

For 3 + 2 * 2, the evaluator first holds 3 as the pending term. The + finalizes that term and starts a new pending term of 2. The * changes that pending term to 4, so the result is 3 + 4 = 7.

Each character is processed once, giving O(n) time for an expression of length n. The parser stores only a few integers and therefore uses O(1) auxiliary space. Both bounds are optimal for this input model: every character may matter, and no storage proportional to the expression is required.

Python solution

class Solution:
    def calculate(self, expression: str) -> int:
        """Evaluate a valid Basic Calculator II expression."""
        completed_sum = 0
        pending_term = 0
        current_number = 0
        previous_operator = "+"

        for character in expression:
            if "0" <= character <= "9":
                current_number = current_number * 10 + int(character)
                continue

            if character == " ":
                continue

            if character not in "+-*/":
                raise ValueError(f"Unsupported character: {character!r}")

            # The newly encountered operator ends the current operand, so
            # apply the operator that appeared before that operand.
            completed_sum, pending_term = self._apply_operator(
                completed_sum,
                pending_term,
                previous_operator,
                current_number,
            )
            previous_operator = character
            current_number = 0

        # No trailing sentinel is needed: explicitly fold the final operand.
        completed_sum, pending_term = self._apply_operator(
            completed_sum,
            pending_term,
            previous_operator,
            current_number,
        )
        return completed_sum + pending_term

    @classmethod
    def _apply_operator(
        cls,
        completed_sum: int,
        pending_term: int,
        operator: str,
        operand: int,
    ) -> tuple[int, int]:
        """Fold one operand into the completed sum or pending term."""
        if operator == "+":
            return completed_sum + pending_term, operand
        if operator == "-":
            return completed_sum + pending_term, -operand
        if operator == "*":
            return completed_sum, pending_term * operand
        if operator == "/":
            return completed_sum, cls._truncate_toward_zero(
                pending_term,
                operand,
            )
        raise ValueError(f"Unsupported operator: {operator!r}")

    @staticmethod
    def _truncate_toward_zero(dividend: int, divisor: int) -> int:
        """Divide integers without converting through floating point."""
        quotient_magnitude = abs(dividend) // divisor
        return quotient_magnitude if dividend >= 0 else -quotient_magnitude

The division helper is important because Python’s // rounds negative results down, while the problem requires truncation toward zero. Computing the magnitude first and restoring the dividend’s sign implements the required behavior without introducing floating-point precision risk.

Interview follow-ups

How would the solution support parentheses?

Parentheses introduce nested expressions, so one pending term is no longer enough by itself. A recursive-descent parser can evaluate one expression level at a time: when it sees (, it recursively evaluates until the matching ), then treats that result as the next operand. The same pending-term rule handles precedence within each level. This remains O(n) time because each token is consumed once, but it uses O(d) call-stack space for nesting depth d. An explicit operator-and-value stack is safer if extremely deep nesting could exceed Python’s recursion limit.

How would unary plus and minus be handled?

The parser must distinguish a binary operator from a sign by tracking whether it currently expects an operand. A + or - at the beginning, after another operator, or after ( is unary; its sign should be accumulated and applied to the next number or parenthesized expression. This preserves linear time and constant extra space without parentheses, but the grammar becomes easier to reason about if tokenization and parsing are separated. Care is also needed for cases such as 2 * -3 and repeated signs if the chosen grammar allows them.

What changes if exponentiation is added?

Exponentiation has higher precedence than multiplication and is usually right-associative, so the current single pending term cannot resolve every case as soon as it is read. A shunting-yard parser can place values and operators on stacks, reducing operators according to precedence and associativity. It evaluates the expression in O(n) time and uses O(n) space in the worst case. Recursive descent is another clean option: give exponentiation its own grammar level and recurse on its right operand to model right associativity.

Can this evaluate an expression arriving in chunks?

Yes. The evaluator can retain completed_sum, pending_term, current_number, and previous_operator between chunks. A number should not be folded merely because a chunk ends, since its remaining digits may arrive in the next chunk; folding happens only when a real operator or the end-of-stream signal appears. The total work stays O(n) and the state stays O(1), which makes this approach suitable for very large streamed expressions.

How would production input validation change the design?

For untrusted input, a lexer should emit numbers and operators with source positions, while a parser enforces the expected alternation between operands and operators. It should reject empty expressions, missing operands, consecutive binary operators, division by zero, and unsupported characters with precise error locations. Validation still takes O(n) time. The main tradeoff is additional parser state and code, but separating syntax errors from arithmetic errors makes the evaluator much easier to maintain and diagnose.

When would a stack-based solution be preferable?

A stack-based version pushes signed terms for + and -, while * and / immediately replace the top term. Summing the stack at the end gives the same result in O(n) time, but it can use O(n) space. The stack is somewhat more direct to explain and easier to extend during an interview. The pending-term solution is preferable when the grammar stays limited to these four operators because it expresses the same precedence rule with constant auxiliary space.