<PREV Problem:
NEXT>
Solved by 45 users: Lukasz16a, greck, tomek, zmy, JohnJones_001, dan, Tulegenov_Amir, rvashegin, Ravent, Romka, lite, Rizvanov, vi002, tourist, rem, Philip_PV, WsemirZ, pmnox, N1k1tung, Chmeli_BSU, zloy_mipt, demo, KZ, mazahaka, Kuznetsov_S, UdH-WiNGeR, RAVEman, Moonlight, defrager, tnsantosh, regal, abortmozga.ru, Fat, murphy, DAV, stasg7, deepakmanohar, Dest, EAA2008, Artur, s01A15, fetetriste, ethanhunt, ddtm, bush.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Minimize parentheses

Time limit = 2 second(s)

There are many different ways to write mathematical equations. Infix notation is probably the most popular and yields expressions like:
       2 * (3 + 5)
Some people like to work with a postfix notation (often called Reverse Polish Notation or just RPN) though, which doesn't require parentheses for the same equation:
       2 3 5 + *
You can compare the results of these equations using the Unix utilities bc (infix) and dc (postfix):
       $ bc <<< '2 * (3 + 5)'
       16
       $ dc <<< '2 3 5 + * p'
       16
The "p" instruction tacked onto the end of the expression for dc just tells it to print the result. Your task is to write a program that translates postfix expression into the equivalent infix expression. You can count on the postfix expressions having spaces between terms. Put minimum number of parentheses. You should take into account associativity of operations * and +.

Input: One line with postfix form of an expression. Allowed operators are +, -, *, /. Other tokens are nonnegative integer or real numbers which representations are less than 10 letters. Number of tokens in input expression is less than 60001.

Output: Infix form of the expression with minimal number of parentheses. Do not use spaces in it. Order of numbers should be the same as in input expression.

Input#1
56 34 213.7 + * 678 -
Output#1
56*(34+213.7)-678

Input#2
1 56 35 + 16 9 - / +
Output#2
1+(56+35)/(16-9)

Input#3
1 2 3 * *
Output#3
1*2*3
Input#4
3 4  5 / *
Output#4
3*4/5
Input#5
3 4 * 5 /
Output#5
3*4/5
Input#6
3 4 5 / /
Output#6
3/(4/5)

Author:
Well-known problem (http://www.rubyquiz.com). Tests and soluton by Artem Voroztsov

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


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

SW soft NIX
ID = 23.20.13.165