ALG8

148 Rozdział 5. Struktury danych

148 Rozdział 5. Struktury danych

„ nadchodzące" elementy:

I    2

+

7 etc.

Etapy tworzenia tlrzeuti hinarnof>o (zawartość stosu):

Rys. 5 - 24.

Tworzenie drzewa binarnego wyrażenia arytmetycznego.

Typowe wyrażenie arytmetyczne, zapisane w powszechnie używanej postaci (zwanej po polsku wrostkową), da się również przedstawić w tzw. Odwrotnej Notacji Polskiej (ONP. postfiksowej). Zamiast pisać aopb używamy formy: a b op . Mówiąc krótko: operator występuje po swoich argumentach. Operacja arytmetyczna jest łatwa do odtworzenia w postaci klasycznej, jeśli wiemy, ile operandów wymaga dany operator.

Analiza wyrażenia beznawiasowego odbywa się w następujący sposób:

•    Czytamy argumenty znak po znaku, odkładając jc na stos.

•    W momencie pojawienia się jakiegoś operatora ze stosu zdejmowana jest odpowiednia dlań liczba argumentów - wynik operacji kładziony jest na stos jako kolejny argument.

Na rysunku 5-24 możemy zaobserwować opisany wyżej proces w bardziej poglądowej formie niż powyższy suchy opis. Pierwsze dwa argumenty, 1 i 2, jako nie będące operatorami, są odkładane na stos (w programie odpowiadać to będzie stworzeniu dwóch komórek pamięci, których pola wskaźnikowe lewy i prawy są zainicjowane wartościami NULL). Trzecim elementem, który przybywa z „zewnątrz”, jest operator t. Tworzona jest nowa komórka pamięci, jednocześnie sam fakt nadejścia operatora prowokuje zdjęcie ze stosu dwóch argumentów, którymi są komórki zawierające liczby / i 2. Te komórki są „doczepiane” do pól wskaźnikowych komórki zawierającej operator +. Kolejnym nadchodzącym elementem jest znowu liczba (7) —jest ona odkładana na stos i proces może być kontynuowany dalej...

W opisany wyżej sposób pracują kompilatory w momencie obliczania wyrażeń za pośrednictwem stosu. Jedyną różnicą jest to, że nie są odkładane na stos kolejne poddrzewa. ale już obliczone fragmenty dowolnie w zasadzie skomplikowanych wyrażeń arytmetycznych. Czytelnik zgodzi się chyba ze