Verem A számítástechnikában a verem (stack) egy speciális adatszerkezet, amiben csak kétféle művelet van. A berak (push) egy elemet a verembe rak, a kivesz (pop) egy elemet elvesz a verem tetejéről. Mindig az utoljára betett elem vehető el, a verem többi része nem elérhető. Ezért is hívják LIFO adatszerkezetnek (Last In First Out).
A kezeléséhez szükség van egy verem mutatóra. A veremmutató mutatja a veremben az első szabad helyet. Kezdetben 0. Ha egy elem a verembe kerül (push), akkor a verem mutató értéke növekszik. Ha egy elem kijön (pop), a verem mutató értéke csökken.
7
6 5 4 3 2 1
356
0
123
Verem mutató 2 0 1
Verem A megvalósítást szimuláljuk tömb segítségével. Ebben az esetben csak egyforma elemek kerülhetnek a verembe. BERAK(mit) Ha vmut=vmeret akkor nincs hely!!! egyébként verem[vmut]=mit : vmut=vmut+1; feltétel vége
KIVESZ(mit) Ha vmut=0 akkor üres a verem egyébként vmut=vmut-1 : mit=verem[vmut] feltétel vége
Verem Készíts Programot, ami beolvas egy c++ programot és ellenőrzi, hogy a zárójelezés rendben van-e… Döntsd el egy stringben tárolt számról, hogy palindrom-e. (A feladatot veremmel kell megoldani.) Olvass be egy számot és egy számrendszert, váltsd át a számot az adott számrendszerbe és írd ki az eredményt helyiérték helyesen. (Használj vermet a megoldáshoz!)
Verem Készítsen játékprogramot a veremkezelés szemléltetésére. A játékszabályok: Legyen egy 100 elemet befogadni képes verem. Induláskor töltsünk be 20 elemet. Egy-egy elem egy 1 és 10 közötti véletlen szám és a hozzá tartozó súly, amely szintén egy véletlen szám 1 és 5 között. A játék: tippelni kell a verem tetején lévő számra. Ha eltaláltuk, akkor annyi véletlen számmal tölti tovább a program a vermet, amennyi a kitalált szám és a hozzá tartozó súly szorzata. (A játékos nem ismeri a súlyozó tényezőket, sem a számokat) Ha nem találtuk ki a számot, akkor a verem tetején lévő szám törlődik, s az alatta lévő (következő) számra lehet tippelni. A játékos nyert, ha a verem megtelt. A nyeremény a veremben letárolt véletlen számok súlyokkal szorzott összege. A játékos vesztett, ha a verem kiürült. A verem tárolására egy 100 elemű egydimenziós tömböt fogunk használni. A tömb elemei rekordok.
Verem Lengyel formula A szokásos matematikai formulákat nagyon nehéz kiértékelni. Pl. a*(b+c)/d^(x+y)*e A kifejezés azonban átírható úgy, hogy zárójelre nincs szükség és a kiértékelés is könnyű. A kapott alakot fordított lengyel formulának hívják, vagy röviden lengyel formulának. Nézzünk néhány példát: Szokásos
Lengyel alak
a+b
ab+
a+b*c
abc*+
a*b^c+d
abc^*d+
Ha operandust találunk akkor azt másoljuk a kimenetre. Ha műveletet, akkor a verem tetején levőt másoljuk ha nagyobb a prioritása, ha kisebb egyenlő akkor ez is megy a verembe.
Verem Kicsit bonyolultabb a helyzet, ha a zárójelezést is kezelni akarjuk. Ha nyitót találunk, akkor az megy a verembe. Az operandusok és műveletek kezelése nem változik. Ha zárót találunk, akkor a veremből sorban a kimenetre másoljuk a jeleket a nyitó zárójelig. (Ez annak köszönhető, hogy a zárójelen belüli kifejezés egy önálló alak, lehetne rekurzív a megoldás… ) Szokásos
Lengyel alak
a*(b+c)
abc+*
(a+b)*c
ab+c*
a*b^(c+d)*e
abcd+^*e*
A műveletek prioritása "("=0; + - =1; */ = 2; ^=3. Az üres verem 0;
Verem A műveletek prioritása "("=0; + - =1; */ = 2; ^=3. Az üres verem 0; Szokásos
Lengyel alak
a * b ^ ( c + d * e ) * f Verem
Verem CIKLUS AMÍG van elem a forrásban CVÉGE Következő elem beolvasása a forrásból X-be CIKLUS AMÍG verem nem üres HA X egy operandus KIVESZ VEREMBŐL Y-ba EREDMENY := EREDMENY + X EREDMENY := EREDMENY + Y HA X egy nyitó zárójel CVÉGE VEREMBE ( X ) HA X egy záró zárójel CIKLUS AMÍG a verem teteje nem nyitó zárójel KIVESZ VEREMBŐL Y-ba EREDMENY := EREDMENY + Y CVEGE KIVESZ VEREMBŐL Y-ba (nyitó zárójel) HA X egy műveleti jel CIKLUS AMÍG a verem tetején levő elem prioritása >= X prioritása KIVESZ VEREMBŐL Y-ba EREDMENY := EREDMENY + Y CVÉGE VEREMBE X
Verem A kiértékelés már sokkal egyszerűbb. CIKLUS AMÍG van elem a forrásban Következő elem beolvasása a forrásból X-be HA X egy operandus verembe(X értéke) HA X egy műveleti jel veremből(E2) : veremből(E1) : verembe (E1 művelet E2) CVÉGE veremből(eredmény)
