Evaluate an Arithmetic Expression with Parentheses, Unary Minus and Four Operators
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Evaluate an arithmetic expression given as a string and return its integer value. This covers the whole reported calculator series: addition and subtraction with parentheses and a leading minus sign, and multiplication and division with their usual precedence.
### Function Signature
```python
def evaluate(expression: str) -> int:
```
### Rules
- The expression contains non-negative integer literals, the binary operators `+`, `-`, `*` and `/`, parentheses, and spaces. Spaces can appear between tokens but never inside a number.
- `*` and `/` bind more tightly than `+` and `-`. Operators of equal precedence are applied from left to right, and parentheses group as usual.
- `-` can also be unary, but only at the very start of the expression or directly after `(`, ignoring spaces. It negates the number or the parenthesized group that follows it. `+` is never unary.
- Division is integer division that truncates toward zero, so `7 / 2` is `3` and `-7 / 2` is `-3`.
- Do not call a built-in expression evaluator such as `eval`.
### Constraints
- `1 <= len(expression) <= 10^4`
- The expression contains only digits, `+`, `-`, `*`, `/`, `(`, `)` and spaces, and it is valid.
- No division by zero occurs.
- Every literal and every intermediate result lies between `-2^31` and `2^31 - 1`.
- Parentheses can be nested deeply, up to about half the length of the expression.
### Examples
**Example 1**
```text
Input: expression = "2 + 3 * (4 - 1) / 2"
Output: 6
```
`3 * (4 - 1)` is 9, `9 / 2` truncates to 4, and `2 + 4` is 6.
**Example 2**
```text
Input: expression = "-(3 + 4) / 2"
Output: -3
```
The leading minus negates the group, giving -7, and `-7 / 2` truncates toward zero to -3.
**Example 3**
```text
Input: expression = "14 - 3 - (2 - (-5))"
Output: 4
```
Subtraction runs left to right: `14 - 3` is 11, the inner group `2 - (-5)` is 7, and `11 - 7` is 4.
Overview: Evaluate an arithmetic expression string with non-negative integers, addition, subtraction, multiplication, division truncating toward zero, parentheses and a unary minus. It tests tokenizing, operator precedence, left-to-right evaluation and deeply nested parentheses without eval.
Given a string `expression` that holds a valid arithmetic expression, evaluate it and return its integer value.
The expression is built from non-negative integer literals, the binary operators `+`, `-`, `*` and `/`, the parentheses `(` and `)`, and spaces. Spaces can appear between tokens but never inside a number.
Evaluation rules:
- `*` and `/` bind more tightly than `+` and `-`. Operators of equal precedence are applied from left to right, and parentheses group as usual.
- `-` can also be unary, but only at the very start of the expression or directly after `(`, ignoring spaces. A unary `-` negates the number or the parenthesized group that follows it. `+` is never unary.
- Division is integer division that truncates toward zero, so `7 / 2` is `3` and `-7 / 2` is `-3`.
- Do not call a built-in expression evaluator such as `eval`.
Return the value of the whole expression as an integer. The input is always valid and never divides by zero, and every literal and every intermediate result lies between -2^31 and 2^31 - 1, so the returned value never exceeds 2^31 - 1 and fits in a signed 32-bit integer.
**Example 1**
```text
Input: expression = "2 + 3 * (4 - 1) / 2"
Output: 6
```
`3 * (4 - 1)` is 9, `9 / 2` truncates to 4, and `2 + 4` is 6.
**Example 2**
```text
Input: expression = "-(3 + 4) / 2"
Output: -3
```
The leading minus negates the group, giving -7, and `-7 / 2` truncates toward zero to -3.
**Constraints**
- `1 <= len(expression) <= 10^4`
- `expression` contains only digits, `+`, `-`, `*`, `/`, `(`, `)` and spaces, and it is valid.
- No division by zero occurs.
- Every literal and every intermediate result lies between `-2^31` and `2^31 - 1`.
- Parentheses can be nested deeply, up to about half the length of the expression.
Constraints
- 1 <= len(expression) <= 10^4
- expression contains only digits, '+', '-', '*', '/', '(', ')' and spaces, and it is a valid expression; spaces can appear between tokens but never inside a number
- '-' can be unary only at the very start of the expression or directly after '(' (ignoring spaces); '+' is never unary
- No division by zero occurs
- Every literal and every intermediate result lies between -2^31 and 2^31 - 1, so the result never exceeds 2^31 - 1 and fits in a signed 32-bit integer
- Parentheses can be nested deeply, up to about half the length of the expression
Examples
Input: ('0',)
Expected Output: 0
Explanation: Minimum valid: the single-digit literal 0 evaluates to zero.
Input: ('(7)',)
Expected Output: 7
Explanation: Minimum valid: a single literal wrapped in one pair of parentheses.
Hints
- Parentheses can nest about 5,000 levels deep in a 10^4-character expression. Think about how much state each open group needs and where you keep it.
- Because '*' and '/' bind more tightly than '+' and '-', a minus sign in front of a product or quotient applies to the whole term. Check that 8 - 9 / 2 gives 4.
- Truncation toward zero and floor division disagree whenever exactly one operand is negative: -7 / 2 must be -3, not -4.