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-06-12 06:56:34
anyone done this is #c
2015-06-06 12:33:41 candide
RPN is a little cryptic, isn't it? IMO there are many spoj problems giving more fun and less popular so why this question is so popular (rank 6)?
Remark : Wording specifies operators priority hierarchy but this is misleading : input always comes with fully parenthesized expressions.

Last edit: 2015-06-13 11:24:37
2015-05-20 09:12:13
You will step up from amateur level after solving this
2015-05-17 18:04:07
my code went well in ideone.but its not working in this spoj compiler .and i did it in c
so please help me with that .dont mind fr the large code .PS .i m an amateur
<snip>

Last edit: 2023-02-09 23:11:42
2015-04-14 09:58:55
where can we get its testing data,
2015-04-12 18:37:27 ARS Rana
for input a*b*c or a+b+c or a^b^c
what will be output?

Last edit: 2015-04-12 19:25:01
2015-03-24 15:48:32 VigneshR
Guys, My program works fine ideone. But I get sigsev in SPOJ. I am not sure what is the problem. SPOJ should say for what input it fails. Failing to do that makes it less interesting to continue in SPOJ.
2015-03-18 17:09:15 Vijay
Guys, for the test cases given above my code returns correct results in spite of which I get wrong answer as result. Can anyone please help?
2015-03-17 06:47:14 Tony T.
Spent a lot of time fiddling with scanf for strings in ideone. Led to runtime errors.
Resolved by switching to iostream.
2015-03-02 07:17:44 sumit suthar
no need to check precedence.nice problem.learn a lot.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.