CCC '98 S4 - Lottery

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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:

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

or

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 Specification

The input to your program consists of a line containing an integer, , followed by lines of input. Each of the lines contains an expression consisting of integers, and the operators +, -, and 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 Specification

Your output should consist of the same lines, with a blank line between them, with parentheses inserted in the lines so as to indicate the order of operations. Multiplication should be done first, from left to right, 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

• commented on July 19, 2019, 7:00 p.m.

(1 + 2) - (3 X 4)

• commented on July 18, 2019, 5:58 p.m.

Should "1 + 2 - 3 X 4" return "(1 + 2) - (3 X 4)" or "1 + 2 - (3 X 4)"?