Coding questions · Instacart

Evaluate an arithmetic expression

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.

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

Evaluate an Arithmetic Expression

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

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.