question 349 Algorithms & Complexity · hard

Evaluate a deeply nested formula without recursion

A pricing tool stores formulas as nested lists: a number, or [operator, left, right] with operator "+", "-" or "*". Formulas built by a rules engine can be nested more than a thousand levels deep, deeper than Python's recursion limit. Write evaluate(formula) with an explicit stack.

Functionevaluate(formula)

formulaa number (int or float), or a list [op, left, right] where left and right are formulas

Returnsthe formula's value; ["-", a, b] is a - b (left minus right)

Constraintmust work for formulas 1,200 levels deep

Examples

callevaluate(['-', ['*', 3, ['+', 4, 5]], 2])returns25

callevaluate(['+', 1, 2])returns3

callevaluate(['*', ['+', 1.5, 2.5], ['-', 0, 3]])returns-12.0