Stapel-Anwendungen in Excel-VBA
Für die folgenden Aufgaben sollen Funktionen programmiert werden, die sich bei der Lösung eines Stapels (stack) bedienen.
Einen String umdrehen (invertieren)
Die Kopfzeile der Funktion soll lauten:
Public Function invertString (ByVal s As String) As String.
Beispiele für Invertierungen:
- Aus „123456789” wird „987654321”
- Aus „Anna“ wird „annA“
- Aus „Obama“ wird „amabO“
Prüfen, ob ein arithmetischer Ausdruck korrekt geklammert ist
Die Funktion soll die Kopfzeile
Public Function balanceCheck (ByVal s As String) As Boolean
besitzen. Sie liefert True, wenn die Klammern in dem Ausdruck s korrekt gesetzt sind, sonst False.
Beispiele:
- Der Ausdruck „(3x – 7y) * z + (4x – 2y) * v“ ist korrekt geklammert
- Der Ausdruck „((a + b) * c( -e“ ist nicht korrekt geklammert
Bei der Beurteilung der Korrektheit kann man folgendermaßen vorgehen:
Lege einen leeren Stapel an. Lies ein Zeichen von s nach dem anderen. Wenn das Zeichen eine öffnende Klammer ist, dann lege diese auf den Stapel. Ist es eine schließende Klammer und der Stapel ist leer, dann liegt ein Fehler vor. Falls der Stapel nicht leer ist, nimm ein Element herunter. Falls das entnommene Element keine öffnende Klammer ist, dann liegt ein Fehler vor. Wenn bei Erreichen des Endes von s der Stapel nicht leer ist, dann liegt ebenfalls ein Fehler vor.
Einen Postfix-Ausdruck auswerten
Bei der Postfix-Notation werden die Operatoren hinter die Operanden gestellt, nicht wie beim Infix-Ausdruck dazwischen. Solche Ausdrücke lassen sich mit Hilfe eines Stapels leicht auswerten. Außerdem kann auf Klammern verzichtet werden.
Beispiele
- Dem Infix-Ausdruck „ 77 / 10 + 4 “ entspricht der Postfix-Ausdruck
„ 77 10 / 4 + “.
Die Auswertung ergibt 11,7. - Dem Infix-Ausdruck „ 6 * ((5 + (2 + 3) * 8) + 3) “ entspricht der Postfix-Ausdruck
„ 6 5 2 3 + 8 * + 3 + * “.
Die Auswertung ergibt 288.
Die Kopfzeile der Funktion soll lauten:
Public Function calcPE(ByVal expr As String) As String
Der Parameter expr ist der Postfix-Ausdruck. In diesem Ausdruck sollen die arithmetischen Operatoren +, -, / und * vorkommen dürfen. Als Operanden sind Integer- und Double-Zahlen erlaubt. Damit die einzelnen Elemente (Tokens) des Ausdrucks erkannt werden können, ist es nötig, dass sie jeweils mit mindestens einem Leerzeichen voneinander getrennt sind. Zur Aufspaltung des Ausdrucks in die Tokens innerhalb der Funktion kann die VBA-Funktion Split verwendet werden.
Bei der Auswertung eines Postfix-Ausdrucks mit Hilfe eines Stapels kann man wie folgt vorgehen:
Man beginnt mit einem leeren Stapel und geht den Ausdruck von links nach rechts durch. Jedes Mal, wenn man auf einen Operanden stößt, legt man diesen auf den Stapel. Gelangt man an einen Operator, so holt man zwei Elemente vom Stapel und merkt sich diese. Dann wendet man den Operator auf die beiden Elemente an, wobei das zweite als erster Operand fungiert. Das Ergebnis der Operation wird auf den Stapel gelegt. Am Ende liegt das Ergebnis des gesamten Ausdrucks auf dem Stapel.
Einen Infixausdruck in einen Postfixausdruck umwandeln
Mit Hilfe eines Stapels kann man auch einen Infixausdruck in einen Postfixausdruck umwandeln. Wir wollen dafür annehmen, dass im Infixausdruck alle Operationen geklammert sind. Mit anderen Worten, der Ausdruck ist formuliert, als ob es keine Vorrangregeln zwischen den Operatoren und keine Linksassoziativität gäbe. Anstatt beispielsweise zu schreiben
3 * 4 + 2 * 11
schreibt man also
( ( 3 * 4 ) + ( 2 * 11 ) )
Die Umwandlung in einen Postfixausdruck geschieht folgendermaßen:
Man beginnt mit einem leeren Stapel und einem noch leeren Postfixausdruck und geht den Infixausdruck von links nach rechts durch. Jedes Mal, wenn man auf einen Operanden trifft, wird dieser direkt rechts an den Postfixausdruck angefügt. Trifft man auf einen Operator, so wird dieser auf den Stapel gelegt. Sobald man auf eine schließende Klammer trifft, holt man einen Operator vom Stapel und fügt ihn rechts an den Postfixausdruck an. (Anmerkung: zusätzlich müssen Trennzeichen ausgeschrieben werden).
VBA-Code für einen Stapel
Die Grundoperationen für einen Stapel sind
- push (ein Element auf den Stapel legen)
- pop (ein Element vom Stapel herunternehmen)
- top (das oberste Element lesen, ohne es herunterzunehmen)
- isEmpty (Prüfung, ob der Stapel leer ist)
Manche Stapel-Implementierungen enthalten noch weitere Methoden. Die folgende Klasse stack weist nur die oben genannten Basis-Operationen auf. Sie genügen für die gestellten Aufgaben.
‘class stack
Option Explicit
Private s() As Variant
Private tos As Integer
Public Sub initStack()
tos = 0
ReDim s(1 To 1)
End Sub
Public Sub push(ByVal e As Variant)
tos = tos + 1
ReDim Preserve s(1 To tos)
s(tos) = e
End Sub
Public Function pop() As Variant
pop = s(tos)
tos = tos - 1
End Function
Public Function top() As Variant
top = s(tos)
End Function
Public Function isEmpty() As Boolean
isEmpty = tos = 0
End Function
Beachten Sie, dass in dieser Implementierung die Größenanpassung des Arrays s nicht symmetrisch erfolgt. Beim Hinzufügen eines Elements durch push wird s vergrößert, falls dies nötig ist. Beim Wegnehmen durch pop erfolgt jedoch keine Verkleinerung. Grund dafür ist, dass das ReDim s(1 to 0) bei leerem Stapel zu einem Fehler führen würde.