I. Adatszerkezetek: a verem

Elsõ nekifutás

Az egyes adatszerkezet-típusokat jellemzi, hogy miképpen tárolhatunk bennük adatot, és azt hogyan kaphatjuk vissza (ezek a mûveletek az adatszerkezettel).

Példák: a tömböt jellemzi, hogy minden elemét meg lehet címezni, ezt ki lehet olvasni, és módosítani lehet. A szekvenciális (soros) file-t jellemzi, hogy:

• az elejére lehet állni
• ki lehet olvasni a soron következõ elemét
• a végére lehet írni egy új elemet

tehát pl. az utolsó elemét csak úgy lehet kiolvasni, hogy az elejétõl kezdve sorban végigolvassuk. Az utolsó elemet úgy lehet kitörölni, hogy az elsõ elemtõl kezdve az utolsó elõttiig végigolvassuk, és az elemeket egy kezdetben üres másik szekvenciális file végére írjuk. (Ilyen a Pascal TEXT típusa.)

A verem jellemzõi:

• be lehet tenni egy elemet a tetejére
• ki lehet venni a legutóbb berakott (legfelsõ) elemet

így tehát ha egy üres verembe berakjuk az 1, 6, 3 számokat ilyen sorrendben, akkor elõször a 3, azután a 6, végül az 1 vehetõ ki belõle. Ha még egy elemet ki akarunk venni belõle, a verem-eljárás hibát jelez.

A verem jellegzetes eljárásai:

• Procedure INICI {beállítja a verem kezdõértékét}
• Procedure BETESZ (a:típus) {a paraméter értékét beteszi a verem tetejére}
• Procedure KIVESZ (var a:típus) {a legfelsõ elem a paraméterként átadott változóba kerül}
• Function ÜRES:boolean {igaz eredményt ad, ha a verem üres}

Programrészlet:

Var r:integer; {amennyiben a verem elemeinek típusa integer}
BEGIN
   Inici;
   Betesz(5);
   Betesz(7);
   While not Ures do begin
      Kivesz(r);
      Writeln(r);
   end;
END.

1. feladat: írd meg a verem eljárásait! (mondjuk, real típusú veremre. Célszerû a verem alaptípusát TYPE utasítással külön elnevezni, hogy könnyen lehessen változtatni rajta). Segítség: a vermet egy tömbben tudod tárolni. Szükséged van egy MUT változóra, amely a legutóbb berakott elem helyét mutatja a tömbben. Elõször készíts algoritmust, csak azután fogj hozzá az íráshoz!

Mire jó a verem? Eljáráshívásoknál a visszatérési címet veremben kell tárolni, hogy ha egy eljárás lefut, a vezérlés a legutóbb bekerült címre, vagyis az illetõ eljárást indító eljáráshoz térjen vissza. A verem másik hasznát a következõ feladat világítja meg.

2. feladat: adott egy zárójeles kifejezés, melyben háromféle zárójel-párt használhatunk: ( ), [ ], { }. Helyes kifejezésnek számítanak:
   (xyz(ppp[5]xxx)) és (({i}{}[[(i)]])) és [a[a(a(a(x)b)b)b]b]
Helytelen viszont:
   [3+(2+2]) és [[x] és [y]]
tehát, ha (mondjuk balról jobbra haladva) egy záró zárójelet találunk, akkor a legutóbbi le nem zárt zárójel annak nyitó párja kell, hogy legyen. Továbbá, a nyitó és záró zárójelek száma meg kell, hogy egyezzék.
Készíts vázlatos algoritmust, mely elemez egy beadott zárójeles kifejezést, tehát megadja, hogy helyes-e vagy sem! Segítség: kétféle hiba fordulhat elõ. a) záró zárójelet találtunk, melynek nincs nyitó párja, b) a kifejezés végére értünk, és még maradt le nem zárt nyitó zárójel.

Második nekifutás

A verem-gép: olyan számológép, amelyben van egy verem. A mûveletek:

• szám beírása: a számot a verembe teszi
• +: a verembõl kivesz két számot, összeadja õket, és az eredményt beteszi a verembe
• *: ugyanez szorzásra

A verem-mûveleteket úgy szokás jelölni, hogy megadjuk a verem tetejének (hogy alul mi van, nem lényeges) kezdõ- és végállapotát. Pl.: + (a b ___ a+b), vagyis kezdetben volt a verem tetején két szám (és b volt fölül, tehát a, b sorrendben raktuk be a számokat), a végén pedig az összegük került oda. További mûveletek (figyelj a sorrendre, nem mindegy, hogy a-b vagy b-a!):

• - (a b ___ a-b)
• / (a b ___ a/b)

És természetesen szükség van egy olyan mûveletre, amely kiveszi a verem tetején lévõ számot, és kiírja. Ez a . (pont).

• . (a ___ )

1. feladat: mit ír ki a verem-gép?
   1 2 3 + + .
   2 4 6 + / .
   1 3 + 5 3 + / .

Az utolsó példából látszik, hogy mi a verem-gép fõ elõnye: zárójel nélkül lehet vele számolni. Sok programnyelv kifejezés-kiértékelõje mûködik úgy, hogy a zárójeles kifejezést a fentihez hasonló módon átalakítja. A következõ mûveletet: ((a+b)-c)/2+1 verem-géppel így kellene elvégeztetni:
   a b + c - 2 / 1 + .
Persze így is lehetett volna: 1 a b + c - 2 / + .

A mûveletek sorrendjének ilyen felírását (érték érték mûvelet) postfix vagy lengyel formának (Polish notation, PN) nevezzük. Ez nem tartalmaz zárójelet.

2. feladat: végezd el verem-géppel a következõ mûveleteket!
   ((1+2)-7)/10
   10/(1+2)
   (3+2)/(7-1)
   (1-2/3)/(2-3/4)

Hogyan lehetne más mûveleteket definiálni? Például a reciprokot: (a ___ 1/a)? Megoldani egyszerû, mert 1 a / - rel pontosan ez történik. De mi van, ha az a már ott van a verem tetején? Ezért hasznos a következõ verem-mûvelet:

• SWAP (a b ___ b a)

Ekkor a reciprok mûvelete a verem tetején lévõ számmal így fog kinézni:
   1 SWAP /

3. feladat: a reciprokhoz hasonlóan készítsd el az ellentett mûveletét
   (a ___ -a)!

A SWAP segítségével az ((a+b)-c)/2+1 másképen is felírható:
   1 2 c b a + SWAP - SWAP / + .
Ellenõrzésképp írd fel minden egyes mûvelet után a verem állapotát! Ebben a módszerben az az érdekes, hogy elõször bepakoljuk az összes számot a verembe, és utána már csak mûveleteket végzünk.

4. feladat: végezd el ilyen módon is a 2. feladat mûveleteit! (tehát elõször bepakolsz mindent a verembe, és utána már csak mûveleteket végzel). Persze nem mindegy, hogy a számokat milyen sorrendben teszed a verembe. Az utolsó feladat valószínûleg gondot fog okozni.

A SWAP mûvelet továbbfejlesztése a

• ROT (a b c ___ b c a)

amely a 3 legfelsõ elem sorrendjét változtatja meg ciklikus permutációval. Próbáld meg ennek segítségével megoldani az utolsó feladatot!

Még egy fontos mûvelet:

• DUP (a ___ a a)

Ezzel megoldható a verem tetején lévõ szám négyzetre emelése: DUP *. Hasonlóképpen a köbre emelés: DUP DUP * *.

5. feladat: készíts veremgép-szimulátort! Vagyis a programnak a következõ dolgokat adhatod be: szám, + - * / SWAP DUP ROT . , egy sorba csak egy dolgot írva. A verem legyen Real típusú (lehessen törtszámot is beadni). Mivel a programod mindenképpen sztringet fog beolvasni (hiszen nem lehet elõre tudni, hogy 154-et vagy DUP-ot ír be a felhasználó), ismerned kell a Pascal VAL eljárását, mellyel szövegbõl számot tudsz készíteni (miután eldöntötted a beadott sztringrõl, hogy se nem SWAP, se nem DUP, se nem ROT, se nem pont). A hibaellenõrzéssel ne foglalkozz, tehát ha a felhasználó p9p9-et gépel be, nem baj, ha a VAL nullának veszi.

Gyakori probléma, hogy a verem tetején rossz sorrendben vannak a számok, és valamely alul lévõ számra van szükségünk (ld. a 4. feladatot). Emiatt a veremgépek gyakran rendelkeznek egy másik veremmel is, amelybe az eredeti verembõl be át lehet pakolni számokat, és viszont. Így mûködhet a PUSH és POP utasítás:

• PUSH (a ___ ) (a legfelsõ értéket átrakta a kiegészítõ verembe)
• POP ( ___ a) (a kiegészítõ verem legfelsõ elemét átrakta a fõ verembe)

Így pl. a felülrõl negyedik elem kiírása: PUSH PUSH PUSH . POP POP POP

6. feladat: oldd meg a 2. feladatot a PUSH és POP utasítások segítségével, mégpedig úgy, hogy a számokat elõször a feladatban szereplõ sorrendben bepakolod a verembe, és utána már csak mûveleteket végezhetsz!

7. feladat: valósítsd meg a ROT utasítást PUSH, POP, SWAP utasításokkal!

*** Matematikai kiegészítés (permutációk)