Theorieteil zu Folge 21: Stackmaschinen

Grundsätzliche Arbeitsweise einer Stackmaschine

Eine Stackmaschine ist ein Stack, der rechnen kann. Dazu wird die Klasse Stack um vier weitere Methoden ergänzt: add(), sub(), mul() und div(). Was diese Methoden bewirken, zeigt die folgende Abbildung:

Die Methode add() nimmt die beiden obersten Stackelemente, entfernt sie vom Stack und pusht das Ergebnis der Addition wieder auf den Stack.

Die Methode sub() subtrahiert das oberste Stackelement vom zweitobersten, entfernt beide Elemente vom Stack und pusht das Ergebnis wieder auf den Stack.

Die Methode mul() nimmt die beiden obersten Stackelemente, entfernt sie vom Stack und pusht das Ergebnis der Multiplikation wieder auf den Stack.

Die Methode div() dividiert das zweitoberste Stackelement durch das oberste, entfernt beide Elemente vom Stack und pusht das Ergebnis wieder auf den Stack.

Ganz so einfach wie eben beschrieben geht das natürlich nicht. Bevor die beiden obersten Stackelemente aus den Stack entfernt werden, müssen natürlich die Werte dieser beiden Element gesichert werden.

Eine nicht so gute Implementation von add()

Wir gehen jetzt mal davon aus, dass wir eine eigene Klasse Stackmaschine vorliegen haben, die durch Vererbung von der Klasse Stack abgeleitet wurde. Alle Operationen der Klasse Stack stehen der Klasse Stackmaschine also zur Verfügung. Wie könnten wir dann die Methode add() der Klasse Stackmaschine implementieren? Hier eine Möglichkeit:

public void add()
{
   list[max-1] += list[max]; 
   max--;  
}

Das ist wirklich ein sensationell kurzer Quelltext. Bekanntlich implementiert man ja einen Stack grundsätzlich so, dass die neuen Elemente hinten an den Array angehängt werden, der übrigens stets "list" heißen muss. Die Pop-Operation entfernt stets das letzte Element, und Top gibt immer den Wert des letzten Elementes zurück. Wenn der Stack so organisiert ist, dann funktioniert der obige Quelltext tatsächlich (ich habe in jetzt nicht selbst ausprobiert, aber ich denke schon, dass er funktioniert).

Und was ist, wenn der Stack anderes implementiert wurde? Wenn zum Beispiel der interne Array gar nicht "list" heißt, sondern beispielsweise "st"? Dann passt man den Quelltext der add()-Methode eben entsprechend an.

Und was ist, wenn der Stack völlig anderes implementiert wurde, zum Beispiel mithilfe einer einfach oder doppelt verketteten dynamischen Liste? Dann passt man den Quelltext der add()-Methode eben entsprechend stärker an?

Uns was ist, wenn man keine Ahnung davon hat, wie die Klasse Stack implementiert wurde, oder wenn einen die Implementierung von Stack überhaupt nicht interessiert, weil man beim Programmieren solche Klassen als black box behandelt, als schwarze Kästen, in die man nur mit Hilfe von sondierenden Methoden hineinschauen kann und deren Inhalt man nur mit Hilfe manipulierender Methoden verändern kann?

Eine bessere Implementation von add()

Genau dies ist nämlich der Grundgedanke der Datenkapselung. Man wendet das Prinzip des information hiding an, man versteckt also alle Informationen, die man nicht unbedingt braucht, vor sich selbst und vor anderen Programmierern. Das ist ein guter Schutz vor Fehlern und ein effizientes Hilfsmittel beim Schreiben großer und komplexer Programmsysteme.

Betrachten wir nun eine add()-Methode, bei der das Datenkapselungs-Prinzip bewahrt wurde:

public void add()
{
   double ergebnis = top(); 
   pop(); 
   ergebnis += top(); 
   pop(); 
   push(ergebnis);
}

Vorteile der Datenkapselung

Diese Art und Weise der Programmierung ermöglicht sogar einen Austausch der Mutterklasse Stack gegen eine völlig anders implementierte Mutterklasse.

Beispiel: In der alten Klasse Stack wurden die int-Zahlen in einem Array verwaltet; die zuletzt hinzugefügte Zahl wurde im letzten Arrayelement gespeichert. Nun wird die Mutterklasse Stack ausgetauscht. In der neuen Klasse Stack werden die int-Zahlen in einer einfach verketteten Liste gespeichert, wobei die zuletzt hinzugefügte Zahl immer an den Listenanfang gesetzt wird.

Beide Klassen stellen öffentliche manipulierende und sondierende Methoden push(), pop(), top() und empty() zur Verfügung, auch die Parameter und Rückgabewerte gleichen sich. Ein Austausch der alten Klasse Stack gegen die neue ist problemlos möglich, wenn die Tochterklasse Stackmachine gemäß dem Prinzip der Datenkapselung programmiert wurde. Wenn natürlich ein genialer Programmier die add()-Methode so schreibt, dass die beiden letzten Array-Elemente addiert werden, funktioniert der Quelltext nach dem Austauschen nicht mehr. Der Programmierer muss den gesamten Quelltext von Stackmachine umschreiben und an die neue Stack-Klasse anpassen. Eine Arbeit, die er sich hätte sparen können, wenn er von vornherein nach dem Prinzip der Datenkapselung verfahren wäre.

Die vier arithmetischen Methoden add(), sub(), mul() und div()

Die Methode mul() zur Multiplikation arbeitet ähnlich wie add(), nur dass hier die Werte der beiden oberen Stackelement multipliziert werden.

Bei der Subtraktion und bei der Division muss man etwas mehr überlegen. Soll z.B. bei der Subtraktion das oberste Stackelement vom zweitobersten abgezogen werden oder umgekehrt? Aus der Einleitung wissen Sie bereits, dass das oberste Stackelement vom zweitobersten abgezogen wird. Aber warum ist das so? Wieso nicht umgekehrt.

Gleiches gilt für die Division. Wieso wird das zweitoberste Element durch das oberste dividiert und nicht umgekehrt?

Wenn Sie diese Fragen wirklich verstehen wollen, müssen Sie sich wohl oder übel mit einem weiteren theoretischen Thema beschäftigen. Es stellt sich nämlich die Frage, wozu sind Stackmaschinen überhaupt gut? Wenn man das verstanden hat, weiß man auch die Antworten auf die obigen Fragen.

Stackmaschinen und arithmetische Ausdrücke

(4 + 3.14) / (8 - 2.71)

Berechnung eines Klammerausdrucks durch einen Menschen

Ein mathematisch geschulter Mensch weiß sofort, wie man den obigen Klammerausdruck ausrechnen muss: Zuerst wird die Addition in der linken Klammer ausgeführt, als zweites die Subtraktion in der rechten Klammer. Die beiden so gewonnenen Zahlen werden im dritten Schritt multipliziert.

Berechnung eines Klammerausdrucks durch eine Stackmaschine

Eine Stackmaschine geht ähnlich vor wie ein mathematisch geschulter Mensch. Das ist ja auch kein Wunder, denn 90% aller Stackmaschinen wurden von mathematisch geschulten Menschen entwickelt.

Berechnung der linken Klammer

Zuerst wird also der linke Klammerausdruck berechnet. Zu Beginn der Berechnung ist der Stack noch völlig leer. Es werden nun die beiden Zahlen 4 und 3.14 auf den Stack gepusht:

push(4);
push(3.14);

Danach sieht der Stack so aus:

Nach der Ausführung des add()-Befehls sieht der Stack dann so aus:

Berechnung der rechten Klammer

Nun wird die zweite Klammer berechnet. Wieder werden die beiden Zahlen gepusht:

push(8);
push(2.71);

Danach besteht der Stack aus drei Elementen:

Nun wird die Subtraktion ausgeführt. Eine Subtraktion entspricht ja dem Schema

a - b

Da b zuletzt gepusht wurde, steht b oben im Stack. Bei einer Subtraktion muss die Stackmaschine also das oberste Stackelement vom zweitobersten abziehen, nicht umgekehrt. Daher muss der sub()-Befehl der Stackmaschine folgenden Code enthalten:

ergebnis = top();
pop();
ergebnis = top() - ergebnis;
pop();
push(ergebnis);

Bei der dritten Zeile des obigen Codes achten Sie bitte darauf, dass es sich hier nicht um eine mathematische Gleichung handelt, sondern um Computerbefehle. Von top() wird der alte Wert von ergebnis subtrahiert, und daraus berechnet sich dann der neue Wert von ergebnis.

Nach der Subtraktion ist das Ergebnis der rechten Klammer berechnet, und der Stack sieht jetzt so aus:

Berechnung des Endergebnisses

Jetzt "erinnert" sich die Stackmaschine daran, dass ja auch noch eine Division durchzuführen ist; und zwar soll der erste Klammerausdruck durch den zweiten Klammerausdruck dividiert werden. Der erste Klammerausdruck wurde bereits berechnet, und das Ergebnis dieser Berechnung steht im zweitobersten Stackelement. Das Ergebnis des zweiten Klammerausdrucks steht im obersten Stackelement. Also muss das zweitoberste Element durch das oberste dividiert werden.

Am Ende dieser Division steht das Endergebnis der Berechnung im Stack - und sonst gar nichts:

Ausblick

Aufbau eines Stackinterpreters

Realisierung eines Stackinterpreters

In Java benötigen wir eine Klasse Stackinterpreter, die ihrerseits Objekte der Klassen Stackmaschine sowie Codepuffer enthält. Der Interpreter holt sich den jeweils nächsten Befehl aus dem Codepuffer, z.B. "push 4", und führt diesen Befehl dann aus. Dazu muss der Stackinterpreter natürlich über eine Befehlserkennung verfügen, die wir programmieren müssen. Nachdem der Interpreter erkannt hat, dass es sich um einen push-Befehl handelt und dass das Argument dieses Befehls die Zahl 4 ist, kann er die Stackmaschine dazu veranlassen, die Zahl 4 auf den Stack zu pushen.

Vorgehen in diesem Kurs

Wir werden nicht gleich mit dem Stackinterpreter beginnen, sondern erst mal ganz in Ruhe eine einfache Stackmaschine bauen. Dazu ist es gut, wenn man einen funktionierenden Stack zur Verfügung hat. Mit Hilfe der Vererbung, die wir ja bereits in einem früheren Kapitel kennengelernt haben, leiten wir dann aus der Klasse Stack die Klasse Stackmaschine ab.

zurück zum Lehrtext

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 20. Juli 2006 und völlig neu überarbeitet am 4. März 2008.