[Java] Terme berechnen

[dowhile]

Hi,

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

neue Version:


Folgendes wird unterstützt:

* Konstanten (e, pi)
* Operatoren (+, -, *, /, ^) mit ^ vor *, / vor +, -
* Funktionen beliebig vielen Parametern (sin, cos, tan, exp, ln)
* Parameter
* Ableiten
* Term mit grafisch darstellen

Genutzt werden kann die neue Version wie folgt:

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

Expression kann:

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:

 Spoiler

DefaultFunctionNode:
getName():String -> Bezeichnung (wie cos, sin, ...)
calculate():double -> berechnen, den berechneten Parameter gibt es über getParameter().calculate()
isConstant():boolean -> true, wenn konstant, d.h. kein Parameter
cloneTree():Node -> klonen
cloneTreeForDerivative():Node -> selbiges
differentiateOuter(variable:Parameter):Node -> äußere Funktion ableiten; beim Ableiten muss der Parameter mit cloneTreeForDerivative() geklont werden.

FunctionNode hat zusätzlich:
differentiate(variable:Parameter):Node -> Ableiten
getMinParameterCount():int -> min. Parameter
getMaxParameterCount():int -> max. Parameter
... dafür kein differentiateOuter().

OperatorNode hat neben cloneTree, cloneTreeForDerivative, differentiate und calculate:

getPriority():int -> Priorität zu anderen Operatoren; +/- hat PRIORITY_LOWER, *// PRIORITY_NORMAL, ^ PRIORITY_HIGHER
getSymbol():String -> Das Symbol

Komplettes Beispiel:

        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:

 Spoiler

Folgendes wird unterstützt:

* Konstanten (e, pi)
* Operatoren (+, -, *, /, ^, %) mit ^, % vor *, / vor +, -
* Funktionen mit einem Parameter (sin, cos, tan, abs, sqrt, log)
* Parameter

Genutzt werden kann die Library wie folgt:

ExpressionFactory factory = new ExpressionFactory();
Expression exp = factory.compile("5 + 4 * 2^sin(e^pi)");

Expression kann:

Expression.calculate():double
Expression.getParameterNames():Set<String>
Expression.setParameter(name:String, value:double)
Expression.getParameter(name:String):double

Eigenen Operator hinzufügen:

factory.addOperator("[NAME]", new OperatorNode() {

    @Override
    public double calculate() {
        parameterA.calculate(); // Wert links
        parameterB.calculate(); // Wert rechts
        return ...;
    }
}

Die Priorität kann über das Attribut priority angegeben werden; ggf. im Konstruktor setzen.
Konstanten dazu:
OperatorNode.PRIORITY_HIGH = 100 = %, ^
OperatorNode.PRIORITY_MEDIUM = 0 = *, / = Standardwert
OperatorNode.PRIORITY_LOW = -100 = +, -

Eigene Funktion hinzufügen:

factory.addFunction("[NAME]", new FunctionNode() {

    @Override
    public double calculate() {
        parameter.calculate(); // Parameter
        return ...;
    }
}

Eigene Konstante hinzufügen:

factory.addConstant("[NAME]", new ConstantNode([VALUE]));

Im Anhang ist das NetBeans-Projekt (Quelltext in src, Binary in dist).

Vielleicht kann es ja jemand gebrauchen.

[dowhile]

Neue Version.

[snow]

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.

[dowhile]

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?)

[Shadow992]

Originally Posted by dowhile

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)

[snow]

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.

[dowhile]

Hi,

Originally Posted by Shadow992

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:

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:

((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

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.

[Shadow992]

Originally Posted by snow911

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: