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
karthik_spoj1: 2020-10-04 15:27:49

maintaining two stacks makes it easier

appuk: 2020-09-10 17:14:10

im gettung a runtime error when submitting? can anyone help??


jjprioli: 2020-08-06 06:26:14

This one WAS stupid-easy, though I will admit I started to overthink it. (Hallmark of a good contest problem!)
AC in one go.

thetwinzycats_: 2020-08-05 10:02:18

lolololo

hemanth_ds: 2020-08-04 11:32:21

suggestion:Don't think deep,its doable!
hint: -
1)use stack.
2)observe input and output clearly to get logic.

Last edit: 2020-08-04 11:32:43
anurag_pandey_: 2020-07-29 04:39:32

May Anyone explain this problem?

zerothking: 2020-07-24 14:33:56

I solved it pretty easily using stacks by how can i solve it without stack? (Some people have said they have used recursion and some have used if-else blocks)

paritosh99: 2020-07-23 10:31:54

New to CP still AC in first attempt

khasrulalam: 2020-06-12 06:20:16

no need deep thinking

hello_1234: 2020-06-04 15:14:59

can anyone one explain this problem!!


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%
250 7