Book of programming problems

Complexity (1-100): 25

An arithmetic formula is written in a string containing only decimal digits and symbols '+', '-', '*', '/', '^' (exponentiation). There are no other symbols in the string. Evaluate the furmula.

Self-tests:

1. -1-5+6*7^3/8 = 251.25000
2. 2^2^2^2^2/65536 = 1.00000

One can group the operations by precedence like this:

1. numbers
2. ^
3. *,/
4. +,-

All the operations are left-associative: a op b op c = (a op b) op c. We here deliberately noted numbers as operation between digits: ab = a*10+b.

Let us solve the following subproblem: evaluate the formula a₁ op₁ a₂ op₂ ... op_n-1 a_n, where all operations op_i  are of the same precedence. The solution to the subproblem is obvious: we start at some initial value I  such that I op₀ a = a for some op₀ of the group of operators and number a.Then we iterate over the input string and modify the evaluator state according to the following rules:

1. if the input symbol is a number, than perform the last remembered operation or operation op₀ for the first number;
2. if the input symbol is an operation, we remember the operation to perform on the next number.
3. if the input symbol is an operation not from this group of operations, than return error.

operation group	I, op0	last operation encoding	value of a operation b
numbers	0		10a+b
^	NoPower		if a = NoPower then b else ab
*,/	(1, 1)	1 for '*', -1 for '/'	a*blast_operation
+,-	(0, 1)	1 for '+', -1 for '-'	a+last_operation*b

We can now solve the general problem: for each incoming symbol, we ask the corresponding operation group to update its context (that is, the current value and the last operation, if necessary). We pass the accumulated value of a higher precedence group of operations to the next lower group, so that "2^3" in "1+2^3*5" appear as a number to the operation '*'.