Evaluate an Integer Arithmetic Expression With Precedence and Parentheses
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
Given a string `s` that holds an arithmetic expression, evaluate it and return its integer value. The expression is built from non-negative integer literals, the binary operators `+`, `-`, `*` and `/`, parentheses, and spaces. In the interview the problem started without parentheses and the follow-up added them; implement the version with parentheses, which also handles every parenthesis-free expression. Do not use a built-in expression evaluator such as `eval`.
### Function Signature
```python
def evaluate(s: str) -> int:
```
### Rules
- `*` and `/` take precedence over `+` and `-`. Operators of equal precedence are applied from left to right, and parentheses group in the usual way.
- `/` is integer division that truncates toward zero: `7 / 2` evaluates to `3`, and an intermediate value of `-7` divided by `2` gives `-3`, not `-4`.
- There are no unary operators: every `+` and `-` has an operand on each side, so inputs such as `-3` or `2*(-1)` never occur. Intermediate results can still be negative, as in `1 - 5`.
- Spaces may appear anywhere between tokens and are ignored; a number never contains a space.
- Literals are written in decimal without leading zeros (zero itself is written `0`).
- The expression is always valid.
### Constraints
- `1 <= len(s) <= 10^4`
- `s` contains only the digits `0` to `9`, the characters `+`, `-`, `*`, `/`, `(`, `)`, and spaces.
- Every integer literal is between `0` and `2^31 - 1`, inclusive.
- Every intermediate result, and the final result, is between `-2^31` and `2^31 - 1`, inclusive.
- No division by zero occurs.
- Parentheses nest at most `100` levels deep.
### Examples
**Example 1**
```text
Input: s = "14 - 3 * 4 / 5"
Output: 12
```
`3 * 4` is `12`, then `12 / 5` truncates to `2`, and `14 - 2` is `12`.
**Example 2**
```text
Input: s = "2 * (5 - 9) / 3 + 7"
Output: 5
```
`(5 - 9)` is `-4`, `2 * -4` is `-8`, `-8 / 3` truncates toward zero to `-2`, and `-2 + 7` is `5`.
**Example 3**
```text
Input: s = "(1+(4*(2+3)))-6/(1+1)"
Output: 18
```
`2+3` is `5`, `4*5` is `20`, `1+20` is `21`; `1+1` is `2`, `6/2` is `3`, and `21-3` is `18`.
Overview: A coding problem to evaluate an arithmetic string containing non-negative integers, the four basic operators, spaces and nested parentheses, with integer division that truncates toward zero. It tests operator precedence, left-to-right evaluation and hand-written parsing without a built-in evaluator.
Read the full Meta Software Engineer interview experience this question came from