Submit  All submissions  Best solutions  Back to list 
RPN  Reverse Polish notation 
Wersja polska  English version 
Your task is to transform the expression with brackets into RPN form.
Priority: +  < * / < ^ < ( )
Input
The first line of the standard input contains one integer t (t<101) which is the number of test cases.
In each of the next t lines there is a string consisted of twoargument operators: +, , *, /, ^, brackets ( ) and letters az (operands).
Output
For each test case print the expression in RPN form.
Example
Input:
4
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
((ag)^l/c^h*(l^fg^y)^i^j)
Output:
abc*+
ab+zx+*
at+bac++cd+^*
agl^ch^/lf^gy^i^j^*
Information
You can win PenDrive 16 GB in this competition: contest.pl by solving a task similar to this. It's in Polish but it's just a task like this.
The difference is that the only language which is available is C. Also, if You want to win You have to have code which is not longer than 80 character.
The reward may not be very encouraging but it's to feel rivalry and satisfaction.
Edit (19.02.11): Competition has ended. Mateusz Gołębiewski from Poland has written code of length... 78 chars! Congratulations!
Notice
I made a mistake and exponentation in the task is leftassociative while it should be rightassociative.
Despite the mistake, I do not change tests so that all users who have already done this task didn't have to rewrite their programs.
I would like to apologise for the situation.
Special thanks to hallvabo who discovered this mistake.
Added by:  Piotr Kąkol 
Date:  20100319 
Time limit:  0.180s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: SCM qobi 
Resource:  Reverse Polish notation 
hide comments


20140418 12:33:27 Piotr KÄ…kol
Let's say it's 200. 

20140417 17:12:51 Giovanni Botta
Is there a limit on the total size of the input in number of chars? 

20110219 17:47:03 Piotr KÄ…kol
Done. Thank You for finding the mistake and informing me! Last edit: 20110219 17:47:13 

20110213 12:43:31 Hallvard Norheim Bø
Just leave it as it is. Maybe mention it in the problem description? 

20110210 13:42:41 Piotr KÄ…kol
Yes, I know. Frankly saying, I read this article to find out what rightassociative means. But I'm glad to have learned it. Thanks. :) I understand that it's a mistake, but don't You think that it doesn't make a huge difference in programs to implement wrong algorithm? Because after changing the task I would have to rejudge all submissions and all of them would get WA, so maybe it isn't a good idea to change it now (after over half a year from adding this task). What do You think? Last edit: 20110210 13:44:11 

20110209 09:07:30 Hallvard Norheim Bø
Yes. Exponentiation operator usually groups from right, so a^b^c is a^(b^c), not (a^b)^c. See http://en.wikipedia.org/wiki/Operator_associativity. 

20110208 19:29:17 Piotr KÄ…kol
You mean 5^{67} should be 5^{279936}, not 15625^{7}? // As for the contest, somebody has already written a program which has... 78 chars! And after sharing it in comment he was beaten by 1 char more! So now the record is 77 chars. Here's the code: main(c){read(0,&c,1)?c41&&main(c40&&(c%96<27main(c),putchar(c))):exit(0);} Congratulations for Mateusz Gołębiewski (matix2267)! Last edit: 20110208 19:32:25 

20110207 04:04:39 Hallvard Norheim Bø
Shouldn't exponentiation be rightassociative? Last edit: 20110207 04:05:04 

20100509 12:35:23 Piotr KÄ…kol
For his program it gives different answer. ;) // I deleted the phrase: "priority from the lowest to the highest". Last edit: 20100509 12:36:45 

20100508 07:09:36 HWK
But the sentence "priority from the lowest to the highest" is IMHO misleading. Edit: The last test doesn't give different results. E.g. it would do if you'd change * and /. Last edit: 20100508 07:34:54 