Evaluate an infix formula with parentheses

Question

Evaluate an arithmetic expression given as a plain string, honoring * / over + - and any nesting of parentheses.

"2 + 3 * (4 - 1)"  ->  11.0
"10 - 2 - 3"       ->  5.0

Return the numeric value of the expression. Support + - * /, parentheses, spaces, and multi-digit / decimal numbers.

Accepted Answer

Use two stacks: one for numbers, one for operators (the shunting-yard idea). Read left to right. Numbers push onto the number stack. An opening parenthesis pushes onto the operator stack; a closing one resolves operators back to the matching open. For a normal operator, first resolve any pending operator of equal-or-higher precedence, then push it. At the end, drain remaining operators. For "2 + 3 (4 - 1)", the parenthesis resolves to 3, then 3 3 = 9, then 2 + 9 = 11. Time O(n), space O(n). Edge cases: left-associativity for - and / is preserved by resolving equal-precedence operators before …

Evaluate an infix formula with parentheses

Your answer

More Coding questions