Evaluate a Tokenized Arithmetic Expression
Company: Jane Street
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Evaluate a Tokenized Arithmetic Expression
You are given an arithmetic expression that has **already been tokenized** for you — you do not need to write a parser or tokenizer. The input is an array of string tokens `tokens`, where each token is one of:
- a non-negative integer literal, e.g. `"4"`, `"17"`;
- one of the four binary operators `"+"`, `"-"`, `"*"`, `"/"`;
- an opening or closing parenthesis `"("` or `")"`.
The token sequence is guaranteed to form a syntactically valid infix arithmetic expression. Evaluate the expression and return its value as an integer.
## Evaluation rules
- `*` and `/` have higher precedence than `+` and `-`.
- Operators of equal precedence are applied left to right.
- Parentheses may be nested arbitrarily deep and override precedence.
- All four operators are binary; there is no unary plus or minus.
- Every division that occurs during evaluation is guaranteed to be exact (the dividend is an integer multiple of the divisor), and no division by zero ever occurs, so every intermediate result is an integer.
## Examples
**Example 1**
```
Input: tokens = ["(", "4", "+", "5", ")", "*", "6"]
Output: 54
```
`(4 + 5) * 6 = 9 * 6 = 54`.
**Example 2**
```
Input: tokens = ["8", "-", "6", "/", "2"]
Output: 5
```
Division binds tighter than subtraction: `8 - (6 / 2) = 8 - 3 = 5`.
**Example 3**
```
Input: tokens = ["2", "*", "(", "3", "+", "(", "9", "-", "5", ")", ")", "/", "7"]
Output: 2
```
`2 * (3 + (9 - 5)) / 7 = 2 * 7 / 7 = 14 / 7 = 2`. Both the multiplication and the division are evaluated left to right, and the division is exact.
## Constraints
- `1 <= tokens.length <= 10^4`
- Each integer literal `v` satisfies `0 <= v <= 10^9`.
- All intermediate results and the final answer fit in a signed 64-bit integer.
- The expression is syntactically valid; parentheses are balanced.