PROBLEM STATEMENT
Even children in lower grades learn how to use parentheses following the rule
that (a + b) * c == a * c + b * c.
Another thing they learn is how to transform polynomials of 'x' in normal form,
i.e. each exponent of 'x' should participate only once in the final result and
there should be no parentheses.
More formally, we define Expression in the following manner:
Expression ::= Number
| Variable
| ( Expression )
| Expression + Expression
| Expression * Expression
Number ::= <integer between 0 and 100 exclusive>
Variable ::= <the character 'x'>
Note that Expressions are represented by String objects and contain only
addition, multiplication, parentheses, numerical constants and the variable
'x'. Parentheses will take precedence over multiplication, and multiplication
will take precedence over addition. We call expressions that obey the
definition above 'well-formed'.
Some examples of well-formed expressions are:
1+2
(x+2)*x+1
(x+(3+x)+(4+5*x*x))*(x+3*x*4*x)
Some examples of malformed expressions are:
1+2+
(2+x)*(3+(4+x)
(2-x)*(2+x)
x+y
We define a normal form polynomial (NFP) of x as the polynomial of x with the
minimum number of terms (see definition of Term below), that satisfies:
NFP ::= Term
| Term + NFP
Term ::= Number1 * Variable ^ Number1
| Number1 * Variable
| Variable ^ Number
| Variable
| Number
Number ::= <any positive integer constant>
Number1 ::= <any positive integer constant > 1>
Variable ::= <the character 'x'>
Note that only the following characters are allowed in both Expressions and
NFPs:
'0'..'9', '+', '*', 'x'
In addition the '^' is allowed in NFPs.
No spaces whatsoever!
DEFINITION
Class name: Expression
Method name: simplify
Parameters: String
Returns: String
Implement a class Expression, which contains a method simplify. The method
should take an Expression (in the form of a string) as an argument and convert
that Expression to an NFP, returning the result (again as a String).
The method signature is (make sure your method is public): String simplify
(String expression);
TopCoder will ensure that:
* expression will satisfy the definition above, including that all numbers K
satisfy 1 <= K <= 99
* expression will be less than 50 characters in length
* all coefficients in the result will be strictly smaller than 1000000
You should ensure that:
* the result returned should be sorted by descending exponents of x.
* the solution should run in under 6 seconds on TopCoder's tester.
Examples:
expression: x+x
result: 2*x
expression: (x+2)*(x+3)
result: x^2+5*x+6
expression: (x+2*(x+3))*(3*(5+x)+5)
result: 9*x^2+78*x+120