Basic calculator II: evaluate + - * / without parentheses

Evaluate a string expression of non-negative integers, the operators +, -, * and /, and spaces. There are no parentheses. * and / bind tighter than + and -, and division truncates toward zero.

Interface

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

• calculate(s: str) -> int — the input is always a valid expression.

Example

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

Constraints

• 1 <= len(s) <= 3 * 10^5. Every intermediate result fits in a 32-bit signed integer.
• No unary minus. Numbers may have several digits.
• Use O(1) extra space beyond the input.

Clarifying questions

• Can numbers have leading zeros or be very long?
• Is there a unary minus, as in -3+2?
• Division by zero: can it happen?
• Python's // floors. Should -7/2 give -3 (truncate)?

What a strong answer covers

• The stack solution first: push signed terms, apply * and / to the top of the stack, and sum at the end.
• Then O(1) space: keep the running total and the last term. On + or -, add the last term to the total. On * or /, combine it into the last term.
• Parsing multi-digit numbers and skipping spaces in one pass. Handling the final number.
• Truncation toward zero in a language that floors, using int(a / b) or sign handling.
• Tests: a single number, spaces everywhere, a division with a negative partial result such as "2-7/2" -> -1.

Follow-ups

• Only + and * are allowed, and numbers may be separated by spaces or commas.
• Add parentheses. Use recursion or a stack of saved states.
• Add unary minus and variables.