Kapitel 18

Rohübersetzung -- bitte um Rückmeldungen über Fehler und Unklarheiten an Mike Müller

Stacks

18.1 Abstrakte Datentypen

Bisher haben wir nur konkrete Datentypen kennengelernt, bei denen wir vollständig spezifiziert haben, wie diese implementiert sind. So repräsentiert zum Beispiel die Klasse Karte eine Karte durch 2 Ganzzahlen. Wie wir damals diskutiert hatten, ist das nicht der einzige Weg eine Karte abzubilden; es existieren viele alternative Implementierungen.

Ein abstrakter Datentyp (ADT) spezifiziert eine Menge an Operationen, (oder Methoden) und die Semantik der Operationen (was diese tun), er spezifiziert nicht wie diese implementiert sind. Das macht ihn abstrakt.

Warum ist das nützlich?

Die Spezifizierung eines Algorithmus wird einfacher, wenn man die nötigen Operationen schon bezeichnen kann, ohne sie sich gleichzeitig um die auszuführen Operationen kümmern zu müssen.
Da es typischer Weise viele Wege gibt einen ADT zu implementieren, kann es nützlich sein einen Algorithmus zu entwickeln, der mit jeder der möglichen Implementierungen verwendet werden kann.
Häufig genutzte ADT, wie der in diesem Kapitel behandelte Stack, sind häufig in Standardbibliotheken implementiert. Auf diese Weise können sie von vielen Programmieren verwendet werden.
Die Operationen auf ADT stellen eine allgemeine Hochsprache für die Spezifizierung und der Kommunikation über Algorithmen dar.

Wenn wir über ADT sprechen, unterscheiden wir häufig zwischen Code, der die ADT nutzt, den so genannten Clientcode und dem Code, der den DT implemeniert, dem Bibliothekscode.

18.2 Der abstrakte Datentyp Stack

In diesem Kapitel werden wir uns mit einem gebräuchlichen ADT, dem Stack (eng. Stapel) , beschäftigen. Ein Stack ist eine Sammlung, also eine Datenstruktur, die mehrere Elemente enthält. Andere Sammlungen, die wir kennengelernt haben sind u.a. Listen und Dictionaries.

Ein ADT wird durch die Operationen, die mit ihm ausgeführt werden können definiert. Diese werden Interface genannt. Das Interface für den ADT Stack besteht aus diesen Operationen:

__init__: Intialisiere einen neuen, leeren Stack.
push: Füge ein neues Element (eng. item) zum Stack hinzu.
pop: Entferne ein Element vom Stack und gib es als Ergebnis des Methodenaufrufes zurück. Das zurückgegebene Element ist immer das zuletzt hinzugefügte.
istLeer: Teste ob der Stack leer ist.

Ein Stack wird manchmal als "zuletzt rein zuerst raus" or LIFO (last in, first out) Datenstruktur bezeichnet, weil das Element, das zuletzt hinzugefügt wurde, zuerst entfernt wird.

18.3 Implementierung von Stacks mit Python-Listen

Die Listenoperationen, die Python zur Verfügung stellt sind denen ähnlich, die einen Stack definieren. Das Interface entspricht nicht genau dem wie es sein soll, aber wir können Code schreiben, der vom ADT Stack zur eingebauten Operationen übersetzt.

Dieser Code wir Implementierung des ADT Stack genannt. Im Allgemeinen ist eine Implementierung eine Menge von Methoden, die den syntaktischen und semantischen Anforderungen eines Interfaces entsprechen.

Hier ist eine Implementierung des ADT Stack unter Nutzung einer Python-Liste:

class Stack :
def __init__(self) :
self.items = []

def push(self, item) :
self.items.append(item)

def pop(self) :
return self.items.pop()

def istLeer(self) :
return (self.items == [])

Ein Objekt Stack enthält ein Attribut, das mit items bezeichnet wird. Bei diesem handelte es sich um eine Liste mit Elementen im Stack. Die Initialisierungsmethode setzt items auf eine leere Liste.

Die Methode push (eng. schieben) hängt ein neues Element an items an und legt es damit auf den Stack. Um ein Element vom Stack zu nehmen nutzt die Methode pop die homonyme * Note Listenmethode, mit der das letzte Element der Liste entfernt und zurückgegeben wird.

Schließlich vergleicht die Methode istLeer items mit einer leeren Liste, um zu kontrollieren, ob der Stack leer ist.

Eine Implementierung wie diese, in der die Methoden aus einfachen Aufrufen existierender Methoden besteht, wird als Furnier bezeichnet. Im realen Leben ist ein Furnier eine dünne Schicht Holz guter Qualität, die bei der Möbelherstellung verwendet wird, um darunter liegendes Holz geringer Qualität zu verbergen. Informatiker nutzen diese Metapher, um ein kleines Stück Code zu beschreiben, das die Details einer Implementierung verbirgt und ein einfacheres oder mehr standardisiertes Interface zu bieten.

18.4 Legen und Holen

Ein Stack ist ein generischer Datentyp, was bedeutet, dass wir jeden beliebigen Typ als Element hinzufügen können. Das folgende Beispiel legt zwei Ganzzahlen und einen String auf den Stack:

>>> s = Stack()
>>> s.push(54)
>>> s.push(45)
>>> s.push("+")

Wir können die Methoden istLeer und pop nutzen, um alle Elemente zu entfernen und auszudrucken.

while not s.isLeer() :
print s.pop(),

Der Output sieht so aus + 45 54. Mit anderen Worten haben wir geraden einen Stack verwendet, um die Element rückwärts zu drucken! Zugegeben ist das nicht das Standardformat zum Drucken einer Liste, aber durch Nutzung eines Stack, war es bemerkenswert einfach umzusetzten.

Du solltest diesen kurzen Code mit der Implementierung von druckeRueckwaerts in Abschnitt vergleichen.

Es gibt eine natürliche Parallele zwischen der rekursiven Version druckeRueckwaerts und hier den gezeigten Stackalgorithmen. Der Unterschied liegt darin, dass druckeRueckwaerts den Laufzeitstack von Python nutzt, um den Überblick über die Knoten zu behalten während es durch die Liste geht. Auf dem Rückweg von der Rekursion werden die Knoten dann ausgedruckt. Der Stackalgorithums macht genau das Gleiche, mit dem Unterschied, dass er anstatt des Laufzeitstacks das Objekt Stack nutzt.

18.5 Nutzung eines Stacks für die Auswertung von Postfix-Notationen

In den meisten Programmiersprachen werden mathematische Ausdrücke mit dem Operator zwischen den beiden Operanden zum Beispiel so 1+2 geschrieben. Dieses Format wird als Infix-Notation bezeichnet. Eine Alternative, die von einigen Rechner genutzt wird, wird Postfix-Notation genannt. In der Postfix-Notation folgt der Operator den Operanden wie in 1 2 +.

Der Grund, der die Postfix-Notation manchmal nützlich macht besteht darin, dass es einen natürlichen Weg gibt Ausdrücke in Postfix-Notation mit einem Stack auszuwerten:

Beginnend am Anfang des Ausdruck nimm einen Term (Operator oder Operant) nach dem anderen.

Wenn der Term ein Operand ist, lege ihn auf den Stack.
Wenn der Term ein Operator ist, nimm zwei Operanden vom Stack, führe die Operationen an ihnen durch, und lege das Ergebnis zurück auf den Stack.

When wir zum Ende des Ausdruck kommen, sollte genau ein Operand auf dem Stack übrig sein. Dieser Operand ist das Endergebnis.

Wende diesen Algorithmus als Übung auf den Ausdruck 1 2
+ 3 * an.

Dieses Beispiel demonstriert einen der Vorteile der Postfix-Notation es gibt keinen Bedarf Klammern zu verwenden, um die Reihenfolge der Operationen zu kontrollieren. Um das gleiche Ergebnis mit Infix-Notation zu erhalten müssen wir (1 + 2)*
3 schreiben.

Schreibe als Übung einen Ausdruck in Postfix-Notation, der 1 + 2* 3 entspricht.

18.6 Parsen

Um den vorangegangen Algorithmus zu implementieren müssen wir durch den String gehen und ihn in Operanden und Operatoren aufteilen. Diese Vorgehen ist ein Beispiel für das Parsen. Die Ergebnisse die individuellen Teile des Stings werden Token genannt. Du erinnerst dich vielleicht an diese Worte aus dem Kapitel 1.

Python bietet eine Methode split sowohl im Modul string als auch im Modul re (reguläre Ausdrücke). Die Funktion string.split teilt einen String in eine Liste unter Verwendung eines einzelnen Zeichens als Trennzeichen. Zum Beispiel:

>>> import string
>>> string.split("Jetzt ist die Zeit"," ")
['Jetzt', 'ist', 'die', 'Zeit']

In diesem Fall wird das Leerzeichen als Trennzeichen gefordert. Der String wird folgerichtig an jedem Leerzeichen geteilt.

Die Funktion re.split bietet mehr, indem wir einen regulären Ausdruck anstatt eines Trennzeichens nutzen können. Ein regulärer Ausdruck ermöglicht es eine Menge von Strings zu spezifizieren. Zum Beispiel ist [A-z] die Menge aller aller Buchstaben (ohne Umlaute und ß) and [0-9] die Menge aller Ziffern. Der Operator ^ negiert eine Menge, so dass [^0-9] die Menge von allen Zeichen darstellt, die keine Ziffern sind. Das ist genau die Menge, die wir benötigen, um Ausdrücke in Postfix-Notation zu zerteilen:

>>> import re
>>> re.split("([^0-9])", "123+456*/")
['123', '+', '456', '*', '', '/', '']

Beachte, dass die Reihenfolge der Argumente von in string.split abweicht; das Trennzeichen kommt vor dem String.

Die resultierende Liste enthält die Operanden 123 und 456 und die Operatoren * und /. Sie enthält auch zwei leere Strings, die nach den Operanden eingefügt wurden.

18.7 Auswerten von Postfix-Notationen

Zum Auswerten von Ausdrücken in Postfix-Notation werden wir den Parser des vorangegangenen Abschnitts und den Algorithmus des Abschnitts davor nutzen. Um das Ganze einfach zu halten, beginnen wir mit einem Auswerteprogramm, das nur die Operatoren + und * implementiert:

def evalPostfix(expr):
import re
tokenList = re.split("([^0-9])", expr)
stack = Stack()
for token in tokenList:
if token == '' or token == ' ':
continue
if token == '+':
sum = stack.pop() + stack.pop()
stack.push(sum)
elif token == '*':
product = stack.pop() * stack.pop()
stack.push(product)
else:
stack.push(int(token))
return stack.pop()

Die erste Bedingung kümmert sich um Leerzeichen und leere Strings. Die nächsten beiden Bedingungen behandeln die Operatoren. Wir nehmen vorerst an, dass alles andern ein Operand sein muss. Natürlich wäre es besser auf fehlerhaften Input zu kontrollieren und eine Fehlermeldung auszugeben, aber dazu kommen wir erst später.

Wir testen das Ganze indem wir den Postfix-Ausdruck (56+47)*2 auswerten:

>>> print evalPostfix ("56 47 + 2 *")
206

Das is nah genug dran.

18.8 Nutzer und Anbieter

Eins der grundlegenden Ziele von ADT ist es Interessen vom Anbieter, der den Code schreibt, der der die ADT implementiert und dem Nutzer, der den ADT anwendet strikt voneinander zu trennen. Der Anbieter kümmert sich nur darum, dass die Implementierung in Übereinstimmung mit der Spezifikation des ADT korrekt ist und nicht darum, wie er genutzt werden wird.

Umgekehrt geht der Nutzer davon aus, dass die Implementierung korrekt ist und kümmert sich nicht um die Details. Wenn du einen der eingebauten Typen von Python nutzt hast du den Luxus ausschließlich als Nutzer zu denken.

Wenn du einen ADT implementierst must du natürlich auch den Nutzercode schreiben, um diesen zu testen. In diesem Falle spielst du beide Rollen, was durchaus verwirrend sein kann. Du solltest dich bemühen immer zu wissen, welche Rolle du gerade inne hast.

18.9 Glossary

abstrakter Datentyp (ADT) Ein Datentyp (üblicherweise eine Sammlung von Objekten), der durch eine Menge von Operationen definiert ist, aber auf unterschiedlichen Wegen implementiert werden kann.	abstract data type (ADT) A data type (usually a collection of objects) that is defined by a set of operations but that can be implemented in a variety of ways.
Interface Eine Menge von Operationen, die einen ADT definieren.	interface The set of operations that define an ADT.
implementation Code, der die syntaktischen und semantischen Anforderungen eines Interfaces erfüllt.	implementation Code that satisfies the syntactic and semantic requirements of an interface.
client Ein Programm (oder dessen Autor), das einen ADT nutzt.	client A program (or the person who wrote it) that uses an ADT.
provider Der Code (oder dessen Autor), der einen ADT implementiert.	provider The code (or the person who wrote it) that implements an ADT.
Furnier Eine Klassendefinition, die einen ADT mit Methodendefinitionen definiert, die andere Methoden aufrufen und manchmal auch noch einfache Transformationen durchführen. Ein Furnier leistet selbst keine wesentliche Arbeit, aber es verbessert oder standardisiert Interface, das vom Nutzern gesehen wird.	veneer A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer does no significant work, but it improves or standardizes the interface seen by the client.
generische Datenstruktur Eine Art der Datenstruktur, die Daten beliebigen Typs enthalten kann.	generic data structure A kind of data structure that can contain data of any type.
Infix-Notation Eine Art des Schreibens mathematischer Ausdrücke, bei der die Operatoren zwischen den Operanden stehen.	infix A way of writing mathematical expressions with the operators between the operands.
Postfix-Notation Eine Art des Schreibens mathematischer Ausdrücke, bei der die Operatoren nach den Operanden stehen.	postfix A way of writing mathematical expressions with the operators after the operands.
parsen Das Lesen eines Strings mit Zeichen oder Token und das Analysieren seiner grammatikalischen Struktur.	parse To read a string of characters or tokens and analyze its grammatical structure.
Token Eine Menge von Zeichen, die zum Zwecke des Parsens als Einheit behandelt werden, so wie die Worte in einer natürlichen Sprache.	token A set of characters that are treated as a unit for purposes of parsing, such as the words in a natural language.
Trennzeichen Ein Zeichen, das verwendet wird, um Token voneinander zu trennen. Es ist mit den Interpunktionszeichen in natürlichen Sprachen vergleichbar.	delimiter A character that is used to separate tokens, such as punctuation in a natural language.