Zadanie polega na napisaniu programu, który wczyta ze standardowego wejścia jedno wyrażenie zapisane w odwrotnej notacji polskiej, obliczy jego wartość i wypisze wynik na standardowe wyjście. Wynik powinien zostać wypisany w postaci szesnastkowej. W przypadku pomyślnego wykonania programu, powinien on się zakończyć z kodem wyjścia 0. W przypadku błędu w obliczeniach program powinien wypisać słowo BLAD i zakończyć się z kodem wyjścia 1.
wyrażenie ::= liczba
| wyrażenie wyrażenie operator
operator ::= + | - | *
liczba jest dowolną nieujemną liczbą całkowitą zapisaną w systemie szesnastkowym przy użyciu jako cyfr znaków od 0 do 9 i od A do F. Liczby są oddzielane operatorami lub białymi znakami. Białe znaki pomiędzy operatorami oraz między liczbami i operatorami są pomijane. Jako białe znaki traktujemy znaki o kodach 9 (tabulacja), 10 (koniec wiersza) i 32 (spacja). Jedno wyrażenie może więc być zapisane w kilku wierszach. Należy wczytywać wyrażenie do momentu napotkania końca standardowego wejścia, to znaczy do momentu, gdy funkcja read zwróci 0. Wpisując wyrażenie z klawiatury można zasygnalizować koniec wciskając Ctrl-D.
10 20 30 + -Wynik: -40
2 2 2 2***Wynik: 10
2 3 * F 5 - +Wynik: 10
1 2 3 4
+ - *
1 2 + asdf?
Wartością wyrażenia wyrażenie1 wyrażenie2 operator jest wartość wyrażenia wyrażenie1 operator wyrażenie2 w zwykłej infiksowej notacji.
Program w podstawowej wersji powinien dokonywać obliczeń na 32-bitowych liczbach ze znakiem. Jeśli w trakcie obliczeń zostanie przekroczony zakres tych liczb, należy zgłosić błąd. Dotyczy to również sytuacji, gdy jedna z liczb podanych na wejściu jest zbyt duża (np. FFFFFFFF).
Wartość wyrażenia należy wypisać bez nieznaczących zer z przodu (czyli np. -123 zamiast -00123).
Nie należy wypisywać nic innego (np. zachęty do wprowadzenia wyrażenia), ponieważ utrudni to automatyczne testowanie rozwiązań.
Program powinien wykrywać następujące błędy:
W przypadku wystąpienia błędu, program powinien wypisać na standardowe wyjście słowo BLAD i wyjść z kodem wyjścia równym 1.
Program nie może być przerywany przez błędy takie, jak chociażby naruszenie ochrony pamięci. Program powinien zachowywać się poprawnie (obliczać wartość wyrażenia lub wypisywać komunikat o błędzie) dla każdego, nawet najbardziej złośliwego wejścia. Można przyjąć jakieś ograniczenia na złożoność obliczanego wyrażenia i sygnalizować błąd przy obliczaniu zbyt skompilkowanych wyrażeń. Wystarczy jeśli program nie będzie uznawał za zbyt złożone żadnego poprawnego wyrażenia nie dłuższego niż 65536 bajtów.
Nie trzeba walczyć o każdą mikrosekundę lub bit pamięci, ale jeśli
ktoś będzie mnożył
Należy unikać wczytywania każdego znaku z wejścia osobnym wywołaniem systemowym. W czasie jednego wywołania systemowego należy wczytywać większą liczbę znaków.
W trakcie obliczania wyrażenia program powinien wykonywać co najwyżej liniową względem długości wejścia liczbę operacji arytmetycznych.
BEEF !48879 %1011111011101111lub:
-CAFE -!51966 -%1100101011111110
Program powinien zostać w całości napisany w asemblerze NASM lub GNU Assembler. Nie może korzystać z żadnych bibliotek. Wystarczy przysłać jeden plik źródłowy, który można zasemblować do pliku object, a następnie ten plik object zlinkować otrzymując plik wykonywalny. Jeśli ktoś życzy sobie zapisać swoje rozwiązanie w kilku plikach źródłowych, powinien dołączyć do niego kompilujący je plik Makefile.
Ewentualne uwagi dla sprawdzającego można umieścić w kometarzu na początku programu. Nie ma zbyt wysokich wymagań co do stylu, ale warto stosować znaczące nazwy symboli i umieścić w programie trochę komentarzy, aby sprawdzający nie miał problemów ze zrozumieniem kodu.
Program należy przysłać na adres tmal@mimuw.edu.pl do (uwaga, zaszły zmiany) poniedziałku 24 kwietnia 2006 do godziny 12:00 w południe. W temacie listu proszę umieścić ciąg [rozw-arch1]. Nadesłanie w późniejszym terminie może spowodować obniżenie oceny.
Napisałem powyżej, że program powinien wykonywać co najwyżej liniową liczbę operacji arytmetycznych względem długości wejścia. W rozszerzonej wersji jako jedną operację arytmetyczną traktuję jedną operację na dużych liczbach, co oczywiście może wymagać wykonania wielu rozkazów procesora. Mnożenie w czasie kwadratowym ze względu na sumę logarytmów mnożonych liczb w zupełności wystarczy.
Zgłaszanie przekroczenia zakresu nie jest obowiązkowe pod warunkiem, że program potrafi podać poprawny wynik. Dopuszczalne jest zasygnalizowanie przekroczenia zakresu, gdy wynik jednej z operacji nie mieści się w zakresie, który ma obsłgiwać kalkulator. Niedopuszczalne jest natomiast podanie niepoprawnego wyniku, nawet jeśli, przykładowo, przystaje on modulo 232 do poprawnego.
Przygotowałem prosty skrypt testujący kalkulator. Ma on na celu sprawdzenie, czy kalkulator akceptuje wyrażenia w odpowiedniej składni i czy wypisuje wyniki w odpowiednim formacie. Jak można się przekonać, testy nie są zbyt złożone obliczeniowo, więc poprawne ich wykonanie nie oznacza wcale, że kalkulator działa poprawnie. Skrypt uruchamia się wydając polecenie:
./test_kalk program katalog_z_testami
Katalog testy zawiera testy z odpowiedziami oczekiwanymi od programu w podstawowej wersji, zaś katalog testy_decbin zawiera testy z odpowiedziami w trzech systemach pozycyjnych.