Mûveletek veremmel. Rekurzív algoritmusok, kifejezések kiértékelése.

Mûveletek veremmel. Rekurzív algoritmusok, kifejezések kiértékelése.

Vermek felhasználása

1., Rekurzív algoritmusok

Veremben tároljuk a

- paramétereket,

- a lokális változókat,

- a visszatérési címeket

Példa rekurzív algoritmus: Hanoi tornyai

Kifejezések kiértékelése: Lengyel-formula

A+B, ( A + B ) * C infix jelölés

+AB,*+ABC prefix jelölés

AB+, AB+C* postfix jelölés

Postfix kifejezések kiértékelése veremmel:

1., Operandus Verem

operátor:

- verem két felsõ elemének (pl.: A,B) kiemelése

- B A elvégzése

- eredmény verem

Példa ( 5*(6+2)-12/4 )

1., 2., 3., 4., 5.,

2

6 6 8

5 5 5 5 40

6., 7., 8., 9.,

4

12 12 3

40 40 40 37

Infix kifejezések átalakítása postfix kifejezéssé veremmel

1., Operandus P (postfix kif.)

verem

operátor:

- verembõl P-be helyezi sorban az összes olyan operátort, melynek precedenciája ³ mint

- verem

- verembõl P-be helyezi -t, míg ( nem jön

- ( eltávolítása

5., Végén  maradékot verembõl P

Példa ( A + B ) * C - D/E

+ +

C ( ( ( *

A A AB AB+ AB+

/ /

* - - - -

AB+C AB+C* AB+C*D AB+C*D AB+C*DE AB+C*DE/-

Példa Sor (FIFO)

V =

F =

Szintaxis:        new: sor

add: sor x elem sor

front: sor elem

remove: sor sor

Konstrukciós: new, add

Szelekciós:     front, remove