Zadanie 1

Szesnastkowy kalkulator RPN

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.

Składnia wyrażeń

wyrażenie ::=   liczba
              | wyrażenie wyrażenie operator
operator  ::= + | - | *

liczba jest dowolną nieujemną liczbą całkowitą zapisaną w systemie szesnastkowym. 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).

Przykłady poprawnych wyrażeń

10 20 30 + -
Wynik: -40 
2 2 2 2***
Wynik: 10 
2 3 *
F 5 -
+
Wynik: 10

Przykłady niepoprawnych wyrażeń

1 2 3 4

+ - *

1 2 + asdf?

Wartość wyrażeń

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.

Błędy

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 sygnały takie, jak SIGSEGV (naruszenie ochrony pamięci), SIGFPE (błąd obliczeń, zazwyczaj dzielenie przez zero) i inne oznaczające błędy wykonania. 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 będzie obliczał wartości wszystkich poprawnych wyrażeń nie dłuższych niż 65536 bajtów.

Efektywność

Nie trzeba walczyć o każdą mikrosekundę lub bit pamięci, ale jeśli ktoś będzie mnożył a przez b wykonując wielokrotne dodawanie a do siebie, to nie otrzyma maksymalnej oceny.

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.

Całe obliczenie program powinien wykonywać w czasie co najwyżej liniowym względem długości wejścia.

Forma

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.

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.

Poprawne rozwiązanie da się zapisać w mniej niż 300 wierszach.

Sposób oddania

Program należy przysłać na adres tmal@mimuw.edu.pl do wtorku 5 kwietnia 2005 do godziny 12:00. Nadesłanie w późniejszym terminie może spowodować obniżenie oceny, a nawet nieprzyjęcie rozwiązania jeśli opóźnienie przekroczy 2 tygodnie.