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

Omar: 2017-02-15 10:24:48

Accepted in one go , 0.00 in cpp 14 , it's just a direct implementation of Shunting yard algorithm ( from infix to postfix).

piyushmittal: 2017-02-13 18:03:09

AC in one go,also take 0.00 sec

rogue_007: 2017-01-30 17:23:40

AC means accepted guys!!

shreeshiv: 2017-01-29 06:05:04

What is mean by AC??

starbot: 2017-01-28 07:07:04

yayayay....AC in one go...too happy...did it without stack, was on my todo list for a long time.....my 103rd!!!!!!!!!

harsh123_: 2017-01-21 22:18:24

Very weak test cases...I realized after 3 months that my solution was wrong.

kira28: 2017-01-11 11:46:17

Very weak testcases :/
Even a wrong code of mine was accepted.... xD xD xD

psiphon_exe: 2017-01-06 10:53:13

Stacks stl


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%
78 3