Compilers often optimize source code to make programs run faster. One common optimization is to evaluate constant expressions while compiling. For example, when compiling the expression "a * 4 * 3", you can first reduce it to "a * 12" before compiling it to machine code. You are to write a class Optimizer with a method reduce that takes a String, expression, and determines the minimum cost of evaluating the expression after it has been fully reduced. For this problem, we will only be considering add and multiply operations on a machine that takes 1 cycle to perform an add operation, and 10 cycles to perform a multiply operation. You should reduce the expression according to the following specifications:
- - Multiplication and addition are both commutative, e.g. "a * b" = "b * a" and "a + b" = "b + a".
- - Multiplication and addition are both associative, e.g. "(a * b) * c" = "a * (b * c)" and "(a + b) + c" = "a + (b + c)".
- - We have no guarantees that the values of the variables will stay the same throughout the computations, so an expression such as "3 * a + 4 * a" can not be reduced to "7 * a". In other words, you should treat each occurrence of a variable as if it was a unique variable.
- - "<expression> + 0" is always "<expression>", and "<expression> * 1" is always "<expression>". Similarly, "<expression> * 0" is always 0.
- - Any reductions that you make must follow directly from commutativity, associativity, the above rule, or from evaluating part of an expression that does not contain any variables. Thus, you may not reduce "a * 2" into "a + a" or vice versa, but you may reduce "(3 + 4) * a" to "7 * a" because you are evaluating a part of the expression that does not contain any variables.
Your method should reduce the expression as much as possible, following the above rules, and return the number of cycles required to evaluate the reduced expression, given that each addition takes 1 cycle, and each multiplication takes 10 cycles. When performing reductions, you must follow standard operator precedence rules: terms in parentheses are evaluated first, then multiplication, then addition.
The input string will be a well-formed <expression> conforming to the following grammar:
<expression> ::= <expression><op><expression> |
(<expression>) | <var> | <num>
<var> ::= a sequence of one or more lowercase letters ('a'-'z')
<num> ::= a sequence of one or more digits ('0'-'9')
<op> ::= '*' | '+'
<sp> ::= zero or more spaces (' ')