SPOJ.com - Problem RPN

Problem hidden

This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

RPN - Reverse Polish notation

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 two-argument operators: +, -, *, /, ^, brackets ( ) and letters a-z (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)))
((a-g)^l/c^h*(l^f-g^y)^i^j)
Output:
abc*+
ab+zx+*
at+bac++cd+^*
ag-l^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 left-associative while it should be right-associative.

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.

Submit solution!

Added by:	Piotr Kąkol
Date:	2010-03-19
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: SCM qobi
Resource:	Reverse Polish notation

hide comments

2014-04-18 12:33:27 Piotr KÄ…kol
Let's say it's 200.

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

2011-02-19 17:47:03 Piotr KÄ…kol
Done. Thank You for finding the mistake and informing me!

Last edit: 2011-02-19 17:47:13

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

2011-02-10 13:42:41 Piotr KÄ…kol
Yes, I know. Frankly saying, I read this article to find out what right-associative 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: 2011-02-10 13:44:11

2011-02-09 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.

2011-02-08 19:29:17 Piotr KÄ…kol
You mean 5^6⁷ should be 5²⁷⁹⁹³⁶, not 15625⁷?

// 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)?c-41&&main(c-40&&(c%96<27||main(c),putchar(c))):exit(0);}
Congratulations for Mateusz Gołębiewski (matix2267)!

Last edit: 2011-02-08 19:32:25

2011-02-07 04:04:39 Hallvard Norheim Bø
Shouldn't exponentiation be right-associative?

Last edit: 2011-02-07 04:05:04

2010-05-09 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: 2010-05-09 12:36:45

2010-05-08 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: 2010-05-08 07:34:54

Shortening codes