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
abhi_96: 2017-07-22 13:22:56

a*(b+c) is a b c + *,but accepts abc+ also.weak test cases.

nikkitricky: 2017-07-20 11:27:54

AC in a go.. :D

brodzik1337: 2017-07-15 19:55:52

O(n) solution bois!!!

Jacek Kupiec: 2017-06-26 23:03:04

AC in One!!!

azazello_: 2017-06-19 10:15:30

http://www.dcode.fr/reverse-polish-notation
Great tool for checking your results with the algorithm :).

Last edit: 2017-06-19 10:16:04
abhishekrahul: 2017-05-29 12:57:53

weak test cases

ak18shay: 2017-05-28 18:06:50

i'am getting ac on codechef but wrong answer on spoj can any one help?

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

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 22%
88 3