How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

Evaluate arithmetic expression with precedence

Quick Overview

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.

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.

Input: ("(1+2)*3",)

Expected Output: 9

Explanation: Parentheses override precedence: (1+2)=3, 3*3=9.

Input: ("-3+5",)

Expected Output: 2

Explanation: Leading unary minus: -3 + 5 = 2.

Input: ("2*-4",)

Expected Output: -8

Explanation: Unary minus after an operator: 2 * (-4) = -8.

Input: ("-(1+2)",)

Expected Output: -3

Explanation: Unary minus applied to a parenthesized group: -(3) = -3.

Input: ("7/2",)

Expected Output: 3

Explanation: Integer division truncates toward zero: 7/2 = 3.5 -> 3.

Input: ("-7/2",)

Expected Output: -3

Explanation: Truncate toward zero, not floor: -7/2 = -3.5 -> -3 (floor would give -4).

Input: (" 10 - 3 * 2 ",)

Expected Output: 4

Explanation: Arbitrary whitespace is ignored: 3*2=6, 10-6=4.

Input: ("100",)

Expected Output: 100

Explanation: A bare multi-digit integer literal.

Input: ("((2+3))",)

Expected Output: 5

Explanation: Nested redundant parentheses still evaluate to 5.

Input: ("1+2)",)

Expected Output: None

Explanation: Trailing unmatched ')' — invalid input returns None.

Input: ("(1+2",)

Expected Output: None

Explanation: Missing closing parenthesis — invalid input returns None.

Input: ("5/0",)

Expected Output: None

Explanation: Division by zero must be signaled, not silently produce garbage.

Input: ("",)

Expected Output: None

Explanation: Empty input is invalid and returns None.

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.

Last updated: Jun 25, 2026

Loading coding console...

Quick Overview

Evaluate arithmetic expression with precedence

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Input: ("(1+2)*3",)

Expected Output: 9

Explanation: Parentheses override precedence: (1+2)=3, 3*3=9.

Input: ("-3+5",)

Expected Output: 2

Explanation: Leading unary minus: -3 + 5 = 2.

Input: ("2*-4",)

Expected Output: -8

Explanation: Unary minus after an operator: 2 * (-4) = -8.

Input: ("-(1+2)",)

Expected Output: -3

Explanation: Unary minus applied to a parenthesized group: -(3) = -3.

Input: ("7/2",)

Expected Output: 3

Explanation: Integer division truncates toward zero: 7/2 = 3.5 -> 3.

Input: ("-7/2",)

Expected Output: -3

Explanation: Truncate toward zero, not floor: -7/2 = -3.5 -> -3 (floor would give -4).

Input: (" 10 - 3 * 2 ",)

Expected Output: 4

Explanation: Arbitrary whitespace is ignored: 3*2=6, 10-6=4.

Input: ("100",)

Expected Output: 100

Explanation: A bare multi-digit integer literal.

Input: ("((2+3))",)

Expected Output: 5

Explanation: Nested redundant parentheses still evaluate to 5.

Input: ("1+2)",)

Expected Output: None

Explanation: Trailing unmatched ')' — invalid input returns None.

Input: ("(1+2",)

Expected Output: None

Explanation: Missing closing parenthesis — invalid input returns None.

Input: ("5/0",)

Expected Output: None

Explanation: Division by zero must be signaled, not silently produce garbage.

Input: ("",)

Expected Output: None

Explanation: Empty input is invalid and returns None.

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.

Last updated: Jun 25, 2026

Loading coding console...