Evaluate an Integer Expression String with +, -, * and Nested Parentheses
Company: Aiprise
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Write a function that evaluates an arithmetic expression given as a string and returns its integer value. The expression contains non-negative integer literals, the binary operators `+`, `-` and `*`, and parentheses. There is no division, and the expression is always valid. For example, `2*(3+5*(8-4))` evaluates to `46`.
### Function Signature
```python
def evaluate(expression: str) -> int:
```
### Rules
- `*` binds tighter than `+` and `-`, which have equal precedence. Operators of equal precedence apply from left to right, so `10-2-3` means `(10-2)-3`, which is `5`.
- Parentheses group as usual and can be nested.
- Every `+`, `-` and `*` has an operand on each side: there is no unary minus or unary plus, and no implicit multiplication such as `2(3)`.
- Spaces may appear between tokens and are ignored. A space never appears inside a number.
- The result can be negative even though every literal is non-negative: `3-5` evaluates to `-2`.
- Return the exact integer value of the whole expression.
### Constraints
- `1 <= len(expression) <= 10^4`
- `expression` contains only the digits `0` to `9`, `+`, `-`, `*`, `(`, `)` and spaces, and is valid under the rules above.
- Each number literal has at most 9 digits. Leading zeros may appear and do not change the value (`007` is `7`).
- Parentheses are nested at most 100 levels deep.
- The value of every subexpression, and of the whole expression, has absolute value at most `10^15`. This exceeds the 32-bit signed range, so use 64-bit integers in languages with fixed-width types; every value stays within `±2^53`.
### Examples
**Example 1**
```text
Input: expression = "2*(3+5*(8-4))"
Output: 46
```
`8-4` is `4`, `5*4` is `20`, `3+20` is `23`, and `2*23` is `46`.
**Example 2**
```text
Input: expression = "10 - 2 * 3 - 4"
Output: 0
```
The multiplication goes first, giving `10 - 6 - 4`; then, from left to right, `10 - 6` is `4` and `4 - 4` is `0`.
**Example 3**
```text
Input: expression = "(1-(4*(2+3)))*3-7"
Output: -64
```
`2+3` is `5`, `4*5` is `20`, `1-20` is `-19`, `-19*3` is `-57`, and `-57-7` is `-64`.
Overview: Evaluate a valid arithmetic expression string containing non-negative integers, the operators +, - and *, and nested parentheses, and return its exact integer value. Tests tokenizing, operator precedence, left-to-right associativity of subtraction and correct handling of nested parentheses without division.
Write a function `evaluate(expression)` that evaluates an arithmetic expression given as a string and returns its integer value.
The expression contains non-negative integer literals, the binary operators `+`, `-` and `*`, and parentheses. There is no division, and the expression is always valid.
**Rules**
- `*` binds tighter than `+` and `-`, which have equal precedence. Operators of equal precedence apply from left to right, so `10-2-3` means `(10-2)-3`, which is `5`.
- Parentheses group as usual and can be nested.
- Every `+`, `-` and `*` has an operand on each side: there is no unary minus or unary plus, and no implicit multiplication such as `2(3)`.
- Spaces may appear between tokens and are ignored. A space never appears inside a number.
- The result can be negative even though every literal is non-negative: `3-5` evaluates to `-2`.
- Return the exact integer value of the whole expression. The value can exceed the 32-bit signed range (2^31 - 1), so the function returns a 64-bit integer: `long` in Java and `long long` in C++.
**Example 1**
```text
Input: expression = "2*(3+5*(8-4))"
Output: 46
```
`8-4` is `4`, `5*4` is `20`, `3+20` is `23`, and `2*23` is `46`.
**Example 2**
```text
Input: expression = "10 - 2 * 3 - 4"
Output: 0
```
The multiplication goes first, giving `10 - 6 - 4`; then, from left to right, `10 - 6` is `4` and `4 - 4` is `0`.
**Constraints**
- `1 <= len(expression) <= 10^4`
- `expression` contains only the digits `0` to `9`, `+`, `-`, `*`, `(`, `)` and spaces, and is valid under the rules above.
- Each number literal has at most 9 digits. Leading zeros may appear and do not change the value (`007` is `7`).
- Parentheses are nested at most 100 levels deep.
- The value of every subexpression, and of the whole expression, has absolute value at most `10^15`. This exceeds the 32-bit signed range, so use 64-bit integers in languages with fixed-width types; every value stays within `±2^53`.
Constraints
- 1 <= len(expression) <= 10^4
- expression contains only the digits 0 to 9, +, -, *, (, ) and spaces, and is valid under the rules above.
- Each number literal has at most 9 digits. Leading zeros may appear and do not change the value (007 is 7).
- Parentheses are nested at most 100 levels deep.
- The value of every subexpression, and of the whole expression, has absolute value at most 10^15. This exceeds the 32-bit signed range, so use 64-bit integers in languages with fixed-width types; every value stays within ±2^53.
Examples
Input: ('7',)
Expected Output: 7
Explanation: Minimum valid input: a single one-character literal.
Input: ('( ( 007 ) )',)
Expected Output: 7
Explanation: A literal with leading zeros inside redundant nested parentheses, with spaces between every token.
Hints
- Start without parentheses: `*` binds tighter than `+` and `-`, and operators of equal precedence apply from left to right. Work out how to evaluate a flat expression such as `10 - 2 * 3 - 4` in a single pass first.
- To the operators around it, a parenthesized group behaves exactly like a single number. Think about what you must remember about the outer expression while you evaluate a group, given that groups can nest up to 100 levels deep.
- Numbers can span several digits and may have leading zeros, and values can reach 10^15 in magnitude, so read each number whole and use 64-bit integers.