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
2021-06-02 12:20:49
lessgoo
2021-05-23 21:47:19
The problem statement grossly overstates how complex the input can be. I did not have to account for operator precedence at all, and I could assume every 2 operand sub-expression would have brackets around it!
2021-02-01 14:04:03
Do we have to assume that the given algebraic expression will always be correct?
2021-01-22 04:36:57
I just wanna leave this here for the next person who does this:
You're gonna see lots of guys below say use a stack(and yes, try using one)
While you're gonna have to put some thought into it, draw out some patterns and observations, and you should be fine : )
2020-12-27 05:26:31
it was a very good problem.i take 2 hours to think it but the solution was very easy.
2020-12-22 20:29:00
I used AST and recursive descent. It seems I'm the only one here... Made in python, used tuples for the AST nodes...
2020-12-20 20:44:37
Very easy. Got AC in one go. Yeaaa
2020-11-27 02:55:22
Don't worry about loops, STL works, complexity can be handles with more indented loops
2020-11-04 15:44:33
i thought it was hard one , but i solved it with little effort
2020-10-29 08:23:42
I solved it in first attempt without any help using recursion, though my method is very inefficient. I'm so happy, I am gonna try this again with more efficient method.

Last edit: 2020-10-29 08:26:32
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.