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
botter_code: 2021-06-02 12:20:49

lessgoo

kpjoshi: 2021-05-23 21:47:19

The problem statement grossly overstates how complex the input can be. I did not have to account for operator precedence at all, and I could assume every 2 operand sub-expression would have brackets around it!

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

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 23%
256 7