Times Before Plus
formula is a valid arithmetic formula built from whole numbers, the operators +, - and *, round brackets and spaces. Return its value as an integer, following the usual rules:
- Brackets are worked out first, and they may be nested.
*is applied before+and-, so2 + 3 * 4is 14.- Operators of the same level are applied from left to right, so
8 - 3 - 2is 3. - A
-at the very start of the formula, right after(, or right after another operator negates what follows it: a number, a bracket, or another negation. So-2 + 3is 1,2 * -3is -6,-(1 + 2)is -3 and--5is 5. - Spaces can appear anywhere except inside a number, and they mean nothing.
A + is never used as a sign. A recursive evaluator is the natural fit: one function reads a sum of products, another reads a product of factors, and a factor is a number, a negated factor, or a bracketed formula, which calls the first function again. A loop with two stacks works too.
Example 1
The product 3 * 4 = 12 is worked out first, then 2 is added.
Example 2
Inside the brackets 2 * 5 = 10 comes first, so 7 - 10 = -3; negated it is 3; then 3 * -3 = -9 and -9 - 4 = -13.
Constraints
1 <= len(formula) <= 60- every number is between
0and999and has no leading zeros - brackets are nested at most 6 deep
- every intermediate result and the final value lie between
-109and109
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Recursion problems
- Valleys in the Folded StripHard
- Count the BoxesBeginner
- Digit TallyBeginner
- Equal NeighboursBeginner
- Halving TotalBeginner
- Largest DigitBeginner
- Multiply It OutBeginner
- Nested SumBeginner