Die Auswertung eines arithmetischen Ausdruckes (2+(3*(7-4)-2(6-4))), die Organisation von mehreren Prozessen mit Hilfe eines Prozessors, die Speicherung von Rücksprungadressen bei verschachtelten Prozeduraufrufen haben alle eins gemeinsam: Sie werden mit Hilfe sog. Stacks realisiert:
Ein Stack ist ein Speichermedium, das all diese komplexen Abläufe mit Hilfe von nur zwei Prozeduren organisieren kann:
procedure push : Mit dieser Methode wird ein anliegendes Datum oben auf den Stack gelegt.
procedure pop : Mit dieser Methode wird das oberste Datum aus dem Stack entfernt.
Man bezeichnet Stacks wegen dieser funktionsweise auch als LIFO- (oder auch FILO-) Speicher. Für ein sinnvolle Programmierung sind noch zwei weitere Funktionen nötig:
function top : Hat als Rückgabewert den Wert des obersten Stackeintrages.
function empty: signalisiert, wenn keine Daten mehr auf dem Stack liegen.
Die Sicherung des Prozessorzustandes bei Mehrfachprozessen ist ein typisches Beispiel für die Arbeitsweise eines Stacks. Der Zustand eines Prozessors an einem bestimmten Punkt eines Prozesses wird durch den Inhalt der sog. Prozessorregister beschrieben. Das sind hardwaremäßig organisierte Speicherstellen im Prozessor selber, die schnell beschrieben und ausgelesen werden können. Auch der Stack befindet sich im Prozessor selber und die zugehörigen (Assembler-) Befehle push und pop sind mittels logischer Schaltungen realisiert, so dass der Prozessorzustand sehr schnell gerettet und wieder hergestellt werden kann. Die Befehle für eine Interruptbehandlung beginnen darum typischerweise mit Befehlen wie push ax, push bx, push cx,.. und enden mit den komplementären Befehlen ...pop cx, pop bx, pop ax.
Wir wollen die Stackklasse TStack als Nachkommen der Klasse TList organisieren. Da wir die Typendeklaration in einer getrennten Unit vornehmen wollen, ist es im Prinzip gleichgültig, wie die einzelnen Methoden implementiert werden. Man nennt solche Datentypen oft auch abstrakte Datentypen (ADT) wie sie nur durch ihre Funktionsaufrufe und nicht durch die Implementation der Methode definiert sind.
Aufgaben:
1. Schreibe eine Unit stack.pas (Lösung stack.pas), die die Deklaration der Klasse Tstack = class(TList) als Nachfolger der TList-Klasse enthält. Wenn Deine Unit fehlerfrei programmiert und kompiliert ist, müsste sich reibungslos mit dem Programm stackdemo zusammenarbeiten Das ist genau das Spielziel der Definition eines abstrakten Datentyps, dass einzig und allein die Methodenaufrufe veröffentlicht werden, die eigentliche Implementation Geheimnis des Programmierers bleibt.
2. Ändere das Programm stackdemo so ab, dass ein anderer Datentyp (bzw. dessen Adresse) (z.B. ein String, ein Datensatz) im Stack gespeichert wird. Überlege, an welcher Stelle typisierte in untypisierte Zeiger umgewandelt werden und umgekehrt.
3. Als Ziel soll mit Hilfe eines Stacks die Auswertung eines arithmetischen Term der Form
at := '((2+3)+(3*(6-2))'
programmiert werden. Dazu muss man Zeichenketten zerlegen können. Das geschieht am einfachsten mit Hilfe folgender Anweisungen: at[1] ist das erste Zeichen in der Zeichenkette at. Mit delete(at,1,1) löscht man das erste Zeichen der Zeichenkette at, so dass man mit at[1] auf das zweite Zeichen zugreifen kann usw. Ändere das Programm stackdemo so ab, dass man in einer Combobox mehrere Zeichenketten vorgibt, die dann Zeichenweise in einen Stack geschoben werden. Überprüfe so z.B. ob ein Term gleichviel öffnende und schließende Klammern enthält.
(Lösung: arithm.pas)
© Dietrich Praclik