Loading page…
Practice problem · medium
A payments app stores each fee rule as a postfix formula. The numbers come first, and an operator comes after the two numbers it works on. So 4 13 5 / + means 4 + 13 / 5. This form needs no brackets and no precedence rules.
Each token is a whole number, which may be negative, or one of the four operators +, -, * and /. Fees are charged in whole minor units, so a division drops its fraction, toward zero. A formula can have up to 100,000 tokens.
Write evaluate_formula(tokens).
tokens is a list of strings in postfix order. The formula is always valid: no division by zero, and every result fits in a 32-bit signed integer.Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9| Step | Token | What happens | Stack after (bottom to top) |
|---|---|---|---|
| 1 | 2 |
a number: push it | 2 |
| 2 | 1 |
a number: push it | 2, 1 |
| 3 | + |
pop 1 (right) and 2 (left), push 2 + 1 | 3 |
| 4 | 3 |
a number: push it | 3, 3 |
| 5 | * |
pop 3 (right) and 3 (left), push 3 × 3 | 9 |
One value is left, and it is the answer: (2 + 1) × 3 = 9.
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 613 / 5 is 2.6, which drops to 2. Then 4 + 2 = 6.
Input: tokens = ["7", "-2", "/"]
Output: -37 / -2 is -3.5, and dropping the fraction toward zero gives -3, not -4.
1 ≤ number of tokens ≤ 10^5+, -, *, /A plan that finds an operator, rewrites the list and starts again costs up to n^2 / 4 steps: 2.5 × 10^9 here. That is too slow.
Evaluating each token once is the clean target. The only memory you need is the finished values that are still waiting for an operator.
evaluate_formula · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.