Basic calculator: evaluate an arithmetic expression string

Evaluate an arithmetic expression given as a string, respecting operator precedence, without eval. Before coding, state exactly which grammar you accept.

Interface

Unless you agree on a different interface with the interviewer, assume:

• calculate(s: str) -> int
• s holds non-negative integers, the operators +, -, *, / and spaces. * and / bind tighter than + and -; operators of equal precedence apply left to right. / is integer division that truncates toward zero. The expression is always valid.

Example

calculate("3+2*2")               ->  7
calculate(" 3/2 ")               ->  1
calculate("14-3/2")              ->  13
calculate("2-7*3/4")             ->  -3    # 7*3 = 21, 21/4 = 5, 2-5 = -3
calculate("10 - 2 * 3 + 8 / 4")  ->  6

Constraints

• 1 <= len(s) <= 3 * 10^5.
• All intermediate results fit in a 32-bit signed integer; no division by zero.

Clarifying questions

• Which operators and characters can appear? Parentheses? Unary minus?
• Is division integer division, and does it truncate toward zero or floor?
• Can numbers have several digits, and can there be spaces anywhere?
• Is the input always valid, or should I report errors?

What a strong answer covers

• The grammar written down first: expr := term (('+' | '-') term)*, term := number (('*' | '/') number)*.
• A one-pass evaluator with a stack: push +n or -n, and for * or / combine with the top; sum the stack at the end. Or keep a running total and the last term for O(1) space.
• Truncation toward zero in languages where / floors negatives (Python's //).
• Multi-digit numbers and spaces in the tokenizer.
• Tests: a single number, all four operators, spaces everywhere, a negative intermediate result.

Follow-ups

• Add parentheses: recursion or an explicit stack of saved states.
• Add unary minus (-3*-2).
• Support variables, or floating-point numbers with a clear rounding rule.