### 1999 Canadian Computing Competition, Stage 2

## Day 2, Problem 2: Sum of Products

Mathematicians, as opposed to computer scientists, write expressions using single lower case letters as variables. Addition is represented by a plus sign and multiplication is represented by placing the variables or expressions adjacent with no symbol in between. Multiplication is done before addition unless the addition is parenthesized.

For this problem, we consider mathematical expressions consisting of only variables, addition, multiplication, and parentheses. (There are no other symbols, like spaces, division, subtraction, or numerals in the input or output.) For example,

a+b+c xyz xyz+ab+cd (a+b)(c+d)e

Your task is to read in a number of expressions in this notation and to rearrange each, using the laws of algebra, to equivalent expressions with no parentheses. For example,

(a+b)(c+d)e

can be re-expressed as

ace+ade+bce+bde

Once you have finished removing the parentheses, sort each of the terms in alphabetical order (e.g `cae`

should be come `ace`

). Then, sort all the terms in *dictionary* order (e.g. `a`

comes before `ab`

, but `abe`

comes before `ac`

)

### Input

The first line of input contains an integer *n*. *n* lines of
input follow, each containing a valid expression as described above.
No input line exceeds 100 characters.

### Output

Your output should consist of *n* lines, each giving a parenthesis-free expression equivalent to
the corresponding line of input.

### Sample Input

5 a+b+c (a+b)(c+d)e c+cb+a+c ((a+b)+(c+d))e (a+a)(a+a)

### Sample Output

a+b+c ace+ade+bce+bde a+bc+c+c ae+be+ce+de aa+aa+aa+aa

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Apr 19, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...