<PREV Problem:
NEXT>
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.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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+addition
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:

The answer is unique: (((1+(2*3))-(((4/5)/6)*(7^(9^10))))+((7*8)-1))

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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 160ms

SW soft NIX
ID = 23.20.13.165