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
2020-10-17 18:56:56
did using stl stack will effect the time ?

Last edit: 2020-10-17 19:09:54
2020-10-06 06:31:28
I dont understand of all solution i have gone through, none of them considered associativity in solution. All solutions were based on precedence. why?
Is it beacuse all of the operators given in question are left to right associative?

Last edit: 2020-10-06 06:34:35
2020-10-04 15:27:49
maintaining two stacks makes it easier
2020-09-10 17:14:10
im gettung a runtime error when submitting? can anyone help??


2020-08-06 06:26:14
This one WAS stupid-easy, though I will admit I started to overthink it. (Hallmark of a good contest problem!)
AC in one go.
2020-08-05 10:02:18
lolololo
2020-08-04 11:32:21
suggestion:Don't think deep,its doable!
hint: -
1)use stack.
2)observe input and output clearly to get logic.

Last edit: 2020-08-04 11:32:43
2020-07-29 04:39:32
May Anyone explain this problem?
2020-07-24 14:33:56
I solved it pretty easily using stacks by how can i solve it without stack? (Some people have said they have used recursion and some have used if-else blocks)
2020-07-23 10:31:54
New to CP still AC in first attempt
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.