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+^*

hide comments
horizon121: 2017-05-24 17:12:33

Nice..Solved it using structures instead of stack<>..feels good.

arvind_1995: 2017-05-22 17:06:59

I tried using strings and my program pass in test cases. But its failing when submitting. The outputs are also printed in new line. What can be the reason? pl post any test cases. Its failing in codechef also

boyue: 2017-04-26 19:48:54

Last edit: 2017-04-27 07:00:48
codershan2new: 2017-04-24 06:35:44

I used to think this problem is complicated, but it's effin' easy!

vietanknb: 2017-04-22 12:35:58

nice problem :D

nachi_w: 2017-03-18 16:19:59

AC in one go.
I'm a noob when it comes to programming.This gave some confidence.

xprilion: 2017-03-17 17:55:13

AC in One without stack :D My first AC in one! ^_^ time taken: 0.00 :P

Last edit: 2017-03-17 17:56:37
ANKIT JAIN: 2017-03-10 19:56:25

AC in one go :)

p3arl_03: 2017-02-20 10:49:27

AC in one go, took 0.07 sec!!
Where to see test cases of problems?? Anyone knows??

cat_got_bored: 2017-02-17 20:20:05

Not enough tricky cases.


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:-

Problem's scores 1 vote

Concept difficulty
Concept difficulty 22%
Implementation difficulty
Implementation difficulty 21%
84 3