Evaluate expression without stack, constant space
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given a string `s` representing a valid arithmetic expression of non-negative integers, the operators `+`, `-`, `*`, `/`, and spaces (there are **no parentheses**), evaluate the expression and return its integer value, respecting operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity.
Constraints and follow-ups the interviewer will push on:
1. **Single pass, constant space.** Solve it in a single left-to-right pass in O(n) time and O(1) extra space. You may **not** use an explicit stack, and you may **not** use recursion.
2. **Operator precedence without a stack.** Explain how you track the *last term* and a running *aggregated result* so that `*` and `/` are applied immediately while `+`/`-` are deferred — this is how you enforce precedence with no auxiliary data structure.
3. **Multi-digit numbers.** Explain how you accumulate multi-digit operands (e.g. `42`) as you scan, digit by digit.
4. **Integer division semantics.** Division is integer division that **truncates toward zero** (so `7/2 == 3` and `-7/2 == -3`), not floor division.
5. **Edge cases.** Handle interior and trailing spaces, single-number inputs, and the final pending term after the last character.
Example: `"3+2*2"` evaluates to `7`; `" 3/2 "` evaluates to `1`; `" 3+5 / 2 "` evaluates to `5`.
Quick Answer: Evaluate expression without stack, constant space 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.
Given a string `s` representing a valid arithmetic expression of non-negative integers with the operators `+`, `-`, `*`, `/`, and spaces (no parentheses), evaluate the expression and return its integer value.
Respect operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity. Solve it in a single left-to-right pass in O(n) time and O(1) extra space: you may NOT use an explicit stack and you may NOT use recursion.
Key requirements:
- Operator precedence is enforced by tracking the *last additive term* and a running *aggregated result*, so `*` and `/` are applied immediately while `+`/`-` are deferred.
- Accumulate multi-digit operands digit by digit (e.g. `42`).
- Integer division truncates toward zero (so `7/2 == 3` and `-7/2 == -3`), NOT floor division.
- Handle interior and trailing spaces, single-number inputs, and the final pending term after the last character.
Examples: `"3+2*2"` -> `7`; `" 3/2 "` -> `1`; `" 3+5 / 2 "` -> `5`.
Constraints
- s is a valid arithmetic expression of non-negative integers
- Operators are limited to +, -, *, / and the space character
- There are no parentheses
- * and / bind tighter than + and - (operator precedence)
- Integer division truncates toward zero
- Must run in O(n) time and O(1) extra space with no explicit stack and no recursion
- All intermediate and final values fit in a 32/64-bit signed integer
Examples
Input: ("3+2*2",)
Expected Output: 7
Explanation: 2*2=4 is applied immediately (higher precedence), then 3+4=7.
Input: (" 3/2 ",)
Expected Output: 1
Explanation: Leading/trailing spaces are skipped; 3/2 truncates toward zero to 1.
Hints
- With no parentheses the expression is a flat sum of products/quotients. You only ever defer additive terms, and their sum is a single number, so the unbounded stack collapses into one accumulator (result) plus one in-progress term (last).
- Track four variables: result (sum of completed additive terms), last (signed value of the current term), cur (the number being parsed), and op (the operator preceding cur, initialized to '+').
- Apply * and / immediately to `last`; commit `last` into `result` only when a +/- arrives. Append a sentinel '+' (or special-case the last index) so the final pending term is flushed.
- Division must truncate toward zero. Python's // floors (-7 // 2 == -4), so use abs(last)//abs(cur) and re-apply the sign, giving -7/2 == -3.