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.
Quick Answer: This question evaluates understanding of arithmetic expression evaluation, including operator precedence, parenthesis handling, associativity, and exact integer arithmetic, testing competency in token-level expression processing within the Coding & Algorithms domain and representing a practical application of algorithmic techniques.
You are given an arithmetic expression that has already been tokenized for you (no parser/tokenizer needed). 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 "+", "-", "*", "/"; or a parenthesis "(" or ")". The token sequence is guaranteed to form a syntactically valid infix arithmetic expression. Evaluate it and return its integer value.
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 (no remainder) and no division by zero occurs, so every intermediate result is an integer.
Examples:
- tokens = ["(", "4", "+", "5", ")", "*", "6"] -> 54 since (4 + 5) * 6 = 9 * 6.
- tokens = ["8", "-", "6", "/", "2"] -> 5 since division binds tighter: 8 - (6 / 2) = 8 - 3.
- tokens = ["2", "*", "(", "3", "+", "(", "9", "-", "5", ")", ")", "/", "7"] -> 2 since 2 * (3 + (9 - 5)) / 7 = 2 * 7 / 7 = 14 / 7, evaluated left to right.
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.
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.
- Every division is exact and there is no division by zero.
Examples
Input: ["(", "4", "+", "5", ")", "*", "6"]
Expected Output: 54
Explanation: (4 + 5) * 6 = 9 * 6 = 54. Parentheses force the addition first.
Input: ["8", "-", "6", "/", "2"]
Expected Output: 5
Explanation: Division binds tighter than subtraction: 8 - (6 / 2) = 8 - 3 = 5.
Hints
- Use two stacks: one for integer values and one for operators (including '('). Push numbers onto the value stack as you read them.
- When you hit an operator, first resolve any pending operators on top of the stack whose precedence is greater than or equal to the current one (but stop at a '('). This enforces * / over + - and left-to-right for equal precedence.
- On ')', keep applying operators until you pop the matching '('. At the end, drain any remaining operators. The single remaining value is the answer.