Modellierung - Mathematischer Term

[Naryxus]

Hallo,

ich bastel seit geraumer Zeit an einem Taschenrechner rum.

Ich bin jetzt an dem Punkt angekommen, an dem mein Rechner einen String bekommen soll und diesen Parsen und - sofern alles korrekt ist - als mathematischen Term interpretieren soll.
Dafür wollte ich eine Klasse MathTerm erstellen, wobei ich bei dem Design noch unschlüssig bin.

Im Prinzip ist ein mathematischer Term eigentlich eine Liste von mathematischen Begriffen (Operatoren, Elemente der Grundmenge und Variablennamen). Deshalb wäre meine intuitive Wahl in Richtung einer LinkedList gegangen. Hier bin ich mir aber auch noch nicht im Klaren, ob meine Klasse MathTerm dann eine Unterklasse von LinkedList darstellt, oder ob MathTerm ein LinkedList-Attribut besitzen soll.
Da ich sowohl beim Parsen, als auch beim Evaluieren mich ziemlich viel in der Datenstruktur bewegen muss, wäre meine Wahl eigentlich eher auf das Erweitern der Klasse LinkedList gegangen.

Vorhin ist mir gerade noch der Gedanke gekommen, dass ein Term nun auch verschachtelt sein kann und im Prinzip die innersten Ausdrücke dann zuerst ausgeführt werden sollten. Dafür wäre dann eigentlich eine Baumstruktur geeignet, um das möglichst effizient abzuhandeln.

Ich würde gerne eure Meinung darüber hören, was ihr denkt, was Sinn macht und wo ich daneben liege.

Vielen Dank schon mal und liebe Grüße,
Naryxus

 

[rme]

Hallo

In Java ist Erweiterung durch Komposition (die Variante, bei der du die Liste als Instanzvariable) in fast allen Fälle der Erweiterung durch Vererbung vorzuziehen, da Java keine Mehrfachvererbung kennt. Wenn du von der Liste ableiten würdest, könntest du darüber keine eigene Oberklasse mehr haben.

Außerdem wirst du zum Parsen und Auswerten noch andere Datenstrukturen benötigen, wenn das Ganze effizient sein soll. Einen Baum zum Speichern des Ausdrucksbaums, einen Stack zum eigentlichen Auswerten (falls du es ohne rekursiven Abstieg machen möchtest) usw. Die Liste brauchst du eigentlich nur im ersten Schritt.

 

[Naryxus]

Vielen Dank für die schnelle Antwort!

Würde das dann nicht sehr redundant sein alles?
Wenn ich deinen Vorschlag richtig verstehe, hätte ich eine Klasse MathTerm mit mindestens zwei Instanzvariablen:
Der Ausdruck dargestellt durch eine LinkedList und
der Ausdruck gespeichert durch einen Baum

Ist es eigentlich speichertechnisch sinnvoll den Term als Baum zu speichern? Ich meine für das Parsen ganz klar sinnvoll, um einen Syntaxbaum zu durchlaufen etc. Oder anders gefragt: Ist es sinnvoll überhaupt den Schritt über die Liste zu gehen?

Und noch eine Stufe weiter höher: Rechtfertigt der Zweck wirklich den Aufwand das Frontend eines "Compilers" abzubilden?
Ich meine, ich würde gern ein möglichst effizientes Programm schreiben, aber arbeiten andere Rechner auch mit solchem Aufwand, um einen Term auszurechnen?


Grüße

 

[rme]

Das kommt ganz darauf an, wie die Eingabe ist. "Normalerweise" bekommen solche Parser einen String - da du stattdessen eine Liste nehmen wolltest, dachte ich, dass du sowas wie eine lexikographische Analyse gemacht hast und deshalb eine Liste wie "Zahl<3>, Mal, KlammerAuf, Zahl<4>, Plus, Var<x>, KlammerZu" meintest. Falls das so gemeint war, kannst du die Redundanz vermeiden, indem du das direkt in einen Baum parst, sobald du den Parameter in irgendeiner Methode bekommt - danach brauchst du die Liste nicht mehr, weil die Information im Baum ja auch enthalten ist.

Ob der Aufwand gerechtfertig ist, kommt auf dein Ziel an. Wenn du nur einfache Terme und vielleicht Klammern benötigst, reicht ein rekursiver Abstieg und du brauchst gar keinen Baum. Aber wenn Funktionen (keine eigenen, sondern sowas wie sin und cos) und Variablen dazukommen, wäre das mit einem Baum auch einfach eleganter, finde ich.

Nachtrag: Falls du mit "Rechner" sowas meinst, wo man grafisch Buttons anklickt und dadurch den Term zusammensetzt, würde ich glaube ich einen Zustandsautomaten und einen Stack verwenden.

 

[Naryxus]

Ich sehe schon. Die Ineffizienz hat in meinen Überlegungen gesteckt!

Ich hätte quasi den unnötigen Schritt gemacht den übergebenen String in einer Token-Liste abzuspeichern und aus dieser dann einen Syntaxbaum gebastelt.

Diesen Schritt kann ich mir ja dann im Prinzip sparen und während dem Parsen direkt in eine Baumstruktur speichern.
Macht es dann Sinn für das Parsen eine eigene Methode zu schreiben, die ich im Konstruktor aufrufe oder kann ich das auch direkt im Konstruktor machen?
Ich glaube, um es möglichst modular zu halten, wäre es sinniger eine eigene Methode zu schreiben.

Und ja, das soll schon solche Dimensionen annehmen, dass ich auch andere mathematische Funktionen verwende.

Zu deinem Nachtrag: Also ich würde das dann irgendwann auch mal gerne mit einer GUI versehen, aber im Moment bin ich noch in der Modellierungsphase, wo es erstmal mathematisch hinhauen muss. Später soll dann natürlich ein Term mithilfe von Buttons, aber auch über ein Textfeld (vielleicht sogar mit LaTeX-Befehlserkennung) eingegeben werden können, aber das ist ja noch in etwas fernerer Zukunft.

 

[rme]

Dass du auf die Token-Liste ganz verzichten sollst, meinte ich eigentlich nicht. Sondern, dass du eine Methode mit der Token-Liste aufrufst, diese aber die Liste nicht abspeichert, sondern in den Baum überführt. Wenn du mit Token statt mit Strings im Baum arbeitest, wäre das deutlich einfacher zu warten.

Nach außen fände ich diese Arbeitsweise angenehm:

MathContext ctx = new MathContext();
ctx.bindVariable("x", 23.42);
double res = ctx.evaluate("2x + 4");

Dabei erzeugt evaluate intern eine Instanz des Tokenizers, der eine Liste von Token liefert, füttert damit eine Parser-Klasse zum Auswerten und gibt das Ergebnis zurück. Damit ist MathContext quasi die FrontEnd-Klasse für die einzelnen Teile.

Richtig cool wäre evtl. ich auch sowas:

ctx.bindFunction("sin", new UnaryFunction() {public double f(double x) {return Math.sin(x); }});

 

[rme]

Gerade überlegt: Wenn man das Ganze noch eine kleine Stufe weiter treibt, könnte der Parser den Baum in irgendeiner Form an den Aufrufer zurückliefern, sodass man dieses Objekt mit einem anderen MathContext erneut anwenden kann. Dann wäre es zusammen mit der obigen Idee von bindFunction möglich, dass der Benutzer sich selbst Funktionen anlegen kann: parsen und Ergebnis via bindFunction an den MathContext zuweisen, sodass die Funktion dann nur noch den Kontext setzen und den Baum auswerten muss

 

[turtle]

Ich habe ebenfalls mal einen Taschenrechner realisiert.

Beim Parsen bzw. Auswerten einer Funktion habe ich den sogenannten Shunting-Yard Algorithmus eingesetzt. Er beruht darauf die Eingabe in "umgekehrter polnischer Notation (RPN)" umzuwandeln. Anschließend ist es leicht den Term auszurechnen.

Ich schlage vor, sich diesen mal genauer anzuschauen, ist nicht besonders schwierig

Dieser wertet eine Funktion aus und berechnet die Ausgabe. Dieses sieht per jUnit-Test beispielsweise so aus:

	@Test
	public void eval_15_plus_7_multiply_31_minus_4() {
		String expr = "15+7*31-4";
		List<Token> rpn = ShuntingYardScience.parse(expr);
		double result = ShuntingYardScience.evalRPN(expr, rpn);
		assertEquals("15 7 31 Multiply Plus 4 Minus", ShuntingYardScience.toString(rpn));
		assertEquals(228, result, 0.001);
	}