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
2017-09-12 21:27:55
Solved such problem even in my computer science class in university
2017-07-22 13:22:56
a*(b+c) is a b c + *,but accepts abc+ also.weak test cases.
2017-07-20 11:27:54
AC in a go.. :D
2017-07-15 19:55:52
O(n) solution bois!!!
2017-06-26 23:03:04 Jacek Kupiec
AC in One!!!
2017-06-19 10:15:30
http://www.dcode.fr/reverse-polish-notation
Great tool for checking your results with the algorithm :).

Last edit: 2017-06-19 10:16:04
2017-05-29 12:57:53
weak test cases
2017-05-28 18:06:50
i'am getting ac on codechef but wrong answer on spoj can any one help?
2017-05-24 17:12:33
Nice..Solved it using structures instead of stack<>..feels good.
2017-05-22 17:06:59
I tried using strings and my program pass in test cases. But its failing when submitting. The outputs are also printed in new line. What can be the reason? pl post any test cases. Its failing in codechef also
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.