ONP - Transform the Expression

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a, b ... z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Added by:mima
Date:2004-05-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:-

hide comments
2015-07-19 00:37:02
A good algorithm for solving this problem:
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
2015-07-16 16:18:53
Could someone tell me what is wrong in my code <snip> compile and works well but spoj detects runtime error (SIGSEGV)

Last edit: 2023-02-09 23:11:24
2015-07-14 13:52:23 Supreme
Tried solving without using stacks - didnt get the solution even after 2 days.
Tried solving implementing stacks - got the solution within 1.5 hour.

Got to know the power & importance of stack.
2015-07-13 18:25:28 himanshu kumar
please do see the priority hehe... giving me one wrong answer :p
2015-06-28 15:09:30
STL made code shorter......Excellent problem for beginners.......
2015-06-26 13:46:50 Tanuj Kumar
Can someone please tell whether it is possible for the SPOJ compiler to judge wrongly. Because my code worked fine on idone.com but it shows wrong answer here. P.S. My code is in C.

Here is my code <snip>


Last edit: 2023-02-09 23:10:40
2015-06-24 11:03:43
hint : stack is used for the implementation
2015-06-24 11:00:45
yeah AC in one go after thinking the algorithm about 1 hour haha, anyway, nice problem :)
2015-06-18 03:43:07
i used cin.getline() to read the input and got WA too many times......and then used cin>> and got AC.....also check that array size is atleast 400
2015-06-17 18:47:18 mohit
<snip>
My code showing wrong answer!!

Last edit: 2023-02-09 23:10:47
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.