Evaluate arithmetic expression with precedence
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Implement an evaluator for a string arithmetic expression. The input contains non-negative integers, the operators `+`, `-`, `*`, `/`, parentheses `(` and `)`, and arbitrary spaces. Your evaluator must respect operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity, and return the result as a 64-bit integer.
1. **Core evaluation.** Parse and evaluate the expression, honoring precedence, associativity, and parentheses. Use 64-bit intermediate values to avoid overflow on large sub-results.
2. **Unary minus.** Support a leading or post-operator unary minus, e.g. `-3+5`, `2*-4`, or `-(1+2)`.
3. **Integer division.** Division is integer division that truncates toward zero (so `7/2 == 3` and `-7/2 == -3`).
4. **Error handling.** Return an error (or raise) for invalid input such as mismatched parentheses, an empty/garbage token stream, or division by zero.
5. **Approach and complexity.** Describe your method (e.g. the two-stack operator/operand technique, the shunting-yard algorithm, or a recursive-descent parser), and analyze its time and space complexity. Aim for O(n) time and O(n) space, where n is the length of the input string.
Example: `"2*(3+ -4) / 2"` evaluates to `-1`.
Quick Answer: Instacart software-engineer onsite coding question: implement an arithmetic expression evaluator for a string of non-negative integers, +, -, *, /, parentheses, and spaces. It tests operator precedence and associativity, unary minus, 64-bit intermediates, integer division truncating toward zero, and robust handling of invalid input via a two-stack, shunting-yard, or recursive-descent parser.
Implement an evaluator for a string arithmetic expression and return the result as a 64-bit integer.
The input contains non-negative integers, the operators `+`, `-`, `*`, `/`, parentheses `(` and `)`, and arbitrary spaces. Your evaluator must:
1. Respect operator precedence (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity, using 64-bit intermediate values.
2. Support unary minus, whether leading or after an operator, e.g. `-3+5`, `2*-4`, `-(1+2)`.
3. Use integer division that truncates toward zero, so `7/2 == 3` and `-7/2 == -3` (NOT floor division).
4. Signal an error for invalid input — mismatched parentheses, an empty or garbage token stream, division by zero, or trailing tokens. In this harness, signal an error by returning `None` (Python) / `null` (Java/JS) / the sentinel value for an invalid expression rather than crashing.
Example: `"2*(3+ -4) / 2"` evaluates to `-1`.
Aim for O(n) time and O(n) space, where n is the length of the input string.
Constraints
- Input contains non-negative integer literals, the operators + - * /, parentheses ( ), and spaces.
- Operator precedence: * and / bind tighter than + and -; same-precedence operators are left-associative.
- Unary minus/plus has the highest precedence and may appear leading or after another operator.
- Division is integer division that truncates toward zero (7/2 == 3, -7/2 == -3).
- All intermediate results fit in a signed 64-bit integer.
- Invalid input (mismatched parentheses, empty/garbage tokens, division by zero, trailing tokens) returns None instead of crashing.
Examples
Input: ("2*(3+ -4) / 2",)
Expected Output: -1
Explanation: 3 + (-4) = -1; 2 * -1 = -2; -2 / 2 = -1. Demonstrates precedence, parentheses, unary minus, and division.
Input: ("3+5*2",)
Expected Output: 13
Explanation: * binds tighter than +: 5*2=10, then 3+10=13.
Hints
- A recursive-descent parser mirrors the grammar directly: expr := term (('+'|'-') term)*, term := factor (('*'|'/') factor)*, factor := NUMBER | '(' expr ')' | ('-'|'+') factor.
- Handle unary minus/plus inside parse_factor so it automatically gets the highest precedence — this makes -3*2 == -6 and 2*-3 == -6 fall out without a special case.
- Python's // floors, but the spec wants truncation toward zero. For opposite-sign operands with a nonzero remainder, compute -(abs(a)//abs(b)). C/C++/Java/JS native integer division already truncates toward zero.
- After parsing the top-level expression, check that you consumed the whole string (pos == len). A leftover ')' or trailing token means the input was malformed.