| Submit | All submissions | Best solutions | Back to list |
RPN - Reverse Polish notation |
| Wersja polska | English version |
Twoim zadaniem jest zamiana wyrażenia w nawiasach na ONP (Odwrotną Notację Polską).
Priorytet: + - < * / < ^ < ( )
Wejście
W pierwszej linii znajduje się liczba testów t (t<101).
Każda z kolejnych t linii zawiera ciąg znaków (operatorów: +, -, *, /, ^, nawiasów ( ) oraz liter a-z).
Wyjście
Dla każdego testu wypisz wyrażenie w ONP.
Przykład
Wejście:
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)
Wyjście:
abc*+
ab+zx+*
at+bac++cd+^*
ag-l^ch^/lf^gy^-i^j^*
Informacja
Możesz wygrać PenDrive'a 16 GB w tym konkursie: contest.pl rozwiązując zadanie podobne do tego (strona jest po polsku).
Jednak jedynym dostępnym językiem jest C. Ponadto, jeśli chcesz wygrać, musisz napisać kod krótszy od 81 znaków.
Nagroda może i nie jest zbyt zachęcająca, ale chodzi przecież o rywalizację i satysfakcję.
Edit (19.02.11): Konkurs został zakończony. Mateusz Gołębiewski (bądźmy dumni!) napisał... 78-znakowy kod! Gratulacje!
Uwaga
Popełniłem błąd zakładając, że potęgowanie jest lewostronne, kiedy powinno być prawostronne.
Pomimo błędu, nie będę zmieniał testów, żeby użytkownicy, którzy zaliczyli już to zadanie, nie musieli poprawiać swoich programów.
Przepraszam za kłopot.
Specjalne podziękowania dla użytkownika hallvabo, który znalazł ww. błąd.
| 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 567 should be 5279936, not 156257? // 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 |
|||||
RSS