Evaluate an arithmetic expression
Company: Instacart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Write a function that evaluates a mathematical expression given as a string.
Requirements:
- Supports non-negative integers and whitespace.
- Supports operators `+`, `-`, `*`, `/` with standard precedence (`*` and `/` before `+` and `-`).
- Optionally supports parentheses `(` and `)` (if you choose to support them, document your approach).
- Integer division should truncate toward zero.
Examples:
- Input: `"3+2*2"` → Output: `7`
- Input: `" 3/2 "` → Output: `1`
- Input: `" 3+5 / 2 "` → Output: `5`
- (If supporting parentheses) Input: `"2*(3+(4-1))"` → Output: `12`
Quick Answer: This question evaluates a candidate's ability to implement expression parsing and evaluation, assessing competencies in string parsing, operator precedence, parentheses handling, and integer arithmetic semantics including truncation toward zero.
Write a function that evaluates a mathematical expression given as a string. The expression may contain non-negative integers, whitespace, the operators '+', '-', '*', and '/', and parentheses '()'. Multiplication and division must be evaluated before addition and subtraction, unless parentheses change the order. Division must truncate toward zero. You may assume the expression is valid and never divides by zero. This version of the problem supports parentheses.
Constraints
- 1 <= len(s) <= 100000
- s contains digits, spaces, '+', '-', '*', '/', '(', and ')'
- All numbers in the expression are non-negative integers
- The expression is valid and division by zero will not occur
- The final result fits in a 32-bit signed integer
Examples
Input: "3+2*2"
Expected Output: 7
Explanation: Multiplication happens first: 2*2 = 4, then 3+4 = 7.
Input: " 3/2 "
Expected Output: 1
Explanation: 3 divided by 2 truncates toward zero, so the result is 1.
Hints
- Use one stack for numbers and another for operators.
- When you read a new operator, apply any earlier operators that have higher or equal precedence. Parentheses act as barriers.