ALG9

5.6. Drzewa i ich reprezentacje 149

stwierdzeniem, że z punktu widzenia komputera ON P jest istotnie bardzo wygodna w użyciu^-.

Przypatrzmy się już konkretnym instrukcjom w C++, które zajmują się inicjacją drzewa binarnego.

typedef struct

(

double val; char cp;

}VAL;

void main()

{

STOS<wyrazenie*> s;

VAL t[9]- (    (2,'0'),(3,'0'},(0,' + '), (7, '0'),    (9,'0•>,    (0,'*'),

•0,’+’),(12.5,'0'),(0,'*')); wyrażenie ^xx; forfint i-0;i<9;i++) i

x=new wyrażenie;

if ( (t [i] .op— •**) I (t [i] .cp==' + ') | |

(11i].op=='-')|i <t[i].cp=='/')I.(tli].op==':')) x->op =t[i]. op;

else

(x->val=t[i].val;x->op='0';) x->lewy -NULL; x->prawy=NULL;

if ( (t(i] .op==^,x'J I (t [ i ] . op= *-+•*) I (t [ i ] . op==' - ’} I I (t[i].op=='/')[|(Łli].op«“':¹))

wyrażenie *ll,*pl; s.pop(11); s.pop(pl) ; x->lewy -11; x->prawy=pl;

)

s.push(x);

)

pisz_infix(x); cout << "=" « oblicz(x) « endl; pisz_prefix(x);cout « ”=" « oblicz(x) « endl;

>

W powyższym listingu tablica / zawiera poprawną sekwencję danych, tzn. taką, która istotnie stworzy drzewo binarne mające sens. Warto odrobinę poeks-perymentować z zawartością tablicy, aby zobaczyć, jak algorytm „zareaguje” na błędny ciąg danych. Można się spodziewać, że w przypadku np. braku drugiego operanda lub operatora rezultaty otrzymane będą również błędne -jest to prawda, ale najlepiej jest przekonać się o tym „na własnej skórze”.

² Notabene wbrew pozorom ONP jest dość wszechstronnie stosowana: patrz kalkulatory firmy Hewlett Packard, język Forth, język opisu stron drukarek laserowych Postscript... W pewnych „kręgach” jest to zatem dość znana notacja.