Algorithmen und Datenstrukturen in Pascal Teil 1: Stacks

Einleitung

Mit einem Artikel über Stacks, möchte ich heute eine neue Artikelserie beginnen. Im Laufe dieser Serie werde ich Sie, liebe Leser und ATARI- Freunde, nach und nach, mit weiteren Begriffen der Programmierung, wie Queues, Listen, Bäume und einigen Sortierverfahren, bekanntmachen.

Als vermittelnde Computersprache habe ich PASCAL gewählt, weil, wie ich meine, PASCALs klare, programmtechnische Formulierungen, bei diesen doch recht abstrakten Problemen, den Kürzeln der Modesprache C eindeutig vorzuziehen sind. Dies soll jedoch die Freunde einer anderen Programmiersprache nicht abschrecken, denn prinzipiell ist der behandelte Stoff leicht auf jede Sprache umzusetzen, die des PRODEDURE/FUNCTIONS- Konzeptes mächtig ist, sowie über eine dynamische Speicherverwaltung verfügt (PASCAL, MODULA II, C, ...). Als weitere technische Anmerkung sei mir gestattet, daß ich den PASCALplus- Compiler (CCD) zur Übersetzung der Programmbeispiele benutzt habe, daß dies aber keine wesentliche Rolle spielt, da ich gedenke, im Laufe dieser Serie nur Standard PASCAL, gemäß Niklaus Wirth, zu benutzen. (An den wenigen Stellen, wo ich, der Einfachheit halber, vom Standard abweiche, werde ich dieses erwähnen.)

Doch kommen wir nun zur Sache.

Was ist überhaupt ein Stack?

Wie die deutsche Übersetzung des Begriffes 'Stack' schon sagt, handelt es sich dabei, im übertragenen Sinne, um einen Stapel und zwar um einen Stapel von Informationen. Um einen solchen Stapel zu verwalten, ist es notwendig, Operationen zum Aufbauen, Erweitern und Abbauen, sowie der Kontrolle von Stacks zu besitzen. Hierzu haben sich in der kurzen Tradition der Computergeschichte die folgenden Begriffe eingebürgert:

Um die Wirkungsweise dieser Operationen zu verdeutlichen, möchte ich Sie bitten, die Abb.1a zu betrachten.

Hier wird die Arbeitsweise der PUSH- und der POP- Operation gezeigt. Der in den Stacks 'oben' abgebildete Bereich zeigt den Stackpointer, also den Zeiger, welcher auf das zuletzt 'abgestapelte' Element weist. Durch die PUSH- Operation (links) wird ein Element dem Stack hinzugefügt und der Stackpointer entsprechend umgesetzt. Die POP- Operation (rechts) entfernt das oberste Element aus dem Stack und setzt den Stackpointer auf das darunter liegende Element. Diese Art der Informationsspeicherung nennt man LIFO, für Last-in-first-out, was ja auch ziemlich deutlich die Arbeitsweise umschreibt. Mit der in der Abbildung nicht erwähnten TOP- Operation, erhält man die Informationen des obersten Stackelements (auf das der Stackpointer weißt), ohne dieses jedoch vom Stack abzutrennen. Ein weiterer Befehl ist die Stackkontrollfunktion IS_EMPTY. Da es nur mit den drei Operationen PUSH, POP und TOP, möglich wäre, nicht vorhandene Stackelemente zu löschen, dient sie dazu, vor einem Zugriff mit POP, oder TOP, den Stack auf Elemente zu überprüfen. Betrachten Sie dazu das kurze Beispielprogramm.

Ausgehend von einem leeren Stack werden folgende drei Operationen durchgeführt:

PUSH(X,A);
POP(X);
POP(X);

Dies führt zwangsläufig zu einem Fehler, da auf dem Stack nur ein Element abgeladen wurde, zwei aber gelöscht wurden. Deshalb ist es in der Anwendung von Stacks unbedingt ratsam, vor jeder TOP-, oder POP- Operation, abzuchecken, ob der betrachtete Stack nicht leer ist.

IF NOT IS_EMPTY(X) THEN
POP(X);

Programmierung von Stacks

Kommen wir nun zur Programmierung von Stacks. Wenn Sie unsere bisherigen Definitionen kurz Revue passieren lassen, werden Sie feststellen, daß der Stack durch wiederholtes Anwenden von PUSH praktisch beliebig (unendlich) groß werden kann. Dies nennt man eine unendliche Datenstruktur. Wenn sich also die maximale Stackgröße nicht abschätzen läßt, ist es erforderlich auf die dynamische Speicherverwaltung zurückzugreifen. (Spätestens hier kommen unsere BASIC- Freunde ins Schwitzen.)

Im Listing der Datentypen (Listing 1a) sehen Sie, daß ich hierzu den Pointer STACK definiert habe. Die abzuspeichernden Informationen (STACK_DATA) habe ich als INTEGER gewählt, hier kann aber jeder beliebige Typ stehen. Ein STACK_ELEMENT besteht somit aus STACK_DATA und einem Zeiger auf das darunterliegende Stackelement (NEXT). Mit dieser Struktur ist es somit möglich den Stack, laut den geforderten, unendlichen Merkmalen, bis zur Arbeitsspeichergröße des ATARI ST aufzublasen. Die Arbeitsweise sieht folgendermaßen aus:

  1. Vereinbarung einer Variable vom TYP STACK (VAR X : STACK;) Machen Sie sich an dieser Stelle bitte klar, daß es sich bei X, wegen der Zeigerstruktur unseres Datentypes, eigentlich nicht um einen Stack, sondern lediglich um einen Stackpointer handelt. Trotzdem werde ich im Folgendem immer vom 'Stack X' sprechen.
  2. Initialisierung dieser Variable X mit CREATE zu NIL, um den leeren Stack zu kennzeichnen.
  3. Durch jeden Aufruf von PUSH, wird dem Stack X, zunächst dem leerem Stack, ein Element A hinzugefügt, indem mittels NEW ein neues Element (NEW_ELEMENT) erzeugt wird. Die Daten dieses neuen Elementes werden zu A initialisiert. Der darunterliegende Stack ist ja unser alter Stack, deshalb ist er auch Nachfolger des neuen Elementes. Schließlich wird die Stackspitze (Stackpointer) X auf das neue Element gerichtet.
  4. Mit TOP wird, im Falle des nicht leeren Stacks, das oberste Element des Stacks über den Funktionsreturn zurückgeliefert. Im Falle des leeren Stacks ist der Rückgabewert undefiniert.
  5. Mit POP, schließlich, kann solange das oberste Element des Stacks gelöscht werden, wie noch Elemente vorhanden sind. Am Schluß muß die Rückgabe eines jeden Elementes an das Betriebssystem, mittels DISPOSE, erfolgen. Werden nicht vorhandene Stackelemente gelöscht, so ruft dies keinen Fehler hervor, sondern erzielt lediglich keine Wirkung.
  6. Mit IS_EMPTY kann modulexplizit und wird modulimplizit der Stack X auf Elemente überprüft.

Die Funktionalität der Funktionen und Prozeduren, soweit Sie sie nicht schon aus den Programmbeispielen entnommen haben, findet sich leicht im Listing. Ein X in der Parameterliste steht hier für einen Stack, ein A für die Daten eines Stacks.

Wenn Sie unsere bisherigen Vereinbarungen nochmal betrachten, stellen Sie fest, daß an einer Stelle ein Widerspruch besteht. Zunächst hatte ich gesagt, daß ein Stack beliebig groß werden darf, dann hatte ich gesagt, daß ein Stack sich bis zur Arbeitsspeichergröße ausdehnen dürfe, was natürlich eine unumgängliche Einschränkung darstellt. Natürlich wäre es gut, auch bei der PUSH- Operation eine Sicherheitsabfrage zu besitzen, ob der benötigte Speicherplatz für STACK_DATA noch vorhanden ist. Leider bietet Standard PASCAL hierzu keinerlei Möglichkeit. Zur Anregung zum Selbstprogrammieren möchte ich jedoch sagen, daß PASCALplus zur Abschätzung des freien Speichers die parameterlose Funktion MEMAVAIL besitzt und sich mit der Funktion SIZEOF(STACK_DATA) der benötigte Speicherplatz berechnen läßt.

Was soll das Ganze?

Wenn Sie nicht schon ein wenig in die Materie der Informatik eingedrungen sind, werden Sie sich irgendwann beim Lesen dieses Artikels gefragt haben, 'Was soll das Ganze?', oder, 'Wozu sind Stacks eigentlich gut?'. Antwort: Stacks sind praktisch unentbehrlich. Ein Compiler kommt nicht ohne sie aus, das Betriebssystem legt seine Unterprogrammrücksprungadressen in Stacks ab (Supervisorstack) und nicht zuletzt jedes Anwendungsprogramm macht regen Gebrauch von Stacks (Userstack, Rekursion, ...). Doch das sind alles Formen von Stacks, die den 'normalen' Anwendungsprogrammierer wenig interessieren, außer natürlich ihre höchst positiven Auswirkungen.

Ein allgemeineres Beispiel für die Anwendungsgebiete von Stacks ist die Analyse und Auswertung arithmetischer Formeln. Wer hat nicht schon einmal neidisch unsere Interpreterfreunde beäugt, wenn es darum geht in einem Programm eben eine Zeile mit einer mathematischen Formel zu ändern. Diese hier so beiläufig erledigte Arbeit, stellt Compilersprachen vor einige Probleme, da eine Änderung des Quellcodes als Lösung ausscheidet.

Anwendung von Stacks: Formelauswertung

Als Demonstration der Möglichkeiten von Stacks, werde ich Ihnen nun ein vereinfachtes Modell zur Auswertung arithmetischer Ausdrücke vorstellen. Hierzu ist es zunächst erforderlich, einige Bezeichnungen zu klären. Grundsätzlich ist es möglich arithmetische Ausdrücke in dreierlei Form darzustellen.

  1. Da wäre zunächst die allen bekannte Notation mit zwei Operanden und dazwischen stehendem Operator: a+b Diese Art der Schreibweise wird infix-Notation genannt.
  2. Weiterhin gibt es noch die präfix-Notation mit vorstehendem Operator und nachstehenden Operanden: +ab
  3. Als letztes noch, die uns interessierende, postfix-Notation, mit nachstehendem Operator und vorstehenden Operanden: ab+

Ziel des Programmes wird es nun sein, einen arithmetischen Ausdruck, während der Eingabe, von der, dem Menschen angepaßten, infix-Notation in die computerfreundliche postfix-Notation zu bringen. Die Computerfreundlichkeit der postfix-Notation liegt darin begründet, daß sämtliche Prioritätsregeln alleine durch die Abfolge von Operanden und Operatoren berücksichtigt werden. Betrachten Sie hierzu folgendes Beispiel:

infix 1*(2+3) ---> postfix 1 2 3 + *

Die Auswertung dieser postfix-Schreibweise erfolgt von links nach rechts. Hierzu werden zunächst die Operatoren betrachtet, wobei man, als Erstes, auf den '+'-Operator stößt. Dieser bezieht sich auf die beiden direkt links neben ihm stehenden Operanden, also '2' und '3'. Das Ergebnis, sowie die erste Zahl, bilden nun ihrerseits wieder die Operanden für den nachfolgenden '*'-Operator. Wie Sie sehen, ist Klammerung und Punkt-vor-Strich-Rechnung hierbei bereits implizit in der Abfolge der Operatoren berücksichtigt. Wie sich in der untenstehenden, algorithmischen Betrachtung, des Problemes, herausstellen wird, werden sowohl bei der Umwandlung in die postfix-Form, als auch bei der Auswertung dieses Ausdrucks, Stacks benötigt.

Zur Eingabe zugelassen werden arithmetische Ausdrücke in infix-Notation, die ganze Zahlen enthalten, sowie die Zeichen ('+','-','','(',')'), also drei der Grundrechenarten plus Klammerausdrücken. Um dem Programm das Ende eines Ausdruckes mitteilen zu können, führe ich noch das Endesymbol '.' ein. Wenn Sie nun das einfache Beispiel '11-1' betrachten, so stellen Sie fest, daß die postfix-Notation, '111-', nicht mehr eindeutig ist, da die Trennlinie zwischen den beiden Zahlen nicht mehr bestimmt werden kann. Deshalb ist es, von Seiten des Programmes, erforderlich, ein Zeichen in die postfix-Form einzufügen, daß das Ende einer ganzen Zahl symbolisiert. Hierzu habe ich '#' gewählt. In unserem einfachen Beispiel sehe die postfix-Form nun wie folgt aus: '11#1#-'. Daraus ergibt sich jetzt ('0'-'9','+','-','','(',')','.','#') als Gesamtalphabet, wobei '#' von der Eingabe ausgeschloßen ist. Weiterhin läßt sich feststellen, daß die Zahlen in allen Notationen (infix, postfix und präfix) die gleiche Abfolge besitzen. Dies bedeutet, daß Zahlen, sofort bei der Eingabe in die postfix-Notation übernommen werden können. Lediglich die Folge der Operatoren ist der postfix-Form anzupassen, wobei die Prioritäten der Punkt-vor-Strich-Rechnung und der Klammern berücksichtigt werden müßen. Zur Berücksichtigung dieser Prioritäten, wird nun ein Stack benutzt.

  1. Eine geöffnete Klammer wird 'abgestackt'.
  2. Bei einer geschloßenen Klammer werden alle Operatoren vom Stack geholt und in die postfix-Form übernommen, bis eine offene Klammer erscheint. Diese wird überschrieben.
  3. Bei einem Operator werden alle auf dem Stack liegenden Operatorzeichen, die mindestens gleiche Priorität, wie das Gelesene, haben ausgegeben. Erscheint ein Zeichen mit kleinerer Priorität auf dem Stack, so wird das aktuelle Zeichen abgestackt. '(' hat hierbei die niedrigste Priorität.

Programm

Mit diesen Vorbetrachtungen können wir uns nun dem Programm zuwenden (Listing 1c). Als Stack habe ich den, in Listing 1a) und Listing 1b) beschriebenen, Integer-Stack benutzt.

VAR X: STACK;

Zum Speichern der postfix-Form, zwischen EINGABE und AUSWERTUNG, benutze ich einen ARRAY:

AUS : ARRAY [ 1..80 ] OF CHAR;

Je nach gewünschter Größe der Ausdrücke, müßte die Grenze, 80, nach unten, oder nach oben verschoben werden.

Eingabe

Kommen wir nun zur PROCEDURE EINGABE. Sie besitzt drei Unterroutinen. Die erste Unterroutine SCHREIBE, schreibt einen Charakter in den Zwischenspeicher für die postfix-Form (AUS). Die nächsten beiden Unterroutinen übernehmen Aufgaben aus dem oben beschriebenen Algorithmus. CLEAR arbeitet den Stack bis auf die nächste geöffnete Klammer ab (Punkt 2). PRIOR weißt jedem Operator seine Priorität zu. In der PROCEDUR selber, findet sich nun, im Wesentlichen, der Algorithmus wieder. Nach einigen Einleitungspreliminarien, Erzeugung des Stack und Abstacken einer geöffneten Klammer zur Stackbodenmakierung, beginnt die WHILE-Schleife, die die Eingabe bis zur Endemarkierung einließt. Hier wird zunächst ein Zeichen gelesen. Handelt es sich um eine Zahl, wird diese direkt in den AUS-ARRAY geschrieben. Bei einem anderen Zeichen wird weiter differenziert. Zunächst muß hier überprüft werden, ob der Vorgänger eine Zahl war, weil in diesem Falle noch die Zahlendemarkierung '#' nach AUS zu Schreiben ist. Die Analyse des Zeichens selber (CASE EIN OF), erfolgt in völliger Analogie zum Algorithmus (siehe Punkt 1-3).

Ausgabe

Die einzige Funktion, der darauffolgenden PROCEDURE AUSGABE, besteht darin, den ARRAY AUS auszugeben.

Auswertung

Hierauf folgt der zweite Hauptteil des Programmes, die AUSWERTUNG. Auch hier sind Theorie und Praxis nicht besonders unterschiedlich. Eine WHILE-Schleife über dem ARRAY AUS wird solange besucht, bis das Wortendesymbol '.' erscheint. Ist der untersuchte Charakter eine Ziffer, so werden die nachfolgenden Charakter bis zur Zahlendemarkierung '#' untersucht und in einen INTEGER-Wert umgesetzt (WERT). Dieser wird zwecks weiterer Betrachtung gePUSHt. Handelt es sich jedoch um einen Operator, so werden die zwei obersten Operanden vom Stack geholt und mittels dieses Operators verknüpft. Hierbei ist auf die Reihenfolge der Operatoren zu achten, den sie stehen ja umgekehrt im Stack. Das Ergebnis wird dann wieder gePUSHt. Ist die postfix-form ganz abgearbeitet(Ende WHILE), so liegt das Ergebnis oben auf dem Stack TOP(X).

Main

Das Hauptprogramm beschränkt sich schließlich auf den Aufruf der drei oben beschriebenen Funktionen. Abbildung 1b) zeigt einen Probedurchlauf. Zunächst erfolgt die Eingabe der Formel in infix, als Ergebnis, folgt dieselbe Formel in postfix, sowie das errechnete Resultat.

Eingabe Infix        ---> 3+7-2*(3+5-6*(3+1-(2*3+4))).
Modifizierte Postfix ---> 3#7#+2#3#5#+6#3#1#+2#3#*4#+-*-*-.
Auswertung           ---> -78

Abbildung 1b: Testlauf RECHNER.TOS

Vorausschau

Hiermit wäre ich mit den Stacks am Ende. Der Ausbau des obigen, kleinen Demoprogrammes, oder andere Stackanwendungen, seien dem interessierten Leser überlassen. In der nächsten Folge von Algorithmen & Datenstrukturen werde ich Queues (Warteschlangen) vorstellen. Hier werden auch wieder zwei kleine Module, zur eigenen Implementierung, von Queues, sowie ein Beispielprogramm, zu erwarten sein. In der Hoffnung Sie mit diesem Artikel nicht zu sehr verschreckt zu haben, erwarte ich dort unser Wiedersehen (lesen).

Listings zu diesem Artikel


Dirk Brockhaus
Aus: ST-Computer 10 / 1987, Seite
Links
Copyright-Bestimmungen: siehe Über diese Seite