Basic Calculator II

You are given a string s holding a valid arithmetic expression made of non-negative integers, the operators +, -, * and /, and spaces. There are no parentheses and no unary minus signs.

Evaluate the expression and return the result. Use the usual rules: * and / bind tighter than + and -, and operators of equal precedence apply from left to right. Division is integer division that truncates toward zero (so -7 / 2 is -3). Do not use a built-in expression evaluator such as eval.

Example 1

Example 2

Example 3

Constraints

• 1 <= s.length <= 3 * 105
• s contains only digits, + - * / and spaces
• Every number is between 0 and 231 - 1 and the expression is valid
• No division by zero occurs
• The result and every intermediate value fit in a 32-bit signed integer

Pattern Path · Stacks · problem 48 of 169

Start simple

Repeatedly scan for the first * or / (then the first + or -), compute it and splice the result back into the token list: O(n²) time.

The key idea

Precedence has a simple shape when there are no parentheses: the expression is a sum of terms, and each term is a left-to-right chain of * and /. Subtraction can be folded in by negating the term that follows the minus sign, because a - b*c equals a + (-b)*c.

Scan the string once, building multi-digit numbers and skipping spaces. Keep op, the operator seen just before the current number (start with +). When the number ends (at the next operator or the end of the string), apply op:

• +: push the number as a new term.
• -: push its negative.
• * or /: pop the previous term, combine it with the number, and push the result back.

Then remember the new operator and reset the number. Because high-precedence operators are applied immediately to the most recent term, by the end the stack holds only independent terms, and their sum is the answer.

Negative terms are why truncation matters: 2 - 7/2 becomes the term -7 / 2, which must be -3, not the floor -4. The stack can be replaced by a single "last term" variable for O(1) space.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def calculate(self, s):
        terms = []        # finished terms; the answer is their sum
        num = 0
        op = '+'          # operator that came before the current number

        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)
            # A number ends at the next operator or at the end of the string.
            if ch in '+-*/' or i == len(s) - 1:
                if op == '+':
                    terms.append(num)
                elif op == '-':
                    terms.append(-num)
                elif op == '*':
                    terms.append(terms.pop() * num)
                else:
                    terms.append(int(terms.pop() / num))  # truncate toward zero
                op = ch
                num = 0

        return sum(terms)

JavaScript

var calculate = function(s) {
  const terms = [];   // finished terms; the answer is their sum
  let num = 0;
  let op = '+';       // operator that came before the current number

  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch >= '0' && ch <= '9') num = num * 10 + (ch.charCodeAt(0) - 48);
    // A number ends at the next operator or at the end of the string.
    if ('+-*/'.includes(ch) || i === s.length - 1) {
      if (op === '+') terms.push(num);
      else if (op === '-') terms.push(-num);
      else if (op === '*') terms.push(terms.pop() * num);
      else terms.push(Math.trunc(terms.pop() / num));   // truncate toward zero
      op = ch;
      num = 0;
    }
  }

  return terms.reduce((sum, t) => sum + t, 0);
};

What the interviewer is checking

The interviewer wants to see a clean single-pass parser that respects precedence, handles multi-digit numbers and whitespace, and gets integer division semantics right, without reaching for a general parser.

Mistakes to avoid

• Using floor division on a negative term (Python // or Math.floor), which gives -4 instead of -3 for -7 / 2.
• Forgetting to process the final number at the end of the string.
• Reading only single digits instead of whole multi-digit numbers.
• Applying the operator that follows a number instead of the one before it.

Follow-ups to expect

• How would you add parentheses? (Recurse or push state on "(".)
• Can you avoid the stack? (Keep a running sum and last term.)
• How would you support unary minus? (Treat it as 0 - x.)

In real software

Spreadsheet formula engines, calculator apps and configuration languages evaluate infix arithmetic with exactly this precedence-aware scan, and compilers generalise it into operator-precedence parsing.

Practice next