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.