/*
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 '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;
	}
}