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.
Time limit = 2
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
2 3 5 + *
You can compare the results of these equations using the Unix utilities bc
(infix) and dc (postfix):
$ bc <<< '2 * (3 + 5)'
$ dc <<< '2 3 5 + * 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
Put minimum number of parentheses.
You should take into account associativity of operations *
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
56 34 213.7 + * 678 -
1 56 35 + 16 9 - / +
1 2 3 * *
3 4 5 / *
3 4 * 5 /
3 4 5 / /
Well-known problem (http://www.rubyquiz.com). Tests and soluton by Artem Voroztsov
<PREV | Problem set | Search related messages | NEXT>