### 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

**Problem Types:**[Show]

**Languages Allowed:**

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

## Comments (Search)

ryuugaon Jul 16, 2010 - 3:26:26 am UTC not right to left?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?

bbi5291on Jul 16, 2010 - 5:17:35 am UTC Re: not right to left?