TopCoder problem "Optimizer" used in TCCC '03 Round 4 (Division I Level Three)



Problem Statement

    

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> |
                       <sp><expression><sp> | 
                       (<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 (' ')
 

Definition

    
Class:Optimizer
Method:reduce
Parameters:String
Returns:int
Method signature:int reduce(String expression)
(be sure your method is public)
    
 

Notes

-Be sure to only apply the reductions mentioned in the problem statement. In particular, note that we are not applying the distrubutive property of addition and multiplication. See example 7.
-A common way to represent the structure of the expression is to build a tree, where each internal node represents an operation ('+' or '*') and each leaf represents a variable or number.
 

Constraints

-expression will contain between 1 and 50 characters, inclusive.
-expression will conform to the grammar defined above.
-Each <num> will represent an integer between 0 and 2^32-1, inclusive.
-The numbers in fully reduced expressions will not exceed 2^32-1.
 

Examples

0)
    
"  alpha*beta+5*006  "
Returns: 11
This can be reduced to "alpha * beta + 30", which has one multiplication and one addition.
1)
    
"a * b * 00 + 1 * 5"
Returns: 0
This can simply be reduced to "5" which requires no evaluation.
2)
    
"dx + a * b * 0 + 1 * c"
Returns: 1
3)
    
"5 * (3 + 4 + c) + (a + c) * (c + d)"
Returns: 24
This can be reduced to "5 * (7 + c) + (a + c) * (c + d)" which has 4 additions and 2 multiplications. Note that we can not reduce "5 * (7 + c)" to "35 + 5 * c" because that reduction is a property of distributivity, and is not one of the allowed reductions.
4)
    
"9 * ((4 + 4)) * (7) * (3 + 1) + 504"
Returns: 0
There are no variables here, so the compiler can evaluate the whole expression and reduce it to "2520"
5)
    
"((((aa))))"
Returns: 0
6)
    
"(1 + 0 * a) * c + (0 + 0 * b) * d"
Returns: 0
7)
    
"5 * d + 5 * b" 
Returns: 21
Remember that we are not applying the distributive property, so we cannot reduce this to "5 * (d + b)".
8)
    
"(a*5)*4+((a+4)+5)"
Returns: 12
Note that we can first change this to "a*(5*4)+(a+(4+5))" and then to "a*20+a+9".
9)
    
"(a*5)*(b*6)"
Returns: 20
10)
    
"(1)+0+1*(w+6)*1"
Returns: 1
We can reduce this to "w + 7"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1574

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4482&pm=1574

Writer:

lars2520

Testers:

brett1479 , schveiguy

Problem categories:

Math, String Manipulation, String Parsing