Katkat
Back

Evaluate arithmetic expression with precedence

InstacartSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.