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
theslowcoder: 2020-01-20 16:44:04

Solved it using binary expression tree. Class Tree that has pointers to the left and right subtrees and two functions one fills the tree from the input string and the second one reads it in postfix traversal.

pprathamesh: 2020-01-14 07:52:29

Easy just think on paper then code one by one

kartikeya18c: 2020-01-06 17:32:16

AC in one go :)

dharan1011: 2020-01-05 08:42:31

The problem is intresting and good. But the question could have be more clear.

truong62: 2020-01-01 16:13:14

how to submit correct format input ?

ag2byte: 2019-12-01 20:40:51

my code runs perfectly on my pc. but its showing WA here. What to do?

alone_musk: 2019-12-01 08:10:15

In this case (a+(b+d)^k) is it abd+k^+ ? . Please correct me if I'm wrong

perl_add_add: 2019-09-27 08:44:36

I am Chinese who is interested in SPOJ and Poland.

gautam97: 2019-09-16 17:18:54

i am getting SIGABRT averytime

neerajamoniya: 2019-08-03 08:05:56

It's very easy. No recursion or stacks and queue required.


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 23%
208 6