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
2014-10-02 10:10:47 nrl 7
It seems all the test cases have brackets. Hence you can keep priority of + and - same or different, it wont matter.
2014-08-22 08:53:47 Gaurav Ahirwar
Xtremely Simple logic! ..just give it a try! :)
2014-08-21 14:57:49 Emanuele Paolini
I think that for clarification the expression a-b+c-d should be added to the examples. Priority of operators is not shown in any example.
2014-01-28 10:02:35 Shatha Abu Hashem
Ugh .. I Just cannot find the algorithm .. it drives me crazy
2013-12-25 17:54:00 Bowen
"+, -, *, /, ^ (priority from the lowest to the highest)"
does - have higher precedence than + or are they the same? also with * and /?
2013-12-12 07:55:21 Duan Yichao
Write some more expressions yourself and try.
2013-08-28 19:54:59 Mayank Raj
Actually everything is bracketed...I coded to look only for the braces!!
2013-08-06 08:24:01 Franz Matejka
Suggestion: Add to problem statement that the algorithm just needs to work with fully bracketed expressions.
2013-07-09 18:19:53 (Tjandra Satria Gunawan)(曾毅昆)
0.05s in Brainf**k ;-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.