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-03-09 08:26:19
Ching Cheng HanJi
2020-03-03 11:55:03
nice one :)

Last edit: 2020-03-03 11:56:29
2020-02-22 16:48:19
use stacks
2020-01-20 16:44:04
Solved it using binary expression tree. Class Tree that has pointers to the left and right subtrees and two functions one fills the tree from the input string and the second one reads it in postfix traversal.
2020-01-14 07:52:29
Easy just think on paper then code one by one
2020-01-06 17:32:16
AC in one go :)
2020-01-05 08:42:31
The problem is intresting and good. But the question could have be more clear.
2020-01-01 16:13:14
how to submit correct format input ?
2019-12-01 20:40:51
my code runs perfectly on my pc. but its showing WA here. What to do?
2019-12-01 08:10:15
In this case (a+(b+d)^k) is it abd+k^+ ? . Please correct me if I'm wrong
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.