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

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


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