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.
UserDateAttemptTimeCMSC
bush`14 feb 2013`Ruby516.78102
bush`14 feb 2013`Ruby416.76112
stasg7`01 dec 2009`Ruby2615.31121
stasg7`01 dec 2009`Ruby1615.28139
Kuznetsov_S`30 apr 2009`Ruby216.87168
demo`12 nov 2008`Ruby1705.34171
greck`03 dec 2007`Ruby107.61171
Fat`19 apr 2009`Haskell600.62191
Fat`19 apr 2009`Haskell500.62228
Rizvanov`29 jan 2008`C++200.09236
lite`23 jan 2008`Scheme205.01283
Moonlight`28 feb 2009`C++300.04307
Ravent`06 jan 2008`C++500.14323
 C++ 31 Ruby 5 Java 3 Kylix 2 Haskell 1 Scheme 1 FPC 1 C 1
` >  >  >  >  >  >  >  >  >  > `

## 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

 © acm.mipt DevGroupThe page was generated in 220ms