Evaluate arithmetic expression without parentheses
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Write evaluate(s: string) to compute the value of an arithmetic expression containing non-negative integers, '+', '-', '*', '/', and spaces, with operator precedence (* and / before + and -) and no parentheses. Division truncates toward zero. Aim for a single pass with O(
1) extra space beyond the output and a small stack or running registers. Discuss handling multi-digit numbers, consecutive spaces, and edge cases such as '3/2', '14-3/2', and trailing operators being invalid. Provide unit tests.
Quick Answer: Evaluate arithmetic expression without parentheses evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Implement `evaluate(s)` to compute the value of an arithmetic expression string containing non-negative integers, the operators `+`, `-`, `*`, `/`, and spaces. Operators follow normal precedence: `*` and `/` bind tighter than `+` and `-`. There are no parentheses. Integer division truncates toward zero (e.g. `3/2 == 1`).
Process the string in a single left-to-right pass. Track the current multi-digit number being built and the operator that precedes it. When you reach the next operator (or the end of the string), commit the pending number: push it for `+`/`-` (signed), or fold it into the top of the stack for `*`/`/`. The answer is the sum of all stack entries. This keeps the multiplicative work local so precedence falls out naturally without a separate parse tree.
Examples:
- `"3+2*2"` -> `7`
- `" 3/2 "` -> `1`
- `"14-3/2"` -> `13`
- `"2-3*4"` -> `-10`
You may assume the expression is valid (a number after every operator, no trailing operator); trailing-operator inputs are considered invalid and are out of scope.
Constraints
- 1 <= len(s); the expression is non-empty and represents a valid expression.
- s contains only digits, '+', '-', '*', '/', and ' ' (space).
- All integers in the expression are non-negative; intermediate and final results fit in a 32-bit signed integer.
- Integer division truncates toward zero (3/2 == 1, and would give -1 for a negative quotient).
- No parentheses; the input has a number after every operator (trailing operators are invalid and out of scope).
Examples
Input: ("3+2*2",)
Expected Output: 7
Explanation: * binds tighter: 2*2=4, then 3+4=7.
Input: (" 3/2 ",)
Expected Output: 1
Explanation: Leading/trailing spaces ignored; 3/2 truncates toward zero to 1.
Hints
- Walk the string once. Build the current number digit by digit (num = num*10 + digit) so multi-digit numbers and runs of spaces are handled naturally.
- Remember the operator that came BEFORE the current number. Only act when you hit the next operator (or the final character): that's when the pending number is complete.
- Defer + and - by pushing the signed number onto a stack; apply * and / immediately to the top of the stack. The final answer is the sum of the stack — precedence is handled for free.
- For truncate-toward-zero division, use int(a / b) in Python (Python's // floors, which differs for negatives). Java, C++, and JS Math.trunc already truncate toward zero.