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-01-05 15:21:36 karan
yepppppp :P :P pinku..

Last edit: 2015-01-13 19:42:55
2015-01-04 06:53:58 jaswin kaur
this problem was motivational
2015-01-03 18:50:39 Shubham
I am not able to implement the Shunting Yard Algorithm for this problem. Is there any other way/algo for this?
2014-12-30 10:47:24 arjun
Do Note that, u r using pointers in this program and as there is only one operator between two operands, so there is no need to check priority.

Enjoy Coding.
2014-12-28 16:17:42 Avinash Raj
Done :) after a few attempts.

Last edit: 2014-12-29 19:15:19
2014-12-25 15:55:12 Akshay Damle
AC in 1st go :D Thanks to 12th std. CBSE CS that taught this with stacks
2014-12-05 10:18:11 Nikola Krstic
Today i learn something new, that is RPN (firts time i heard for it xD ) Good Job SPOJ :)
2014-11-09 00:45:40 gamer496
i learn't something even from this simple problem i love spoj
2014-10-16 11:32:26 jinkies
pretty easy, no need to check priority
2014-10-07 07:09:10 Rohit Retnakaran
I think all the test cases have parenthesis to begin with.... :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.