2.4.1. Stapel mit unbeschränkter Elementanzahl (Klasse stack)

Lernziele

Die Klasse stack
Fehler- und Ausnahmebehandlung

Wer hat schon einmal einen Taschenrechner von Hewlett-Packard bedient? Von denen, die es schon einmal getan haben, kommen i. d. R. nur zwei Arten von Antworten: Entweder „Oh Gott! Grauenhaft kompliziert“ oder „Genial! Damit berechne ich jeden noch so komplexen Ausdruck mit ganz wenig Tastendrücken!“ Woran liegt das?

Diese Taschenrechner erwarten die auszuwertenden Ausdrücke nicht in der so genannten Infix-Notation, an die wir seit der Grundschule gewöhnt sind. Infix-Notation bedeutet, dass in einem arithmetischen Ausdruck die Operatoren zwischen den Operanden notiert werden. Dabei gilt dann die Regel „Punktrechnung geht vor Strichrechnung“, und um die Auswertungsreihenfolge zu beeinflussen, müssen Klammern gesetzt werden. Der Ausdruck

3 * ( ( 1 + 2 ) * 3 + 5)

etwa ist in Infix-Notation und hat den Wert 42, eine Zahl, die in der Informatik eine große Rolle spielt.[21]

Taschenrechner von Hewlett-Packard dagegen erwarten die Ausdrücke in der so genannten Postfix-Notation, nach ihrem Erfinder, dem polnischen Logiker Jan Lukasiewicz auch Umgekehrt Polnische Notation genannt. Darin gehen Operanden immer ihren Operatoren voraus, und auf Klammern kann ganz verzichtet werden. Der zu obigem Ausdruck äquivalente in Postfix-Notation lautet

3 1 2 + 3 * 5 + *

Der Wert eines solchen Ausdrucks ergibt sich durch ein einfaches Verfahren, das mit einem Stapel arbeitet: Der Ausdruck wird von links nach rechts gelesen. Wird dabei eine Zahl gelesen, so wird diese auf dem Stapel abgelegt. Wird dagegen ein Operator gelesen, so werden die beiden obersten Zahlen vom Stapel genommen, gemäß des Operators arithmetisch verknüpft und das Ergebnis wieder auf dem Stapel abgelegt. Das Endergebnis ist dann die Zahl, die am Ende als einzige auf dem Stapel liegt.

Ein Programm, das seine Eingabe auf diese Art und Weise mit Hilfe eines Stapels verarbeitet, wird auch als Kellerautomat (engl. push down automaton) bezeichnet. Abbildung 2.18 zeigt, wie ein Kellerautomat für Postfix-Notation den Ausdruck 8 + ( 1 + 2 ) * 4 auswertet.

Abbildung 2.18. Ein Stapel zur Auswertung von arithmetischen Ausdrücken

Ein Stapel zur Auswertung von arithmetischen Ausdrücken

Hier wird der Ausdruck 8+(1+2)*4 (in Umgekehrt Polnischer Notation) mit Hilfe eines Stacks ausgewertet.


Der Vorteil eines Ausdrucks in Postfix-Notation liegt darin, dass auf Klammern und Präzedenzregeln ganz verzichtet werden kann. Die Ausdrücke sind kürzer als ihre Infix-Äquivalente und mit weniger Aufwand (nämlich mit Hilfe eines Stapels) von einem Programm auszuwerten. Wenn man sich erst einmal an diese Notation gewöhnt hat, weiß man es sehr zu schätzen, beim Auswerten komplexer Ausdrücke nicht mehr auf Klammerungsebenen achten zu müssen. Man ist dann sehr schnell mit einem entsprechenden Taschenrechner. Allerdings muss man zuerst ein Gespür dafür entwickeln, wie ein großer Ausdruck in Teilausdrücke zerlegt werden kann.[22]

Schreiben wir nun ein LEDA-Programm, das die Klasse stack benutzt, um arithmetische Ausdrücke auszuwerten, das also obigen Kellerautomaten implementiert.

Den Ausdruck, den wir auswerten wollen, lesen wir von der Standardeingabe. Wir müssen ihn zuerst in seine Tokens zerlegen, d. h. in seine minimalen syntaktischen Einheiten. Das sind in diesem Falle Dezimalzahlen und die einzelnen Operatorenzeichen. (Das Problem des unären Minus übergehen wir.) Um zusätzlich eine saubere Modularisierung vorzuführen, gliedern wir diese Teilaufgabe aus in eine eigene Übersetzungseinheit. Die Header-Datei Tokenizer.h sieht folgendermaßen aus:

Filename: Tokenizer.h
LEDA-Benutzer ab Version 5.0: Beachten Sie, dass die Header-Dateien nun in Module (Unterverzeichnisse) partitioniert sind!
namespace Tokenizer {

enum token_kind { 
  NUMBER, 
  ADD = '+', SUB = '-', MUL = '*', DIV = '/',
  END_OF_INPUT
};

extern token_kind current_token;
extern double current_number;

void get_next_token();

}

Die Funktion get_next_token() liest dabei das jeweils nächste Token aus der Eingabe und hält in der Variablen current_token fest, um welche Art von Token es sich handelt. Wenn es sich dabei um eine NUMBER handelt, so hält die Funktion den Wert dieser Zahl zusätzlich in der Variablen current_number fest.

Unser Hauptprogramm benutzt einen stack<double>, um die in den Ausdrücken auftretenden Zahlen zu speichern. Es ruft immer wieder die Funktion get_next_token() auf. Liefert diese das Token NUMBER, so legt das Programm diese Zahl durch ein

S.push(current_number);

auf den Stapel ab. Bei einem Token, das einen Operator anzeigt, holt das Programm mittels

S.pop();

die beiden obersten Zahlen vom Stapel, verknüpft sie gemäß des Operators, und legt das Ergebnis der arithmetischen Operation wieder auf dem Stapel ab.

Das Token END_OF_INPUT schließlich zeigt an, dass alle Zeichen der Eingabe gelesen wurden; dann sollte auf dem Stapel nur noch eine einzige Zahl liegen, das Ergebnis der Auswertung. Diese Zahl kann mit top() ermittelt werden.:

S.top();

liefert immer das oberste Element des Stapels, ohne dieses vom Stapel zu löschen.

Filename: RPNEvaluator.C
LEDA-Benutzer ab Version 5.0: Beachten Sie, dass die Header-Dateien nun in Module (Unterverzeichnisse) partitioniert sind!
#include <LEDA/stack.h>
#include "Tokenizer.h"
#include <iostream>

using leda::stack;
using namespace Tokenizer;

int main()
{
  
  stack<double> S;
  get_next_token();

  while(current_token != END_OF_INPUT) {
    if(current_token == NUMBER) 
      S.push(current_number);
    else {
      double num1 = S.pop();
      double num2 = S.pop();
      switch(current_token) {
      case ADD:
        S.push(num2 + num1);
        break;
      case SUB:
        S.push(num2 - num1);
        break;
      case MUL:
        S.push(num2 * num1);
        break;
      case DIV:
        S.push(num2 / num1);
        break;
      }
    }
    get_next_token();
  }

  std::cout << S.top() << "\n";
}

Die LEDA-Klasse stack hat eine besonders einfache Schnittstelle. Außer den oben verwendeten Methoden push(), pop() und top() gibt es noch die folgenden Methoden:

S.empty();

testet, ob der Stack leer ist.

S.size();

liefert die Anzahl der Elemente auf dem Stack. Und schließlich löscht

S.clear();

alle Elemente und macht den Stack leer. y

Der Vollständigkeit halber wollen wir noch die Implementierung Tokenizer.C auflisten. Diese bestimmt das nächste Token mit Hilfe der bekannten Stream-Funktionen der C++-Standardbibliothek.

Filename: Tokenizer.C
LEDA-Benutzer ab Version 5.0: Beachten Sie, dass die Header-Dateien nun in Module (Unterverzeichnisse) partitioniert sind!
#include "Tokenizer.h"
#include <iostream>

namespace Tokenizer {

token_kind current_token;
double current_number;

void get_next_token() {
  char c=0;
  std::cin >> c;
  
  switch(c) {

  case 0:
    current_token = END_OF_INPUT;
    return;

  case '+': case '-': case '*': case '/':
    current_token = token_kind(c);
    return;

  case '0':  case '1':  case '2':  case '3':
  case '4':  case '5':  case '6':  case '7':
  case '8':  case '9':
  case '.':
    std::cin.putback(c);
    std::cin >> current_number;
    current_token = NUMBER;
    return;
  }
}

}

Jetzt können wir dem Kellerautomaten unseren ursprünglichen Ausdruck zum Auswerten übergeben:

3 1 2 + 3 * 5 + *
42

Fehlerbehandlung

Was geschieht, wenn wir bei der Eingabe einen Operator vergessen, etwa in obigem Ausdruck die Zahl 5? Dann wird der Kellerautomat irgendwann versuchen, ein Element von einem leeren Stapel zu ziehen! Das ist aber laut Vorbedingung der Operation pop() verboten! Schauen wir einmal, was geschieht:

3 1 2 + 3 * + *
 
LEDA ERROR HANDLER
        slist: pop on empty list.
 
 
Abort

Das Programm bricht mit einer Fehlermeldung des internen LEDA-Error-Handlers ab. Dieser überprüft die Vorbedingungen mancher Operationen, wie wir im Abschnitt “Vorbedingungen (Preconditions)” gesehen haben. Insbesondere überprüft er, ob ein Stack zum Zeitpunkt eines pop() nicht leer ist. (Stacks sind mit Hilfe der Klasse slist implementiert; daher stammt die Fehlermeldung von slist.)

Oftmals ist es sinnvoll, Fehler dieser Art abzufangen und selbst zu behandeln. Hier wäre es z. B. guter Stil, den Benutzer darauf aufmerksam zu machen, dass sein Ausdruck zu wenig Operanden enthält.

Um die Fehlerbehandlung nicht mit der Implementierung des Verfahrens zu vermischen und dadurch den Blick auf das Wesentliche zu verschleiern, wollen wir den Zugriffscode auf den Stack mit einem try-Block umschließen und eventuelle Fehler in einem zugehörigen catch-Block abfangen und behandeln. Das geht folgendermaßen:

Filename: RPNEvaluatorErrorsHandeled.C
LEDA-Benutzer ab Version 5.0: Beachten Sie, dass die Header-Dateien nun in Module (Unterverzeichnisse) partitioniert sind!
#include <LEDA/stack.h>
#include <LEDA/error.h>
#include "Tokenizer.h"
#include <iostream>

using leda::stack;
using leda::set_error_handler;
using leda::leda_exception;

using namespace Tokenizer;

int main()
{
  set_error_handler(leda::exception_error_handler);

  stack<double> S;
  get_next_token();

  while(current_token != END_OF_INPUT) {
    if(current_token == NUMBER) 
      S.push(current_number);
    else 
      try {
        double num1 = S.pop();
        double num2 = S.pop();
	
        switch(current_token) {
        case ADD:
          S.push(num2 + num1);
          break;
        case SUB:
          S.push(num2 - num1);
          break;
        case MUL:
          S.push(num2 * num1);
          break;
        case DIV:
          S.push(num2 / num1);
          break;
        }
      }
      catch(leda_exception e) {
        std::cerr << e.get_msg() << std::endl;
        std::cerr << e.get_num() << std::endl;
        std::cerr << "Too few numbers in expression." << std::endl;
        exit(1);
      }
    get_next_token();	    
  }

  if(S.size() != 1 ) {
    std::cout << "Too few operators in expression." << std::endl;
    exit(1);
  }
  else std::cout << S.pop() << std::endl;
}

Zuerst müssen wir dem LEDA-Error-Handler sagen, dass er beim Auftreten eines Fehlers eine Ausnahme werfen soll, die wir dann abfangen werden. Das geschieht durch die Anweisung

set_error_handler(leda::exception_error_handler);

Die Ausnahme, die LEDA wirft, ist vom Typ leda_exception. Ein Objekt dieses Typs beinhaltet eine der Ausnahme entsprechende Fehlernummer und Fehlermeldung. Auf diese kann durch die Methoden get_num() bzw. get_msg() zugegriffen werden. Dadurch kann, falls ein catch möglicherweise mehrere Ausnahmen an einer Stelle auffangen muss, die Art der Ausnahme festgestellt werden. Das ermöglicht eine der jeweiligen Ausnahme angepasste Behandlung.[23]

Testen wir nun noch einmal obige ungenügende Eingabe:

3 1 2 + 3 * + *
slist: pop on empty list.
1
Too few numbers in expression.

Jetzt erhalten wir also eine genaue Auskunft darüber, was wir falsch gemacht haben.

[Anmerkung]Anmerkung

In der augenblicklichen Version 6.2 von LEDA haben alle Ausnahmen die Fehlernummer 1, die auch bei obiger Ausgabe auftaucht. Dies soll laut den Verantwortlichen aber bald verbessert werden.

Ebenfalls abgefangen haben wir in obigem Programm den Fall, dass unser Ausdruck zu wenig Operatoren enthält. Dies macht sich allerdings nicht durch Werfen einer Ausnahme durch eine Methode der Klasse stack bemerkbar, sondern dadurch, dass am Ende mehr als eine Zahl auf dem Stack liegt. Dies überprüfen wir durch size(). Eine Beispieleingabe für diesen Fall liefert dann folgende Ausgabe:

1 1
Too few operators in expression.

So kann man 1 und 1 also nicht zusammenzählen...

Implementierung und weitere Informationen

Stacks sind durch einfach verkettete lineare Listen implementiert. Alle Operationen benötigen konstante Zeit, außer clear(), das O(n) benötigt, wenn der Stack n Elemente enthält.

Mehr zu Stacks steht auf der entsprechenden Manualseite. Die Möglichkeiten der Fehlerbehandlung in LEDA sind ebenfalls auf einer eigenen Manualseite beschrieben.

Übungen

Übung 15.

Ein vollständig geklammerter arithmetischer Ausdruck ist ein arithmetischer Ausdruck, bei dem jeder Unterausdruck - bestehend aus zwei Operanden und einem Operator - in runde Klammern eingeschlossen ist, wie z. B.

((( 3 + (2 + 5)) * ( 6 + 8 )) - ( 6 * 2 ))

Werten Sie solche vollständig geklammerten arithmetischen Ausdrücke mit einem Programm aus, das zwei Stapel benutzt, einen für Operanden und einen für Operatoren.

Erweitern Sie das Programm dann so, dass es auch unvollständig geklammerte arithmetische Ausdrücke auswerten kann. Genauer gesagt, soll es alle Ausdrücke auswerten können, die nach den folgenden Regeln erzeugt sind:

  1. Ein Ausdruck beginnt mit einem (unären) Plus oder Minus oder keinem von beiden; es folgt ein Term, dem beliebig viele andere Terme folgen (auch keiner), die durch ein Plus oder Minus voneinander abgetrennt sind.

  2. Ein Term ist ein Faktor, dem beliebig viele andere Faktoren folgen (auch keiner), die durch ein Mal oder ein Divisionszeichen voneinander abgetrennt sind.

  3. Ein Faktor ist eine nicht-negative, ganze Zahl oder ein geklammerter Ausdruck.

Mit Hilfe einer kontextfreien Grammatik ausgedrückt lautet die Menge der (unvollständig geklammerten) arithmetischen Ausdrücke wie folgt:

ausdruck ::= ( '+' | '-' )? term (( '+' | '-' ) term)*
term ::= faktor (( '*' | '/' ) faktor)*
faktor ::= ( '0' | '1' |...| '9' )+ |  ( ausdruck )

Dabei sollen die üblichen Präzedenzregeln („Punktrechnung geht vor Strichrechnung“) befolgt werden. Es soll also bei dem Ausdruck

( 3 + 2 + 5 ) * ( 6 + 8 ) - 6 * 2

derselbe Wert ausgegeben werden wie beim vorherigen, vollständig geklammerten Ausdruck.



[21] Die tiefere Bedeutung des Ausdruckswertes 42 für die Informatik ist in [5] beschrieben.

[22] Um genauer zu sein, muss man intuitiv eine Form von Rekursion beherrschen, um den ursprünglichen Infix-Ausdruck in Postfix-Notation zu bringen. Das kann man üben. So haben z. B. in den 70er Jahren Apollo-Astronauten kritische Kurskorrektur-Manöver mit ihrem HP 65 berechnet.

[23] Hier muss zugegeben werden, dass dieses Ausnahmeschema nicht so hierarchisiert ist, wie wir das etwa von einer großen GUI-Bibliothek gewohnt sind. Das liegt daran, dass Ausnahmebehandlung in Programmen, die hauptsächlich kombinatorische Algorithmen implementieren, bei Weitem keine so große Rolle spielen wie in Programmen mit aufwändiger Benutzerinteraktion.




Imprint-Dataprotection