Lista 13 (24 stycznia 2006): 11 punktów.

Argumenty wywołania programu i dynamiczne struktury danych.

1. (11 punktów) Napisz program, który przekształci wyrażenie infiksowe z nawiasami do postfiksowej postaci Łukasiewicza (odwrotna notacja polska). Wyrażenie infiksowe ma być podane jako argument wywołania programu. Wyrażenie infiksowe nie może zawierać w środku żadnej spacji. Postfiksowa postać wyrażenia powinna być przechowywana w kolejce. Program powinien wypisać podane wyrażenie infiksowe w postaci postfiksowej (poszczególne elementy tego wyrażenia mają być pooddzielane pojedynczymi spacjami), a potem obliczyć i wypisać wartość tego wyrażenia.
   Wyrażenie infiksowe jest wyrażeniem arytmetycznym w naturalnej (dla przeciętnego człowieka) postaci. Składa się ono z liczb rzeczywistych połączonych operatorami i pogrupowanych przy pomocy nawiasów. Nawiasy służą do zmiany kolejności obliczeń wynikającej z priorytetów użytych operatorów. Dla uproszczenia przyjmiemy, że wszystkie operatory są binarne (nie ma unarnego operatora minus, zmieniającego znak wyrażenia na przeciwny): mamy więc dodawanie (symbol +), odejmowanie (symbol -), mnożenie (symbol *) i dzielenie (symbol /). Priorytety dodawania i odejmowania są niższe niż mnożenia i dzielenia (najpierw mnożymy i dzielimy, a potem dodajemy i odejmujemy); ponadto dodawanie ma taki sam priorytet jak odejmowanie, a mnożenie taki sam jak dzielenie (ciąg obliczeń o takim samym priorytecie wykonujemy od strony lewej do prawej). Co do liczb, to są dopuszczalne tylko nieujemne liczby rzeczywiste (aby dostać wartość o przeciwnym znaku należy ją odjąć od zera), w których ewentualna część ułamkowa jest zapisywana po kropce dziesiętnej.
   Wyrażenie postfiksowe jest sposobem zapisu wyrażeń arytmetycznych, w którym symbol operatora operacji umieszczony jest po operandach, a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym. Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.
   Wskazówka: Do przekształcenia wyrażenia infiksowego na postfiksowe (odwrotna notacja polska) użyj dynamicznych struktur danych (stosy i kolejki) zrealizowanych na listach.
   Wskazówka: Algorytm translacji wyrażenia arytmetycznego do postaci ONP jest następujący:
   1. Przygotuj struktury danych: kolejkę, w której umieść kolejne symbole wyrażenia infiksowego (wejście); pomocniczy stos, początkowo pusty; pustą kolejkę na wyrażenie w postaci postfiksowej (wyjście).
   2. pobierz symbol z kolejki wejściowej;
   3. jeśli jest to operand (liczba), to dopisz go do kolejki wyjściowej;
   4. jeśli jest to nawias otwierający (, to przepisz go na stos;
   5. jeśli jest to nawias zamykający), to przepisz ze stosu do kolejki wyjściowej wszystkie symbole do nawiasu otwierającego i usuń ten nawias ze stosu (bez przepisywania go do kolejki wyjściowej;
   6. jeśli jest to operator działania algebraicznego, to przepisz ze stosu do kolejki wyjściowej wszystkie operatory, które mają wyższy lub równy priorytet (jeśli priorytet operatora na wierzchu stosu jest mniejszy lub na stosie jest symbol nawiasu otwierającego lub stos jest pusty, to zakończ przepisywanie);
   7. jeśli w kolejce wejściowej są jeszcze jakieś symbole, to przejdź do punktu 2;
   8. przepisz wszystkie operatory ze stosu do kolejki wyjściowej.
   
   Uwaga: Twój program powinien wyłapać ewentualne błędy w podanym do programu wyrażeniu.
   Uwaga: Opis algorytmu konwersji wyrażenia z postaci konwencjonalnej do postaci ONP oraz algorytm obliczenia wartości wyrażenia zapisanego w postaci ONP można znaleźć na stronie Wikipedii.