Given an expression of one-letter variables (
[a-z]), operators (
*, +, &) and parenthesis, expand it using the following axioms:
a * b != b * a a * b * c = (a * b) * c = a * (b * c) a + b = b + a a + b + c = (a + b) + c = a + (b + c) a * (b + c) = a * b + a * c a & b = b & a a & (b + c) = a & b + a & c | Comm | Assoc | Dist * | NO | YES | + | YES | YES | * & | YES | YES | + *
The user will input an expression, the syntax of the input expression is called "input form". It has the following grammar:
inputform ::= expr var ::= [a-z] // one lowercase alphabet expr ::= add | add & expr add ::= mult | mult + add mult ::= prim | prim * mult | prim mult prim ::= var | ( expr )
That means, the order of operations is * + &,
a + b * c & d + e = (a + (b * c)) & (d + e)
Furthermore, the operator
* can be omitted:
a b (c + d) = ab(c + d) = a * b * (c + d)
Whitespace is stripped out before parsing.
(a + b) * (c + d) = (a + b)(c + d) = (a + b)c + (a + b)d = ac + bc + ad + bd (a & b)(c & d) = ac & ad & bc & bd (a & b) + (c & d) = a + c & a + d & b + c & b + d ((a & b) + c)(d + e) = ((a & b) + c)d + ((a & b) + c)e (I'm choosing the reduction order that is shortest, but you don't need to) = ((a & b)d + cd) + ((a & b)e + ce) = ((ad & bd) + cd) + ((ae & be) + ce) = (ad + cd & bd + cd) + (ae + ce & be + ce) = ad + cd + ae + ce & ad + cd + be + ce & bd + cd + ae + ce & bd + cd + be + ce
Due to commutativity, order of some terms do not matter.
Your program will read an expression in input form, and expand the expression fully, and output the expanded expression in input form, with one space separating operators, and no spaces for multiplication. (
a + bc instead of
a+b * c or
a + b * c or
a + b c)
The fully expanded form can be written without any parens, for example,
a + b & a + c is fully expanded, because it has no parens, and
a(b + c) is not.
Here is an example interactive session (notice the whitespaces in input)
$ expand > a(b + (c&d)) ab + ac & ab + ad > x y * (wz) xywz > x-y+1 Syntax error > c(a +b Syntax error