Prefix formula evaluator: hints, no solution
Medium · Stack
A spreadsheet plugin stores formulas in prefix form: an operator comes first, followed by its two operands, and each operand is either an integer or another prefix formula. The operators are +, -, * and max. The minus operator subtracts the second operand from the first, and max returns the larger of its two operands.
You receive the formula as a list of tokens, written left to right. A token is either one of the four operator strings or an integer such as 7 or -3. The list is always a complete, valid formula. Return its value. Every intermediate result fits in a signed 32-bit integer.
Formulas can be nested thousands of levels deep, so a solution should not rely on deep recursion.
Examples
- Input
- tokens = ["+", "3", "*", "2", "4"]
- Output
- 11
- Note
- The multiplication happens first, then the addition.
- Input
- tokens = ["max", "-", "9", "4", "*", "2", "3"]
- Output
- 6
- Note
- max compares 9 - 4 = 5 with 2 * 3 = 6 and returns 6.
Constraints
- 1 <= tokens.length <= 2001
- Integer tokens are between -1000 and 1000
- The formula is valid and every intermediate value fits in 32 bits
Hint 1: a nudge
In prefix form an operator appears before the numbers it needs. What would you know about the operands if you read the tokens from the other end?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.