1998 Canadian Computing Competition, Stage 1

Problem D: Lottery

You have just won the lottery. All that separates you from your multi-million dollar prize is your correct answer to the following skill-testing question:

1234 + 4567 X 11

In your twenty seconds you see your fortune slipping away because you don't know whether the answer is

(1234 + 4567) X 11 = 63811

or

1234 + (4567 X 11) = 51471

Finally you guess 63811, but that answer is incorrect. Your math teacher set the question and expected you to remember that multiplication is done before addition. The correct answer is 51471.

Your job is to write a program to insert parentheses into lottery questions such as the above so as to make clear the order of operations.

Input

The input to your program consists of a line containing an integer, n, followed by n lines of input. Each of the n lines contains an expression consisting of integers, and the operators +, -, and X (upper case X) denoting addition, subtraction, and multiplication respectively. Adjacent integers are separated by one operator. There is a single space to the left and to the right of each operator and no input line contains more than 80 characters.

Output

Your output should consist of the same n lines, with a blank line between them, with parentheses inserted in the n lines so as to indicate the order of operations. Multiplication should be done first, from right to left, and addition and subtraction should then be done from left to right. Spaces surrounding operators should be preserved.

Sample Input

3
10 + 20 X 30
1 + 2 + 3 - 4
123 + 456 X 789 - 876

Sample Output

10 + (20 X 30)
 
((1 + 2) + 3) - 4
 
(123 + (456 X 789)) - 876

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008

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

Comments (Search)

if multiplication is done right to left, then it should look like:
A X (B X (C X D))
but solution is only accepted when it is formatted like addition is (left to right?):
that is, ((A X B) X C) X D
is the judge wrong?

I assume the problem statement is in error, since multiplication is supposed to be done from left to right. But it does also say "right to left" in the originals, so I suppose it's Waterloo's fault.