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
im_115: 2021-02-01 14:04:03

Do we have to assume that the given algebraic expression will always be correct?

sir_im_dead_0: 2021-01-22 04:36:57

I just wanna leave this here for the next person who does this:
You're gonna see lots of guys below say use a stack(and yes, try using one)
While you're gonna have to put some thought into it, draw out some patterns and observations, and you should be fine : )

hrithox_2000: 2020-12-27 05:26:31

it was a very good problem.i take 2 hours to think it but the solution was very easy.

naens: 2020-12-22 20:29:00

I used AST and recursive descent. It seems I'm the only one here... Made in python, used tuples for the AST nodes...

arafat_123: 2020-12-20 20:44:37

Very easy. Got AC in one go. Yeaaa

poorva_s__7__: 2020-11-27 02:55:22

Don't worry about loops, STL works, complexity can be handles with more indented loops

dileep_32: 2020-11-04 15:44:33

i thought it was hard one , but i solved it with little effort

tomatoispotato: 2020-10-29 08:23:42

I solved it in first attempt without any help using recursion, though my method is very inefficient. I'm so happy, I am gonna try this again with more efficient method.

Last edit: 2020-10-29 08:26:32
vardhman811: 2020-10-17 18:56:56

did using stl stack will effect the time ?

Last edit: 2020-10-17 19:09:54
bhanu_1023: 2020-10-06 06:31:28

I dont understand of all solution i have gone through, none of them considered associativity in solution. All solutions were based on precedence. why?
Is it beacuse all of the operators given in question are left to right associative?

Last edit: 2020-10-06 06:34:35

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