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
gurjits909: 2016-05-31 10:25:22

but in my compiler its execution is normal
and when i upload it ,it show segmentation fault

get_right_jr: 2016-05-31 07:56:56

Infix to Postfix

avisheksanvas: 2016-05-17 16:30:29

Priority rule implementation isn't necessary.
And don't think of skipping a[0] and a[len-1]. They're not always brackets :p

mrhex: 2016-05-13 21:04:39

All operators have the same priority. Parentheses are always used, just like in the examples. Explanation should be clearer, because without parentheses and with different operator priority it is quite difficult.

mohitgupta07: 2016-05-13 20:39:32

ac in a go :P :P using string,string buffers are much better than creating a stack :D :D ...Java everywhere :P :P
hint:- study ur ds book :P :P

bhushangawde: 2016-05-13 12:21:14

its sayn size exceeded. what shud i do please suggest

boney_412: 2016-05-08 23:05:59

yeah AC!!

cs02480: 2016-05-08 12:02:59

any trick in redaing data from stdin i am looking for'\n' string to finish .Geting segmentation fault while reading data

Last edit: 2016-05-08 12:06:52
chandansirola: 2016-04-18 16:52:15

done (y)

Last edit: 2016-04-18 16:55:21
jkaszycki: 2016-04-16 21:18:21

Reverse Polish Notation is such:
2 2 +
Not
2 + 2
Mind the gap...


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 23%
Implementation difficulty
Implementation difficulty 24%
264 7