[Java] Terme berechnen

03/26/2013 19:00 dowhile#1
Hi,

für ein Projekt habe ich eine kleine Library geschrieben, mit der einfache mathematische Terme ausgerechnet werden können.

neue Version:
[Only registered and activated users can see links. Click Here To Register...]

Folgendes wird unterstützt:

* Konstanten (e, pi)
* Operatoren (+, -, *, /, ^) mit ^ vor *, / vor +, -
* Funktionen beliebig vielen Parametern (sin, cos, tan, exp, ln)
* Parameter
* Ableiten
* Term mit [Only registered and activated users can see links. Click Here To Register...] grafisch darstellen

Genutzt werden kann die neue Version wie folgt:

Code:
ExpressionParser parser = new ExpressionParser();
Expression exp = parser.parse("x^2");
Expression kann:

Code:
Expression.calculate():double
Expression.getParameterNames():Set<String>
Expression.setParameter(name:String, value:double)
Expression.getParameter(name:String):Parameter
Expression.differentiate(variable:String):Expression
Expression.differentiate(variable:Parameter):Expression
Expression.render():BufferedImage
Expression.render(size:float):BufferedImage
Expression.render(bgColor:Color, fgColor:Color, size:float):BufferedImage
Nach dem parsen hat jeder Parameter den Wert "0".

Die durch differentiate erstellte Ableitung besitzt die gleichen Parameter-Objekte wie der ursprüngliche Term (d.h. get/setParameter() beziehen sich auf die selben Objekte).

Die render()-Methode benötigt die oben verlinkte Library.

Es können neue Konstanten, Operatore und Funktionen hinzugefügt werden (ExpressionParser bietet dafür addConstant(), addFunction() und addOperator()). Dabei gilt:

Konstante sind Objekte von Constant, Funktionen leiten von FunctionNode oder DefaultFunctionNode (bei nur einem Parameter) ab und Operatore von OperatorNode. Bei beiden müssen einige abstrakte Methoden implementiert werden.

Methoden:

Komplettes Beispiel:
Code:
        ExpressionParser parser = new ExpressionParser();
        Expression exp = parser.parse("x^2");
        
        // Gibt aus: exp(ln(x) * 2.0) * (1.0 / x * 1.0 * 2.0 + ln(x) * 0.0)
        System.out.println(exp.differentiate("x").toTermString());
        
        JFrame frame = new JFrame();
        frame.getContentPane().add(new JLabel(new ImageIcon(exp.differentiate("x").render(32))));
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
Der generierten, abgeleiteten Terme werden noch nicht vereinfacht.

alte Version:
Vielleicht kann es ja jemand gebrauchen.
08/05/2013 22:54 dowhile#2
Neue Version.
08/06/2013 01:51 snow#3
Hast du für das Parsen einen eigenen Algorithmus entwickelt oder nutzt du einen bestehenden?
Ich hätte hier noch nen Taschenrechner, der Ausdrücke lösen kann, is aber in ner Mengenbasierten Skriptsprache geschrieben, den kann ich bei Interesse gerne hochladen.
08/06/2013 03:01 dowhile#4
Hi,

ich habe mich nicht nach bestehenden Algorithmen umgeschaut, meinen Lösungsweg in diesem Sinne also selbst entwickelt. Ich finde ihn aber ziemlich intuitiv und denke, dass auch andere das gleichermaßen lösen.

(Ich arbeite mit einer Methode, die immer in einem Abschnitt nach dem letzten Operator mit der niedrigsten Priorität sucht. Wenn einer gefunden wird, wird die Methode rekursiv für den Teil vor- und nach dem Operator aufgerufen; wird keiner gefunden, wird der Teil sonstig ausgewertet.)

Ich vermute, dass dein Algorithmus ähnlich oder gleich funktioniert (insbesondere wenn nicht, wäre es toll, wenn du deinen Code hochladen könntest - ich wäre interessiert).

(Was ist eine mengenbasierte Skriptsprache?)
08/06/2013 11:48 Shadow992#5
Quote:
Originally Posted by dowhile View Post
Hi,

ich habe mich nicht nach bestehenden Algorithmen umgeschaut, meinen Lösungsweg in diesem Sinne also selbst entwickelt. Ich finde ihn aber ziemlich intuitiv und denke, dass auch andere das gleichermaßen lösen.

(Ich arbeite mit einer Methode, die immer in einem Abschnitt nach dem letzten Operator mit der niedrigsten Priorität sucht. Wenn einer gefunden wird, wird die Methode rekursiv für den Teil vor- und nach dem Operator aufgerufen; wird keiner gefunden, wird der Teil sonstig ausgewertet.)

Ich vermute, dass dein Algorithmus ähnlich oder gleich funktioniert (insbesondere wenn nicht, wäre es toll, wenn du deinen Code hochladen könntest - ich wäre interessiert).

(Was ist eine mengenbasierte Skriptsprache?)
Wie sieht es mit solchen termen aus?
10*(4+4)^(2^(2-1))

Und sind auch Ableitungen von komplizierteren termen möglich z.B.
(10x^2+3x^(4x))/(2x^x)
08/06/2013 18:07 snow#6
Hehyo,

wir haben das ganze mal in einer Vorlesung behandelt. Dort haben wir den Shunting-Yard-Algorithmus verwendet, im Prinzip wird jedes Argument, das als solches erkannt wird (Operator, Zahl etc.) auf einen Stack-Datentypen gehauen und dann wird mit der Auswertung begonnen, indem der Stack abgebaut wird und Operatoren auf den Operator-Stack und Zahlen auf den Zahlen-Stack kommen usw., dabei wird dann auch immer die Priorität verglichen und danach wird das halt ausgewertet.

Wir haben das ganze in ner Vorlesung behandelt, ich schick dir mal nen Link zu dem Skript. :)
Die Sprache ist halt von unserem Dozenten entworfen worden, damit er da die ganzen Zusammenhänge mit der Mengenlehre anwenden kann, automatische Sortierung in ner Menge, Relationen und der ganze Kram halt. Da du Java kannst, sollte das aber recht einfach zu lesen sein.
08/06/2013 18:59 dowhile#7
Hi,

Quote:
Originally Posted by Shadow992 View Post
Wie sieht es mit solchen termen aus?
10*(4+4)^(2^(2-1))

Und sind auch Ableitungen von komplizierteren termen möglich z.B.
(10x^2+3x^(4x))/(2x^x)
das funktioniert beides. Der Term wird so zerlegt:
Code:
de.gccc.matheval.node.operators.Multiplication
	de.gccc.matheval.node.leaves.Literal -> 10.0
	de.gccc.matheval.node.operators.Power
		de.gccc.matheval.node.operators.Addition
			de.gccc.matheval.node.leaves.Literal -> 4.0
			de.gccc.matheval.node.leaves.Literal -> 4.0
		de.gccc.matheval.node.operators.Power
			de.gccc.matheval.node.leaves.Literal -> 2.0
			de.gccc.matheval.node.operators.Subtraction
				de.gccc.matheval.node.leaves.Literal -> 2.0
				de.gccc.matheval.node.leaves.Literal -> 1.0
Die Ableitung sollte zumindest stimmen (ich habe sie nur getestet, indem ich ein paar zufällige Werte für x eingesetzt und das Ergebnis mit andere Online-Tools verglichen habe).

Die Lib generiert folgende Ableitung:
Quote:
((0.0 * x ^ 2.0 + 10.0 * exp(ln(x) * 2.0) * (1.0 / x * 1.0 * 2.0 + ln(x) * 0.0) + 0.0 * x ^ (4.0 * x) + 3.0 * exp(ln(x) * 4.0 * x) * (1.0 / x * 1.0 * 4.0 * x + ln(x) * (0.0 * x + 4.0 * 1.0))) * 2.0 * x ^ x - (10.0 * x ^ 2.0 + 3.0 * x ^ (4.0 * x)) * (0.0 * x ^ x + 2.0 * exp(ln(x) * x) * (1.0 / x * 1.0 * x + ln(x) * 1.0))) / 2.0 * x ^ x * 2.0 * x ^ x
Quote:
Wir haben das ganze in ner Vorlesung behandelt, ich schick dir mal nen Link zu dem Skript.
Die Sprache ist halt von unserem Dozenten entworfen worden, damit er da die ganzen Zusammenhänge mit der Mengenlehre anwenden kann, automatische Sortierung in ner Menge, Relationen und der ganze Kram halt. Da du Java kannst, sollte das aber recht einfach zu lesen sein.
Danke, ich lese mich nachher mal ein.
08/06/2013 21:10 Shadow992#8
Quote:
Originally Posted by snow911 View Post
Hehyo,

wir haben das ganze mal in einer Vorlesung behandelt. Dort haben wir den Shunting-Yard-Algorithmus verwendet, im Prinzip wird jedes Argument, das als solches erkannt wird (Operator, Zahl etc.) auf einen Stack-Datentypen gehauen und dann wird mit der Auswertung begonnen, indem der Stack abgebaut wird und Operatoren auf den Operator-Stack und Zahlen auf den Zahlen-Stack kommen usw., dabei wird dann auch immer die Priorität verglichen und danach wird das halt ausgewertet.

Wir haben das ganze in ner Vorlesung behandelt, ich schick dir mal nen Link zu dem Skript. :)
Die Sprache ist halt von unserem Dozenten entworfen worden, damit er da die ganzen Zusammenhänge mit der Mengenlehre anwenden kann, automatische Sortierung in ner Menge, Relationen und der ganze Kram halt. Da du Java kannst, sollte das aber recht einfach zu lesen sein.
Shunting Yard ist standard was das angeht.
Eigentlich verwendet man den im Normalfall (wenn man nicht zwingend einen optimierten Algorhitmus braucht) auch für Compiler, Parser usw.
Das Prinzip ist auf etliches anwendbar und einfach und doch mächtig zugleich.

Für all diejenigen, die sich auch für diesen Algo interessieren und über Google auf den Thread gestoßen sind:

[Only registered and activated users can see links. Click Here To Register...]