Sphere Online Judge

SPOJ Problem Set (classical)

4. Transform the Expression

Problem code: ONP


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
Resource:-

hide comments
2014-10-30 21:13:52 jose maria
i can't understand. The program run ok in ideone, but when i try to put in spoj, say time exceded ?, can someone help me?
2014-10-21 13:48:42 Shivin
what does priority of operators mean exactly?
2014-10-16 11:32:26 esemzV
pretty easy, no need to check priority
2014-10-07 07:09:10 The one who never told the truth.....
I think all the test cases have parenthesis to begin with.... :)
2014-10-02 10:10:47 nrl 7
It seems all the test cases have brackets. Hence you can keep priority of + and - same or different, it wont matter.
2014-09-29 20:13:59 Hot-Shot
recursion is my sole mate
2014-08-30 14:31:36 saikat
0.00 1.6M in C.. The best code..
2014-08-22 08:53:47 Gaurav Ahirwar
Xtremely Simple logic! ..just give it a try! :)
2014-08-21 14:57:49 Emanuele Paolini
I think that for clarification the expression a-b+c-d should be added to the examples. Priority of operators is not shown in any example.
2014-01-28 10:02:35 Shatha Abu Hashem
Ugh .. I Just cannot find the algorithm .. it drives me crazy
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.