Funktionsparser

[ethrandil]

Hiho,
ich suche einen Algorithmus, der mir zB aus
(x*(5.0+(x^x)))/(2.0-x)
sowas macht:

new Divider(new Multiplier(new XValue(),new Additioner(new Value(5),new Hoch(new XValue(), new XValue()))),new Substractioner(new Value(2),new XValue()))

Ich bin da zu blöde zu :/

[ethrandil]

nochmal übersichtlicher: das ist quasi ein Baum:
new Divider(new Multiplier(new XValue(),new Additioner(new Value(5),new Hoch(new XValue(), new XValue()))),new Substractioner(new Value(2),new XValue()))


(x*(5.0+(x^x)))/(2.0-x) =

Div
/ \
Multi Sub
/ \ / \
X Add 2 X
/ \
5 Hoch
/ \
X X

Das gibt es doch bestimmt ;) Stelle ich mir als musteraufgabe für Rekursion vor :bäh:

[Abe Ghiran]

Hi!

Das ganze in Java? Also da würde ich mir eine abstrakte Oberklasse "NummericalExpression" machen, mit einer static Methode "fromString", die eine "NummericalExpression" zurückgibt (also eine Factory Methode).

Dann bräuchte man einige abgeleitete Klassen, die bestimmte Operationen darstellen, wie du das ja schon hast ("Division", "Klammern", "Number" -> für eine Zahl).

Dann würde man mit "NummericalExpression.fromString(String s)" beginnen, da müsste also der Parser rein. Der sollte sich jetzt das erste Zeichen anschauen und an Hand von diesem schon mal entscheiden, was er denn da so vor sich hat. Da gibt es meiner Meinung nach nur 3 Möglichkeiten:
-eine Zahl, dann muß er das Ende der Zahl suchen und diesen Substring an Number.fromString übergeben.
-eine öffnende Klammer: dann muß er die passende schließende Klammer finden und diesen substring an KlammerAusdruck.fromString übergeben.
-eine Variable, also einen Buchstaben.
Alles andere wäre an dieser Stelle ein Fehler.
Das Ergebnis landet auf einem Stack.
Dann geht der Parser mit dem verbliebenen String weiter, da muß er jetzt am Anfang ein Rechensymbol finden. Das merkt er sich, wertet den zweiten Teil aus und macht dann aus beiden jetzt entstandenen "NummericalExpressions" eine neue.
Die wird dann zum Schluß zurückgegeben.

In den konkreten Klassen, wie "Division", etc, muß dann in fromString wieder ein ähnlich arbeitender Parser sein.

Ich hoffe das war verständlich, wenn es hilft kann ich auch mal eben ein bißchen code zusammenhacken.
BTW, was ist denn aus deinem mp3 streaming Projekt geworden?

Edit: Das ganze ergibt dann eine rekursive Datenstruktur, bei der eine Klasse wieder member dieser Klasse hat. Z.B. hat eine Multiplikation zwei member faktor1 und faktor2, die wieder vom Typ NummericalExpression sind.
Die Klassenhierarchie würde dann so aussehen:

abstract class NummericalExpression
| | |
| | |
| | |
Multiplikation Division Klammerausdruck
etc


Grüße, Jan

[ethrandil]

Ahh du warst das, der beim Streaming mitmachen wollte :)
Also, das Projekt ist wohl eingeschlafen, bzw ich hab nichtmal damit angefangen. Weiß auch nicht warum.
Ich hab nur mal einen mp3player mit java geschrieben, der winamp-Dateilisten lesen kann. Das ist aber ziehmlich blöde mit Java, da es keine 'vernünftigen' Bibliotheken für mp3 gibt in Java, ... naja.

Der von dir vorgeschlagene Lösungsweg ist schon okay... Aaber es müssen ja zB punkt vor Strich Regeln beachtet werden, nicht nur Klammern...
Eine Architektur hab ich mir auch schon ausgedacht:
Es gibt eine Klasse Functionparser, die eine Methode
private static Function parseFunction(String function)
hat
Eine Klasse Function sieht so aus:

class Function{
public Command rootCommand=null;

Function(Command command){
this.rootCommand=command;
}

double getValue(double x){
Command replacedCommand= replace(rootCommand, x);
return replacedCommand.getValue();
}

Command replace(Command command, double x){
if(command.getType().equals("xvalue"))
command=new Value(x);
if(command.subCommandCount()>0){
Command subcommands[]=command.getSubCommands();
for(int i=0;i<subcommands.length;i++)
subcommands[i]=replace(subcommands[i],x);
command.setParameters(subcommands);
}
return command;
}

public String toString(){
return rootCommand.toString();
}

}

Falls es dich interessiert ;)
Command ist eine abstrakte Klasse, von der StdCommand erbt.
StdCommand ist ein Standard für Rechenarten mit 2 Parametern :)
Davon erben dann multiplikation, division, addition, subtraktion, hoch, REST.
die sieht so aus

class Additioner extends StdCommand{
Additioner(Command com1, Command com2){
super(com1,com2);
}

double getValue(){
return values[0].getValue()+values[1].getValue();
}

String getType(){
return "+";
}
}

dH eine Addition bekommt immer 2 Command s als Parameter. auch Ein Wert ist ein Command (Value). unterscheiden lässt sich das dann mit "getType" :)
Wenn ich so eine Funktion übergebe, zB mit:
Command command=new Divider(new Multiplier(new XValue(),new Additioner(new Value(5),new Hoch(new XValue(), new XValue()))),new Substractioner(new Value(2),new XValue()));
Function func=new Function(command);

Funktioniert ja alles Wunderbar :) Das einzige was im Puzzle fehlt ist der, schwere, Algorithmus, der mir das ganze in die Richtige Form parst.

mfg Eth
anhang: Command.java

abstract class Command{
abstract double getValue(); //Gibt den Wert zurück. Im endefekt rekursiv.
abstract String getType(); //der typ. zB +-/* value xvalue
abstract int parameterCount(); //Anzahl der Parameter. wird noch ausgemistet
abstract void setParameters(Command[] commands); //sollte ich umbenennen in setSubCommands
abstract Command[] getSubCommands(); //gibt die subcommands zurück
abstract int subCommandCount(); //das was parameterCount ist. ersteres ist irgendwie unnötig
abstract public String toString(); //gibt das Command samt aller subcommands als String zurück. zB (2 * 4)
}

[ethrandil]

Bei meinem 'Funktionsformat' gibt es keine Klammerausdrücke, da es ein Rekursiver Baum ist, in dem es keine Mehrdeutigkeiten gibt.
Klammern müssen zwar beim Parsen beachtet werden, kommen darin aber nicht vor.
Die Funktion replace ist dafür zuständig die X-Werte durch die Numerischen-Werte zu ersetzen.

[ethrandil]

Ichhabe auch schon eine Funktion, die das ganze in teilstrings unterteilt. Also alles was Zahl ist in einen String und alles andere in einzelne Strings. dH ich mache aus "2.5*7,0^x"
ein Array aus Strings.
"2.5"
"*"
"7,0"
"^"
"x"
Das müsste dann halt nur in ne Funktion verarbeitet werden *heul*

[Abe Ghiran]

Okilidokili....
Ich muß mal eben etwas denken aber ich glaube das klappt schon ;).

Wenn ich fertig bin, poste ich das hier.

Ah, das mit dieser Funktion klingt gut.

Grüße, Jan

[Demirug]

public static ICalc Parse (string formel)
{
int klammerebene = 0;
int splitpos = -1;
int splitlevel = 0;

bool klammer = false;

for (int Index = 0 ; Index < formel.Length ; Index++)
{
switch (formel[Index])
{
case '(':
klammer = true;
klammerebene++;
break;

case ')':
klammer = true;

if (klammerebene == 0)
throw new Exception ();

klammerebene--;
break;

case '+':
case '-':
if (splitlevel > 1 || klammerebene != 0)
break;

splitpos = Index;
splitlevel = 1;
break;

case '*':
case '/':
if (splitlevel > 2 || klammerebene != 0)
break;

splitpos = Index;
splitlevel = 2;
break;

case '^':
if (splitlevel > 3 || klammerebene != 0)
break;

splitpos = Index;
splitlevel = 3;
break;

}
}

if (klammerebene != 0)
throw new Exception ();

if (splitlevel > 0)
{
ICalc left = Parse (formel.Substring (0, splitpos));
ICalc right = Parse (formel.Substring (splitpos+1));

switch (formel[splitpos])
{
case '+':
return new Add (left, right);

case '-':
return new Sub (left, right);

case '*':
return new Mul (left, right);

case '/':
return new Div (left, right);

case '^':
return new Potenz (left, right);

default:
throw new Exception ();
}
}

if (klammer)
return Parse (formel.Substring (1, formel.Length-2));

if (formel == "x")
return new Variable ();

return new ConstWert (formel);
}


Geht sicher auch noch einfacher aber dafür müsste ich nachdenken.

Ist C# die portierung in eine andere Sprache sei dem Leser überlassen.

[zeckensack]

ethrandil,
sagt dir 'umgekehrt polnische Notation' etwas?
Dabei schreibt man erst die Operanden in umgekehrter Reihenfolge, dann die Operatoren. Gehört also zur Familie der Postfix-Notationen.

Das praktische daran ist, daß Prioritäten ohne Klammern ausgedrückt werden können, und es sich hervorragend zu stackbasierter Abarbeitung eignet.
Originally posted by ethrandil
(x*(5.0+(x^x)))/(2.0-x)

linke Seite UPN
x 5.0 x x ^ + *

rechte Seite UPN
x 2.0 -

Zur Zusammenfassung macht man jetzt das:
x 2.0 - x 5.0 x x ^ + * /

Abarbeitung von links nach rechts, pseudo
while (!end_of(string))
{
Symbol=get(string);
If ((Symbol==Konstante)||(Symbol==Variable))
{
Stack.push(value(Symbol))
}
else
If (Symbol==Operator)
{
Operand a=Stack.top(); Stack.pop();
Operand b=Stack.top(); Stack.pop();
Ergebnis=apply(Operator,a,b);
Stack.push(Ergebnis);
}
}
return(Stack.top());

Erstmal ohne Gewähr ;)

Was dir jetzt natürlich noch fehlt, ist eine Funktion die die UPN-Notation erzeugt :D

[Abe Ghiran]

Hui, da war Demirug schneller als ich. Und das sieht auch eine ganze Ecke eleganter aus, als das an dem ich gerade rumgebastelt habe :sulkoff:.

Jan

[Demirug]

Originally posted by zeckensack
ethrandil,
sagt dir 'umgekehrt polnische Notation' etwas?
Dabei schreibt man erst die Operanden in umgekehrter Reihenfolge, dann die Operatoren. Gehört also zur Familie der Postfix-Notationen.

Das praktische daran ist, daß Prioritäten ohne Klammern ausgedrückt werden können, und es sich hervorragend zu stackbasierter Abarbeitung eignet.


linke Seite UPN
x 5.0 x x ^ + *

rechte Seite UPN
x 2.0 -

Zur Zusammenfassung macht man jetzt das:
x 2.0 - x 5.0 x x ^ + * /

Abarbeitung von links nach rechts, pseudo
while (!end_of(string))
{
Symbol=get(string);
If ((Symbol==Konstante)||(Symbol==Variable))
{
Stack.push(value(Symbol))
}
else
If (Symbol==Operator)
{
Operand a=Stack.top(); Stack.pop();
Operand b=Stack.top(); Stack.pop();
Ergebnis=apply(Operator,a,b);
Stack.push(Ergebnis);
}
}
return(Stack.top());

Erstmal ohne Gewähr ;)

Was dir jetzt natürlich noch fehlt, ist eine Funktion die die UPN-Notation erzeugt :D


OT:

Der Code hat sehr viel ähnlichkeit mit dem MSIL Interpreter vom MONO Projekt. MSIL arbeitet auch auf Stackebene was es sehr angenehm macht wenn man aus MSIL Code einen Funktionsbaum aufbauen will.

[ethrandil]

Xmas, ich mus smit dir schimpfen :nono:... Dein Parser beachtet keine potenz vor Strich rechnung!!
(Wenn ich ihn richtig portiert habe)...
27/x^x
wird zu

((value 27.0/xvalue)^xvalue)

man beachte die Klammern ...
wenn ich 27/(x^x) schreibe gehts ...

EDIT: auch keine punkt vor Strichrechnung ... ich glaub langsam der Fehler liegt bei mir ...
EDIT2: Ich hab einfach mal die Split-werte invertiert .. nu gehts ;(

[ethrandil]

Hiho,
mein Funktionsparser hat soeben die Versionsnummer 1.0 erreicht :naughty:
download hier (http://www.ethrandil.de.vu/projects/Funktionsparser1_0b.zip)
Kommentare erwünscht, ein großes Dankeschön an XMas für seine Anregungen [welche Erwähnung möchtest du im Quelltext haben??]

Nächste, momentane noch ferne, Ziele sind:
Optimierung der Funktionen
Schnittpunktbestimmung
Zusätzliche Funktionen wie sin, cos, tan

Und ich werde mal testen, ob das ganze mit einem JIT wesentlich schneller ist *g*.

Soweit erstmal. Gute Nacht noch ;)
Eth

[zeckensack]

Iiiih!! JAVA! :bäh:

[ethrandil]

Danke für deinen Beitrag, ich werde drüber nachdenken du böser Postingabstauber :bäh:
ich sag ja auch net, IIIH C++ Das kann nur pseudo OOP :P

[noid]

Hiho,
mein Funktionsparser hat soeben die Versionsnummer 1.0 erreicht :naughty:
download hier (http://www.ethrandil.de.vu/projects/Funktionsparser1_0b.zip)
Kommentare erwünscht, ein großes Dankeschön an XMas für seine Anregungen [welche Erwähnung möchtest du im Quelltext haben??]

Nächste, momentane noch ferne, Ziele sind:
Optimierung der Funktionen
Schnittpunktbestimmung
Zusätzliche Funktionen wie sin, cos, tan

Und ich werde mal testen, ob das ganze mit einem JIT wesentlich schneller ist *g*.

Soweit erstmal. Gute Nacht noch ;)
Eth

*fertiggebuddelt*

hast du den formelparser noch? :confused:

[noid]

hat sich schon...
benutze jetzt den hiet: http://www.singularsys.com/jep/

[ethrandil]

Na denn :-)

Hätt' ihn auch noch gehabt. :-)

- Eth

[Sliver21]

Zeig deinen mal, Ethrandil :)

[ethrandil]

Willst du den Code oder das Programm?

So wirklich toll ist das Programm nicht, kann auch nur elementare Rechenfunktionen *g*

Meinen Parser hab ich von xmas portiert... moment *suchsuch*


//this code is ported from Xmas' C#-function. No Warranty ;)
public static Command parse(String formel) throws Exception
{
int klammerebene = 0;
int splitpos = -1;
int splitlevel = 0;

boolean klammer = false;

for (int i = 0 ; i < formel.length() ; i++)
{
switch (formel.charAt(i))
{
case '(':
klammer = true;
klammerebene++;
break;

case ')':
klammer = true;
if (klammerebene == 0)
throw new Exception ("nicht genug Klammern geöffnet");

klammerebene--;
break;

case '+':
case '-':
if (splitlevel > 4 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 4;
break;

case '*':
case '/':
if (splitlevel > 3 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 3;
break;

case '^':
if (splitlevel > 2 || klammerebene != 0){
break;
}

splitpos = i;
splitlevel = 2;
break;
}
}

if (klammerebene != 0)
throw new Exception("Klammern nicht geschlossen!!!");

if (splitlevel > 0)
{
Command left = parse (formel.substring(0, splitpos));
Command right = parse (formel.substring(splitpos+1));

switch (formel.charAt(splitpos))
{
case '+':
return new Additioner(left, right);

case '-':
return new Substractioner(left, right);

case '*':
return new Multiplier(left, right);

case '/':
return new Divider(left, right);

case '^':
return new Hoch(left, right);
default:
throw new Exception();
}
}

if (klammer)
return parse (formel.substring(1, formel.length()-1));

if (formel.equals("x"))
return new XValue();

if(formel.length()>0)
return new Value(java.lang.Double.parseDouble(formel));

return new Value(0);
}


Tja, das ists...

- Eth