National University of Singapore

Vanishing Parentheses

Your top secret organization does a lot of cool stuff, and they don’t like to talk about what’s going on. However, they have told you that something has gone horribly wrong transferring very important mathematical formulae from somewhere to somewhere else; all of the parentheses have vanished! The values to these formulae are vital to some sort of very important system. Fortunately, the people that run the system can simply try answers in what you assume are control systems of some sort until things work. They don’t want to spend the time trying all integers, so your boss has assigned you to write a program to help out with the missing parenthesis.

Write a program that puts sets of parentheses back in the formulae and generate all possible answers it can produce for different ways of applying parentheses. You can put in as many sets of parentheses as you need to get all of the unique answers. For example, you might have the formula $1 + 2 \cdot 3 + 4$. You could put the parentheses and get formulae like these: $(1+2\cdot 3+4)$, $(1+2)\cdot 3+4$, $(1+2)\cdot (3+4)$, $((1+2)\cdot 3)+4$, $1+(2\cdot (3+4))$, which would give you the answers $11$, $13$, $15$, and $21$ respectively.


Input has up to $100$ formulas, one per line, ending at end of file. Each formula alternates between integers (in the range $[-2^{31},2^{31}-1]$) and the three basic arithmetic operators of addition, subtraction, and multiplication (+, -, *), separated by whitespace. Each formula begins and ends with an integer. Each formula contains at most ten integers.


Output the unique numeric values that each formula can produce using different parentheses, one value per line, in increasing order. Separate output for adjacent test formulae with a blank line. All inputs have the property that the computations for any valid set of parentheses can be done while maintaining the range of $[-2^{31},2^{31}-1]$ for all intermediate values.

Sample Input 1 Sample Output 1
2 * 4
2 * 3 + 4 * 6