ONP - Transform the Expression

no tags 

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+^*

Added by:Michał Małafiejski
Date:2004-05-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: NODEJS PERL 6 SCM chicken VB.net
Resource:-

hide comments
VigneshR: 2015-03-24 15:48:32

Guys, My program works fine ideone. But I get sigsev in SPOJ. I am not sure what is the problem. SPOJ should say for what input it fails. Failing to do that makes it less interesting to continue in SPOJ.

Vijay: 2015-03-18 17:09:15

Guys, for the test cases given above my code returns correct results in spite of which I get wrong answer as result. Can anyone please help?

Tony T.: 2015-03-17 06:47:14

Spent a lot of time fiddling with scanf for strings in ideone. Led to runtime errors.
Resolved by switching to iostream.

sumit suthar: 2015-03-02 07:17:44

no need to check precedence.nice problem.learn a lot.

Abhyudaya Ranglani: 2015-02-21 15:38:45

I've been struggling like crazy to get rid of NZEC. I am almost certain that this code (http://ideone.com/********) deals appropriately with all possible statements that may throw exceptions. I think the memory constraint might be the issue here. Would appreciate any help.


(Francky) => Kindly read the notes, and use forum for any help.

Last edit: 2015-02-21 15:53:05
Serene Brackets: 2015-02-18 04:55:45

It's good that you people know the answer, but don't give the hints here. Let people figure it out and have fun doing it.

thelazycoder: 2015-02-13 18:17:40

learnt a new thing from this question .. good question

Shubham Kaushik: 2015-02-10 17:01:28

http://ideone.com/Y3nRP0
Please let me know what is wrong in the solution...As it works fine on ideone also

Indian Cyber Army (IndiShell): 2015-01-31 13:49:06

stack implementation

Shabeeb Hashim: 2015-01-26 07:51:21

Fully parenthesized expression :),so no need to use infix to post fix conversion algorithm,it is simpler than that...


Problem's scores 1 vote

Concept difficulty
Concept difficulty 14%
Implementation difficulty
Implementation difficulty 5%
5