Solved by 27 users: daniel.ugra, sridhar87, tomek, ethanhunt, dan, marek.cygan, tnsantosh, nishant, vviswa, scholl, e2n, LoLitter, JohnJones_001, Rizvanov, tourist, pmnox, vi002, WsemirZ, zloy_mipt, mazahaka, UdH-WiNGeR, Fat, Kuznetsov_S, defrager, RAVEman, Dest, EAA2008.
UserDateAttemptTimeCMSC
daniel.ugra`12 jan 2007`Ruby422.24320
Rizvanov`29 jan 2008`C++301.12443
ethanhunt`27 apr 2007`C++202.36522
ethanhunt`27 apr 2007`C++102.22534
JohnJones_001`18 oct 2007`C++900.40552
RAVEman`11 mar 2009`C++500.35579
nishant`03 jul 2007`C++302.55602
vviswa`03 jul 2007`C++102.59602
tomek`27 feb 2007`C++602.67634
LoLitter`17 oct 2007`C++300.14694
tnsantosh`18 jun 2007`C++4002.09713
tnsantosh`18 jun 2007`C++4102.09717
 C++ 23 Kylix 2 Java 1 Ruby 1
` >  >  >  >  >  >  >  >  >  > `

## Universal parser of expression

Time limit = 5 second(s)

Mathematical expressions consist of operators and operands. In turn some operators, such as '+', '-', '*' are associative, i.e. for any numbers a, b, c fairly following: a + (b + c) = (a + b) + c, and some haven't this property, for example, operators '/': (a / b) / c ≠ a / (b / c). If expression has no parantheses we should determine sequence of operator evaluation. The concept of the left and right associativity is defined. In programming languages each operator has the concrete priority and associativity.

Let we have a following set of operators:

PriorityAssociativityOperatorDescription
1right^exponentation
2left*multiplication
2left/division
3left-Subtraction

and expression 1+2*3-4/5/6*7^9^10+(7*8-1). To define sequence of evaluation we can just insert parantheses. Lets see abstract syntax tree:

Input. Some first lines describe operators. Operators listed in one line have same priority. Line number correspons to operator's priority. Each line begins with type of associativity (LEFT or RIGHT) operators containing in it, then (through a blank) operators are listed. After the description of operators one line setting the alphabet from which consist operands can follows. Last line contains expression in which it is necessary to place brackets. Input expression may contain brackets. Not all of them may present in output.

Output. One line containing expression, with the brackets placed in it. Number of brackets pairs should be equal to number of binary operators.

 Input#1```LEFT + - LEFT * / RIGHT ^ ALPHABET 0123456789 1+((2))*3-4/(5)/6*7^9^10+(7*8-1) ``` Output#1```(((1+(2*3))-(((4/5)/6)*(7^(9^10))))+((7*8)-1)) ```
 Input#2```RIGHT = RIGHT * / ALPHABET abcdefghijklmnop a=b=c=d*e*f*g*h/i/j/k/l ``` Output#2```(a=(b=(c=(d*(e*(f*(g*(h/(i/(j/(k/l))))))))))) ```
 Input#3```LEFT , RIGHT = += *= LEFT + - LEFT * / RIGHT ^ ALPHABET 0123456789abcdefghijklmnop abc=f,a=b+c+d/1/2/3,e+=f+=g+=add*4*5+6*7*8-9-10 ``` Output#3```(((abc=f),(a=((b+c)+(((d/1)/2)/3)))),(e+=(f+=(g+=(((((add*4)*5)+((6*7)*8))-9)-10))))) ```

Author:
Classic problem. Tests and descripton -- Tatiana Zinov'eva.
7 December 2006

 © acm.mipt DevGroupThe page was generated in 190ms