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#156 34 213.7 + * 678 - Output#156*(34+213.7)-678
 Input#21 56 35 + 16 9 - / + Output#21+(56+35)/(16-9)
 Input#31 2 3 * * Output#31*2*3
 Input#43 4 5 / * Output#43*4/5
 Input#53 4 * 5 / Output#53*4/5
 Input#63 4 5 / / Output#63/(4/5)

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

 © acm.mipt DevGroupThe page was generated in 200ms