/*
Klasse:   MParse <BR>
Funktion: Parst einen String, der einen mathematischen Ausdruck in Infix-
          Notation enthält, und erstellt daraus eine Baumstruktur von
          Klassen, die den Operatoren und Operanden entsprechen. <BR>
Sprache:  JAVA <BR>
Autor:    Martin Klossek, Martin Meedt und Fabian Wleklinski <BR>*/
 
/**
Der mathematische Ausdruck, der geparst werden soll, muß der folgenden
Grammatik entsprechen: <BR>
<BR>
Start::=Ausdruck <BR>
Ausdruck::=Term {(Plus | Minus) Term}<BR>
Term::=Faktor {(Mal | Durch) Faktor}<BR>
Faktor::=Variable | NumKonstante | KlammerAuf Ausdruck KlammerZu | Funktion<BR>
Funktion::=Wort KlammerAuf Ausdruck KlammerZu
Variable::=Wort <BR>
NumKonstante::=[Minus] Ziffer {Ziffer} [Komma Ziffer {Ziffer}] <BR>
Ziffer::='0'|'1'|'2'|...|'9'<BR>
Buchstabe::='a'|'b'|...|'z'|'A'|'B'|...|'Z' <BR>
Wort::=Buchstabe {Buchstabe} <BR>
Komma::=',' <BR>
KlammerAuf::='(' <BR>
KlammerZu::=')' <BR>
Plus::='+' <BR>
Minus::='-' <BR>
Durch::='/' <BR>
Mal::='*' <BR>
*/
public class MParse {
  /** Erzeugt eine Instanz. Keine Parameter. */
  public MParse() {
    // instanzieren
    String src = new String();
  }

  /** Wertet den Ausdruck aus, und ersetzt dabei alle Vorkommen der Variable "X" durch den in Parameter "X"
  übergebenen Wert. Enthält der Ausdruck außer "X" auch andere Variablen, wird eine Exception geworfen. Enthält
  der Ausdruck undefinierte Funktionen, wird eine Exception geworfen. Der Wert der Auswertung wird zurückgegeben.
  @param X Der Wert für die Variable "X", an dem der Ausdruck ausgewertet werden soll.
  */
  public double evaluate( double x ) {
    return result.evaluate( x );
  }

  // Hält die Anzahl der Elemente, die in der Liste abgelegt wurden
  int nElements = 0;

  // Ist solange TRUE, wie der Ausdruck noch vereinfacht werden kann
  boolean geaendert = true;

  // Wir benötigen eine Liste, in der wir die erzeugten Klassen einfügen. Eigentlich
  // müsste die Liste dynamisch wachsen, aber ich begnüge mich mal mit einer
  // vernünftigen Länge von 2048 Einträgen
  Symbol[] tmpList;

  /** Bearbeitet den übergebenen String und versucht, den mathematischen Ausdruck durch
  eine interne Struktur zu repräsentieren. Werden eine ungültige Grammatik, oder nicht
  bekannte Zeichen verwendet, wird eine Exception geworfen. */
  public void parse( String src ) {
    this.src = src;

    /* Schritt 1 (Erkennung von Terminalsymbolen):
    - Der zu bearbeitende String muß in Infix-Notation mit der oben angegebenen 
    Grammatik angegeben sein. Diese Funktion wird den String Stück für Stück, 
    von vorne nach hinten durcharbeiten, und für jedes erkannte Terminalsymbol
    (Ziffern, Buchstaben, Operator, etc) ein Objekt von der zugehörigen Klasse
    instanziieren, un in einer Liste ablegen. Wenn ein Element nicht erkannt 
    werden kann, wird ein Fehler gemeldet. 
    - Diese Funktion wird auf den gesamten String angewendet
    
    Schritt 2 (Zusammenfassen von Ziffern zu NumKonstanten und Faktoren):
    - In diesem Schritt werden alle Kombinationen von Ziffern und Komma gemäß der 
    Übergangsregel NumKonstante::=[Minus] Ziffer {Ziffer} [',' {Ziffer}]
    ausgewertet. Da NumKonstanten zwangsläufig in Faktoren übergehen, ist
    dieser Übersetzungsschritt integriert, und die NumKonstanten werden gleich
    als Faktoren gespeichert.
    - Diese Funktion wird auf den gesamten Strinmg angewendet

    Schritt 3 (Zusammenfassen von Buchstaben zu Wörtern)
    in diesem Schritt werden alle Koombinationen von Buchstaben zu Wörtern 
    zusammengefasst.
    - Diese Funktion wird auf den gesamten Strinmg angewendet
    
    Schritt 4 (Anwendung der Grammatik und Erzeugung eines Baums):
    - Dieser Vorgang bearbeitet die entstandene Struktur, und versucht, durch die
    oben angegebene Grammatik beschriebene Konstellationen zu finden, z.B.
    "Faktor * Faktor". Wird eine solche Konstellation gefunden, wird eine neue
    Klasse vom Typ des übergeordneten Elementes, in diesem Beispiel "Term" 
    instanziiert. Diese wird die alte Konstellation ersetzen.
    - Diese Funktion wird nur auf Teilstrings angewendet, und zwar immer nur auf
    den Inhalt einer "Klammer", wobei innere Klammern vor äußeren Klammern 
    abgearbeitet werden.
    */

    /* Schritt 1 (Erkennung von Terminalsymbolen): */

    // Hält das aktuelle Zeichen des Strings, das bearbeitet wird
    char curChar;

    // Hält das neu erzeugte Symbol
    Symbol s;

    // Hiermit indizieren wir in der Liste
    int listIndex = 0;

    // FALSE, wenn das aktuelle Zeichen unbekannt ist
    boolean erkannt;

    // Wir benötigen eine Liste, in der wir die erzeugten Klassen einfügen. Eigentlich
    // müsste die Liste dynamisch wachsen, aber ich begnüge mich mal mit einer
    // vernünftigen Länge von 2048 Einträgen
    tmpList = new Symbol[2048];

    // Alle Zeichen des String abarbeiten
    // ToDi: Die Schleife muß abgebrochen werden, wenn ein Fehler unterlaufen ist
    for (int i=0; i < src.length(); i++) {

      // Jetzt nach Terminalsymbolen suchen

      // das aktuelle Zeichen holen
      curChar = src.charAt( i );

      // davon ausgehen, daß das Zeichen unbekannt ist
      erkannt = false;

      // Eine Instanz für das neue Symbol erzeugen
      s = null;

      // Mit den erlaubten Terminalsymbolen vergleichen

      // Leerzeichen (lassen wir unter den Tisch fallen)
      if (curChar == ' ') { erkannt = true; };     

      // Buchstaben 
      if ( (((byte) curChar >= (byte) 'a') && ((byte) curChar <= (byte) 'z')) || 
           (((byte) curChar >= (byte) 'A') && ((byte) curChar <= (byte) 'Z')) ) {
        erkannt = true;
        s = new Buchstabe();
        ((Buchstabe) s).value = curChar;
      }

      // Ziffern
      if (((byte) curChar >= (byte) '0') && ((byte) curChar <= (byte) '9')) {
        erkannt = true;
        s = new Ziffer();
        ((Ziffer) s).value = (((byte) curChar) - (byte) '0');
      }

      // Operatoren
      if (curChar == '+') { erkannt = true; s = new Plus(); }
      if (curChar == '-') { erkannt = true; s = new Minus(); }
      if (curChar == '*') { erkannt = true; s = new Mal(); }
      if (curChar == '/') { erkannt = true; s = new Durch(); }
      // Klammern
      if (curChar == '(') { erkannt = true; s = new KlammerAuf(); }
      if (curChar == ')') { erkannt = true; s = new KlammerZu(); }
      // Komma
      if (curChar == ',') { erkannt = true; s = new Komma(); }

      // Wenn ein Symbol erzeugt wurde, das Symbol in der Liste speichern
      if (s != null) { 
        tmpList[ listIndex ] = s; 
        listIndex++; 
        nElements++;
      }

      // Wenn ein unbekanntes Zeichen gefunden wurde -> Fehler
      if (! erkannt) {
        // Fehler melden
        throw new MParseException( "Das folgende Zeichen wurde nicht erkannt: '" + curChar + "'. Bitte korrigieren Sie die Eingabe." );
      }

    } // Letztes Element der Liste erreicht


    // Schritt 2 (Zusammenfassen von Ziffern zu NumKonstanten):

    // Von dem ersten bis zu dem letzten Element durchlaufen
    for (int i=0; i<nElements; i++ ) {

      // Handelt es sich bei dem aktuellen Element um eine Ziffer?
      if (tmpList[ i ] instanceof Ziffer) {

        // Eine zweite Schleife durchlaufen, solange, bis keine Ziffer mehr gefunden wird
        int j=i;
        int d=1;
        double value = 0;
        boolean done = false;
        boolean komma = false;
        while (! done) {

          if (tmpList[ j ] instanceof Ziffer) {
            if (! komma) {
              value = value * 10 + ((Ziffer) tmpList[j]).value;
            } else {
              value = value + ((double) ((Ziffer) tmpList[j]).value) / d;
            }
          }

          if ((! (tmpList[ j ] instanceof Ziffer)) && (! (tmpList[ j ] instanceof Komma))) { done = true; }
          if (tmpList[ j ] instanceof Komma) { 
            if (! komma) { komma = true; } else { done = true; }
          }

          if (komma) { d = d * 10; }
          
          if (! done) { j++; }

          if (j == nElements) { done = true; }
        }

        // Index "i" ("j-1") zeigt jetzt auf die erste (letzte) Ziffer

        // Einen Faktor erzeugen
        Faktor faktor = new Faktor();
        // Eine NumKonstante erzeugen
        NumKonstante numKonstante = new NumKonstante();
        // Den Wert der NumKonstanten setzen
        numKonstante.value = value;
        // Die NumKonstante an den Faktor dranhängen
        faktor.v = numKonstante;
        // Den Faktor in die Liste einfügen
        tmpList[i] = faktor;

        // Die nachfolgenden Elemente verschieben
        for (int k=i+1; k<nElements; k++) {
          tmpList[k] = tmpList [k+(j-i-1)];
        }
        nElements = nElements - (j-i-1);

        i = -1;

      } // Ende (es handelt es sich um eine Ziffer)
       
    } // Letztes Element der Kette bearbeitet

    // Schritt 3 (Zusammenfassen von Buchstaben zu Wörtern)

    // Jetzt alle Buchstaben zu Wörtern zusammenfassen
    // Von dem ersten bis zu dem letzten Element durchlaufen
    for (int i=0; i<nElements; i++ ) {

      String str = "";

      // Handelt es sich bei dem aktuellen Element um einen Buchstaben?
      if (tmpList[ i ] instanceof Buchstabe) {

        // Eine zweite Schleife durchlaufen, solange, bis kein Buchstabe mehr gefunden wird
        int j=i;
        boolean done = false;
        boolean komma = false;
        while (! done) {
          if (tmpList[ j ] instanceof Buchstabe) {
            str = str + ((Buchstabe) tmpList[ j ]).value + "";
          } else {
            done = true;
          }
          if (! done) { j++; }

          if (j == nElements) { done = true; }
        }
        // Index "i" ("j-1") zeigt jetzt auf den ersten (letzten) Buchstaben
        // Eine NumKonstante mit diesem Wert erzeugen
        tmpList[i] = new Wort();
        ((Wort) tmpList[i]).value = str;

        // Die anderen Elemente löschen
        for (int k=i+1; k<nElements; k++) {
          tmpList[k] = tmpList [k+(j-i-1)];
        }
        nElements = nElements - (j-i-1);
      }
    } // Letztes Element der liste bearbeitet

    // Schritt 4 (Anwendung der Grammatik und Erzeugung eines Baums):

    // Dieser Schritt beinhaltet eine Rekursion, deswegen ist er in einer seperaten Methode ausgelagert

    // doGrammatik erwartet den Index des ersten und des letzten Elementes, daß es bearbeiten soll
    doGrammatik( 0, nElements-1 );

    if (tmpList[ 0 ] instanceof Ausdruck) {
      result = (Ausdruck) tmpList[ 0 ];
    } else {
      result = null;
    }


  }


  /* wendet die Grammatik auf einen Teil der Liste an; der Index des ersten und des letzten zu
  bearbeitenden Elementes muß übergeben werden */
  private int doGrammatik( int start, int end ) {

    /* Bevor wir diesen teil irgendwie verändern können dürfen, müssen wir alle inneren
    Klammern bearbeiten. Deswegen testen wir, ob eine innere Klammer existiert. Dazu suchen
    wir nach einer schließenden Klammer, und sobald wir eine gefunden haben, suchen wir die
    vorhergehende öffnende Klammer. Die Indizes dieser beiden Elemente merken wir uns, und
    rufen die Methode rekursiv mit diesen beiden Indizes auf, um die innere Klammer aufzulösen. */

    // Alle Elemente in dem angegebenen Bereich anschauen


    int endMoved = 0;


  weiter_1:
    for (int endPos=start; endPos <= end; endPos++) {
      // Ist es eine schließende Klammer?
      if (tmpList[ endPos ] instanceof KlammerZu) {
        // ... ja -> in der Elementliste zurücklaufen und eine öffnende Klammer suchen
        for (int startPos=endPos; startPos >= start; startPos--) {
          // Ist es eine öffnende Klammer?
          if (tmpList[ startPos ] instanceof KlammerAuf) {
            // ... ja -> die Methode rekursiv aufrufen
            int tmp = doGrammatik( startPos+1, endPos-1 );
            end = end - tmp;
            endMoved = endMoved + tmp;
            // Es reicht ja, wenn wir EINE öffnende Klammer gefunden haben!
            endPos = start-1;
            break;
          } // öffnende Klammer gefunden
        } // öffnende Klammer suchen
      } // schließende Klammer gefunden
    } // schließende Klammer suchen

    /* Wir können an dieser Stelle davon ausgehen, daß in dem zu bearbeitenden Bereich keine
    Klammern mehr existieren. (Wenn wir das erste mal hier angelangt sind, befinden wir uns
    ja auch in einer der innersten Klammern) */

    /* Jetzt alle Wörter in dem zu bearbeitenden Bereich zuerst in Variablen, und dann in Faktoren
    umwandeln. Dieser Schritt ist legal, weil es sich bei den Wörtern nicht um Funktionen handeln
    kann, denn Funktionen beinhalten ja Klammerung, und dann hätten wir sie ja schon längst in einen Faktor
    umgewandelt. */

    for (int i=start; i <= end; i++) {
      if (tmpList[ i ] instanceof Wort) {
        Variable v = new Variable();
        v.value = ((Wort) tmpList[ i ]).value;
        Faktor f = new Faktor();
        f.v = v;
        tmpList[ i ] = f;
      }
    }

    /* Die folgenden Operationen werden die Länge der Struktur verändern, daher ist es wichtig, nach
    der Anwendung einer Operation die folgenden Elemente in der Liste nach vorne zu ziehen. Diese
    Variable hält die Anzahl der Elemente, die ersetzt werden: */
    int replaced;
    

    /* Jetzt alle Ketten der Form "Faktor" {('*'|'/') "Faktor" } durch "Term" ersetzen */

    // Das erste zu bearbeitende Zeichen sitzt direkt nach der Klammer
    int pos = start;
    // Alle Zeichen bis direkt vor der schließenden Klammer durchlaufen
    while (pos <= end) {
      // Hält die Anzahl der Elemente, die gelöscht werden müssen
      replaced = 0;

      // Eine Produktkette beginnt mit [Faktor] 
      if (tmpList[pos] instanceof Faktor) {

        // Wir haben eine Produktkette gefunden -> einen Term erzeugen
        Term term = new Term();
        // Für den ersten Faktor in dieser Kette ein Symbol erzeugen
        TermItem termItem = new TermItem();
        termItem.item = tmpList[pos]; 
        replaced++;
        term.items.add( termItem );

        // Jetzt eine Schleife starten, die so lange läuft, bis alle Faktoren abgearbeitet sind
        int pos2 = pos+1;
        // Alle Zeichen bis direkt vor der schließenden Klammer durchlaufen
      Schleife_1:
        while (pos2 <= end) {
          // Ausschließen, daß wir über das Ende der Klammer hinweg operieren
          if (pos2+1 <= end) {
            // Zur Fortsetzung der Produktkette akzeptiern wir nur ('*'|'/') [Faktor]
            if (((tmpList[pos2] instanceof Mal) || (tmpList[pos2] instanceof Durch)) && (tmpList[pos2+1] instanceof Faktor)) {

              // Für den neuen Faktor ein Symbol erzeugen
              termItem = new TermItem();
              termItem.item = tmpList[pos2+1];
              term.items.add( termItem );

              // Im Falle einer Division ...
              if (tmpList[pos2] instanceof Durch) {
                termItem.isNeg = true;
              }

              replaced = replaced+2;
            } else {
              break Schleife_1;
            }
          }
          pos2=pos2+2;
        }

        // Das Element in die Liste einsetzen
        tmpList[ pos ] = term;


        // In "replaced" steht jetzt die Anzahl der Elemente, aus denen der Term besteht. Diese Elemente sind
        // überflüssig, weil ja ein Term eingefügt wurde, der sie ersetzt. "replaced-1" ist daher die Anzahl
        // der Elemente, um die die nachfolgenden Elemente verschoben werden müssen.
        if (replaced > 1) {
          for (pos2=pos+1; pos2+(replaced-1) < nElements; pos2++) {
            tmpList[ pos2 ] = tmpList[ pos2 + (replaced-1) ];
          }
        }
        end = end - (replaced-1);
        nElements = nElements - (replaced - 1);
        pos = start-1;
        endMoved = endMoved + (replaced - 1);
      }


      pos++;
    }

    // Jetzt Termketten durch Ausdrücke ersetzen. 
    // Ausdruck ::= Term {('+'|'-') Term }

    // Das erste zu bearbeitende Zeichen sitzt direkt nach der Klammer
    pos = start;
    // Alle Zeichen bis direkt vor der schließenden Klammer durchlaufen
    while (pos <= end) {

      // Hält die Anzahl der Elemente, die gelöscht werden müssen
      replaced = 0;

      // Eine Kette beginnt mit [Term] || [Plus][Term] || [Minus][Term]
      if ( (tmpList[pos] instanceof Term) || ((tmpList[pos] instanceof Plus) && (tmpList[pos+1] instanceof Term)) || ((tmpList[pos] instanceof Minus) && (tmpList[pos+1] instanceof Term)) ) {

        boolean minus = (tmpList[pos] instanceof Minus);
        boolean hatVorzeichen = ! (tmpList[pos] instanceof Term);

        // Wir haben eine Termkette gefunden -> einen Ausdruck erzeugen
        Ausdruck ausdruck = new Ausdruck();
        
        // Für den ersten Summanden in dieser Kette ein Symbol erzeugen
        Term term;
        if (hatVorzeichen) {
          term = (Term) tmpList[ pos+1 ];
          if (minus) { term.isNeg = ! term.isNeg; }
          replaced++;
        } else {
          term = (Term) tmpList[ pos ];
        }
        ausdruck.items.add( term );
        replaced++;

        // Jetzt eine Schleife starten, die so lange läuft, bis alle Terme abgearbeitet sind
        int pos2 = pos+1;
        if (hatVorzeichen) { pos2++; }
        // Alle Zeichen bis direkt vor der schließenden Klammer durchlaufen
      Schleife_2:
        while (pos2 <= end) {
          // Ausschließen, daß wir über das Ende der Klammer hinweg operieren
          if (pos2+1 <= end) {
            // Zur Fortsetzung der Termkette akzeptiern wir nur ('+'|'-') [Term]
            if (((tmpList[pos2] instanceof Plus) || (tmpList[pos2] instanceof Minus)) && (tmpList[pos2+1] instanceof Term)) {

              // Für den neuen Ausdruck ein Symbol erzeugen
              term = (Term) tmpList[pos2+1];
              if (tmpList[pos2] instanceof Minus) { term.isNeg = ! term.isNeg; }
              ausdruck.items.add( term );

              replaced++;
              replaced++;
            } else {
              break Schleife_2;
            }
          }
          pos2=pos2+2;
        }

        // Das Element in die Liste einsetzen
        tmpList[ pos ] = ausdruck;

        // In "replaced" steht jetzt die Anzahl der Elemente, aus denen der Term besteht. Diese Elemente sind
        // überflüssig, weil ja ein Term eingefügt wurde, der sie ersetzt. "replaced-1" ist daher die Anzahl
        // der Elemente, um die die nachfolgenden Elemente verschoben werden müssen.
        if (replaced > 1) {
          for (pos2=pos+1; pos2+(replaced-1) < nElements; pos2++) {
            tmpList[ pos2 ] = tmpList[ pos2 + (replaced-1) ];
          }
        }
        end = end - (replaced-1);
        nElements = nElements - (replaced - 1);
        pos = start-1;
        endMoved = endMoved + (replaced - 1);
      }


    pos++;
    }

    /* An dieser Stelle sollte der Inhalt der bearbeiteten Klammer zu "KlammerAuf" "Ausdruck" "KlammerZu" 
    bearbeitet sein. Ist dies nicht der Fall, war die Grammatik des Klammerinhaltes fehlerhaft, und ein
    Fehler muß gemeldet werden. */

    if (start > 0) {
      if ((!(tmpList[start-1] instanceof KlammerAuf)) || (!(tmpList[start] instanceof Ausdruck)) || (!(tmpList[start+1] instanceof KlammerZu))) {
        // Fehler melden
        throw new MParseException( "Der eingegebene Ausdruck verwendet eine ungültige Grammatik. Bitte korrigieren Sie die Eingabe." );
      }
    } else {
      if ((!(tmpList[start] instanceof Ausdruck)) || (nElements > 1)) {
        // Fehler melden
        throw new MParseException( "Der eingegebene Ausdruck verwendet eine ungültige Grammatik. Bitte korrigieren Sie die Eingabe." );
      }
    }

    // Wenn das Vereinfachungs-Ziel erreicht ist -> exit
    if (nElements == 1) {
      return endMoved;
    }

    /* Wenn wir hier angelangt sind, konnte die innere Klammer tatsächlich zu "KlammerAuf" "Ausdruck" "KlammerZu"
    aufgelöst werden. Aus dieser Konstruktion erzeugen wir jetzt einen Faktor (laut Grammatik). Falls vor der
    öffnenden Klammer ein Wort steht, so handelt es sich eindeutig um eine Funktion. In diesem Fall erzeugen wir
    zwar auch einen Faktor, aber einen, der die Funktion beinhaltet. */

    // Hält die Position in der Liste, an die der Faktor geschrieben werden muß
    int faktorPos = start;
    if (start > 0) { faktorPos--; }
    // Hält die Anzahl der Elemente, um die die nachfolgenden Elemente verschoben werden müssen
    int moveCount = 2;
 
    // "istFunktion" setzen, wenn es sich um eine Funktion handelt
    boolean istFunktion = false;
    if (start > 1) {
      if (tmpList[start-2] instanceof Wort) { 
        istFunktion = true; 
        faktorPos--; moveCount++; 
      }
    }

    // Einen Faktor erzeugen
    Faktor faktor = new Faktor();

    // Wenn es sich um eine Funktion handelt -> Funktion erzeugen und dem Faktor eingliedern
    if (istFunktion) {
      Funktion funktion = new Funktion();
      funktion.ausdruck = (Ausdruck) tmpList[start];
      funktion.name = ((Wort) tmpList[start-2]).value;
      faktor.v = funktion;
    } else {
      faktor.v = (Ausdruck) tmpList[start];
    }

    // Den Faktor in die Liste aufnehmen
    tmpList[faktorPos] = faktor;

    // Die nachfolgenden Elemente verschieben
    for (int k=faktorPos+1; k<nElements; k++) { 
      tmpList[k] = tmpList[k+moveCount]; 
    }
    nElements = nElements - moveCount;

    return moveCount + endMoved;
  }

  // Schreibt die Struktur der Liste auf die Standardausgabe, dient zu Debug-Zwecken
  private void zeigeListe( ) {
    System.out.println("");
    System.out.println("Grammatik zum momentanen Zeitpunkt der Auswertung:");
    System.out.println("--------------------------------------------------");
    System.out.println("");
    for (int x=0; x < nElements; x++) {
      if ( tmpList[ x ] != null) {
        System.out.println(tmpList[ x ].getClass().getName());
      } else {
        System.out.println("Null");
      }
    }
    System.out.println( );
  }

  /** Das oberste Element der Struktur, die den mathematischen Ausdruck beinhaltet. */
  public Symbol result;

  // Hält den zu parsenden String, wie mit 'setSrc' festgelegt
  private String src;
}

/* Die Klasse 'Symbol' ist die abstrakte Basisklasse für alle Terminalsymbole und für
alle nicht-Terminalsymbole, d.h. für alle Bestandteile des Termes. */
abstract class Symbol {
  // Gibt seinen Wert zurück. Falls unbekannte Funktionen enthalten sind, oder undefinierte
  // Variablen, so wird ein Fehler gemeldet.
  public double evaluate( double x ) {
    return 0;
  }

  /* Schreibt den Wert bzw. die Struktur auf die Standardausgabe. Der übergebene Wert
  'indent' bezeichnet den Einzug. */
  public void dump( int indent ) {
    // Den Einzug schreiben
    for (int i=1; i <= indent; i++) {
      System.out.print( " " );
    }
    // Den Wert schreiben
    System.out.print( this.getClass().getName() );
    // rekursiv für alle untergeordneten Elemente aufrufen

    // Die Zeile abschließen
    System.out.println();
  }
}

/* Jeder Bestandteil der Grammatik wird durch eine eigene Klasse symbolisiert.
Die Deklaration dieser Klassen folgt jetzt. */

class Ausdruck extends Symbol {
  // Wertet das Element (an der Stelle "X"==X) aus, und liefert den Wert zurück
  public double evaluate( double x ) {
    double result = 0;
    for (int termI=1; termI <= items.count; termI++) {
      result = result + ((Term) items.get(termI-1)).evaluate( x );
    }
    return result;
  }

  public Ausdruck() {
    items = new SimpleList();
  }
  SimpleList items;
}


class Komma extends Symbol {
}

class KlammerAuf extends Symbol {
}

class KlammerZu extends Symbol {
}

class Plus extends Symbol {
}

class Minus extends Symbol {
}

class Mal extends Symbol {
}

class Durch extends Symbol {
}

class TermItem {
  boolean isNeg;
  Symbol item;
}

class Term extends Symbol {
  public Term() {
    items = new SimpleList();
    isNeg = false;
  }
  boolean isNeg;
  // Wertet das Element (an der Stelle "X"==X) aus, und liefert den Wert zurück
  public double evaluate( double x ) {
    double result = 1;
    for (int faktorI=1; faktorI <= items.count; faktorI++) {
      TermItem termItem = (TermItem) items.get(faktorI-1);
      if (termItem.isNeg) {
        result = result / termItem.item.evaluate( x );
      } else {
        result = result * termItem.item.evaluate( x );
      }
    }
    if (isNeg) { result = -result; }
    return result;
  }
  SimpleList items;
}

class Faktor extends Symbol {
  Symbol v;
  // Wertet das Element (an der Stelle "X"==X) aus, und liefert den Wert zurück
  public double evaluate( double x ) {
    double result = v.evaluate( x );
    return result;
  }
}

class Buchstabe extends Symbol {
  // Definiert als: 'a'|'b'|...|'z'|'A'|'B'|...|'Z'
  // Hält den Wert
  public char value;
}

class Wort extends Symbol {
  public String value;
}

class Funktion extends Symbol {
  public String name;
  public Ausdruck ausdruck;

  public double evaluate( double x ) {
    // TRUE wenn die Funktion definiert ist
    boolean erkannt = false;

    // Hält den Rückgabewert
    double result = 0;

    if (name.equalsIgnoreCase("sin")) {
      erkannt = true;
      result = Math.sin( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("asin")) {
      erkannt = true;
      result = Math.asin( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("acos")) {
      erkannt = true;
      result = Math.acos( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("abs")) {
      erkannt = true;
      result = Math.abs( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("sig")) {
      erkannt = true;
      result = ausdruck.evaluate( x ) / Math.abs( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("atan")) {
      erkannt = true;
      result = Math.atan( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("cos")) {
      erkannt = true;
      result = Math.cos( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("tan")) {
      erkannt = true;
      result = Math.tan( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("round")) {
      erkannt = true;
      long res = Math.round( ausdruck.evaluate( x ) );
      result = (double) res;
    }
    if (name.equalsIgnoreCase("sqrt")) {
      erkannt = true;
      result = Math.sqrt( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("sqr")) {
      erkannt = true;
      result = ausdruck.evaluate( x ) * ausdruck.evaluate( x );
    }
    if (name.equalsIgnoreCase("exp")) {
      erkannt = true;
      result = Math.exp( ausdruck.evaluate( x ) );
    }
    if (name.equalsIgnoreCase("log")) {
      erkannt = true;
      result = Math.log( ausdruck.evaluate( x ) );
    }

    if (! erkannt) {
      // Fehler melden
      throw new MParseException( "Die Funktion '" + name + "()' ist nicht definiert. " );
    }

    return result;
  }
}

class Variable extends Symbol {
  public String value;

  public double evaluate( double x ) {
    // Hält den Rückgabewert
    double result = 0;
    boolean erkannt = false;

    if (value.equalsIgnoreCase("x")) {
      erkannt = true;
      result = x;
    };
    if (value.equalsIgnoreCase("pi")) {
      erkannt = true;
      result = Math.PI;
    };
    if (value.equalsIgnoreCase("e")) {
      erkannt = true;
      result = Math.exp(1);
    };
    if (value.equalsIgnoreCase("Random")) {
      erkannt = true;
      result = Math.random();
    };

    if (! erkannt) {
      // Fehler melden
      throw new MParseException( "Die Variable '" + value + "' ist nicht definiert. " );
    }
    return result;
  }
}

// Hält das Grammatik-Element 'NumKonstante'
class NumKonstante extends Symbol {
  // Definiert als: ['-']Ziffer{Ziffer}['.'{Ziffer}]

  // Hält den Wert
  public double value;
  // Wertet das Element (an der Stelle "X"==X) aus, und liefert den Wert zurück
  public double evaluate( double x ) {
    return value;
  }
}


// Hält das Grammatik-Element 'Fname'
class Fname extends Symbol {
  // Definiert als: 'sin'|'cos'|'tan'|'sqrt'|'exp'|'log'
  // Hält den Bezeichner der Funktion (z.B. "sin")
  public String value;
}

// Hält das Grammatik-Element 'Ziffer'
class Ziffer extends Symbol {
  // Hält den Wert der Ziffer
  public int value;
}

/* Enthält eine ganz einfache Liste */
class SimpleList {
  public SimpleList() {
    // Feste Größe, längere Terme / Ausdrücke kommen nicht vor
    items = new Object[ 64 ];
    count = 0;
  }

  public void add( Object item ) {
    items[ count++ ] = item;
  }

  public Object get( int index ) {
    return items[ index ];
  }

  public int count;

  Object[] items;
}

/* Enthält eine Exception, die ausgelöst wird, wenn beim Parsen oder beim Auswerten ein 
Fehler auftritt. Dies kann eine ungültige Grammatik, eine nicht definierte Variable, oder
eine nicht definierte Funktion sein. */
class MParseException extends RuntimeException {
  // Der Text, der den Fehler beschreibt 
  public String msg;
  // Erzeugt eine neue Instanz 
  public MParseException (String msg) {
    super();
    this.msg = msg;
  }
}