Baumstruktur aus Term

[Runtime]

Hallo Leute,
ich möchte ein Term nach einer Baumstruktur aufbauen. Das soll wie unten beschrieben ablaufen. Der erste Teil habe ich schon, nur bein zweiten hab ich keinen Schimmer und wäre froh, wenn mir jemand eine Idee oder ein Ansatz liefen könnte, wie ich das angehen soll .

(a * b) * 14 + 34 / 12 - 18

1. Wird in dies umgewandelt -->

( - Klammer auf
a - Variable
* - Operator
b - Variable
) - Klammer zu
* - Operator
14 - Nummer
+ - Operator
34 - Nummer
/ - Operator
12 - Nummer
- - Operator
18 - Nummer

2. Soll nun wie ein Baum aufgebaut werden nach richtiger Reihenfolge -->

-
	+
		*
			klammer
				*
					a
					b
			14
		/
			34
			12
	18

Danke!
Gruss

 

[darekkay]

Mathematische Ausdrücke zu parsen ist nicht ganz trivial.

Mein Ansatz würde so aussehen:
- zunächst würde ich alle Klammerausdrücke substituieren, also von innen nach außen Klammerausdrücke durch variablen ersetzen: ((a+1)*2)+4 -> (x*2)+4 -> y+4
- nun kannst du die klammern von innen nach außen durcharbeiten, und dabei so vorgehen:
- das erste + oder minus finden, an dieser stelle den baum "brechen" (linke seite des ausdruckes von dem + oder - aus auf die linke seite des baumes, die rechte auf die rechte)
- wird kein + oder - gefunden, dann weiter mit * oder /

Beispiel:

- ((a+1)*b) / (7+c) - d
- klammern substituieren:
x = a+1
y = x * b
z = 7+c

ausdruck: y / z - d

- nun von innen nach außen durchgehen:
x = a+1 => am plus "brechen", also entsteht ein knoten + mit den kinden a und 1
y = x*b => am mal "brechen", also ensteht ein Knoten * mit den Kindern x und b, wobei x für den bereits erzeugten Knoten steht
z = 7+c => same, ein Knoten + mit 7 und c als Kinder

der Ausdruck lautet ja y / z - d
nun suchst du das erste + oder -, in dem fall ein minus, und auch hier erzeugst du links und rechts die Kinderknoten: - mit den kindern y / z und d
y und z hast du bereits, wieder rücksubstituieren, und dein baum wäre fertig.


Ich weiß, dass ich vielleicht nicht richtig rüberbringen kann, wie ich es meine, und ich weiß auch, dass es bestimmt effizienter geht - für deinen einfachen fall müsste das aber auch reichen

 

[JanHH]

Bei meinen (erfolgreichen) Bemühungen, sowas zu programmieren, ist schon die Token-Struktur ein Baum. Aus (a*b)*14 wird

Token 1: Klammerausdruck, Inhalt: Eine weitere Tokenlisten (bestehend aus drei, a * b)
Token 2: *
Token 3: 14

Wenn das in der Form vorliegt, ist es wesentlich einfacher, das zu verarbeiten und irgendwelche Objektstrukturen daraus generieren.

 

[Runtime]

@darekkay
Es soll wirklich ein Baum werden, weil man dnamisch Operatoren hinzufügen können soll.

@JanHH
Versteh nicht ganz... hab ich doch gemacht

 

[JanHH]

Nö hast Du nicht, nach dem was Du da geschrieben hast ;-).

 

[darekkay]

@darekkay
Es soll wirklich ein Baum werden, weil man dnamisch Operatoren hinzufügen können soll.

Hm? Und was hab ich denn geschrieben? Mein Ansatz erstellt dir doch einen Baum ???:L

 

[Runtime]

Ups, habs nicht verstanden . Ich probiers mal aus.
Edit:
Da gbits ein Problem: wie löst man das: (a + b * c -d / 4) / (x * y + 12)?

 

[darekkay]

Meinst du mit dem Beispiel, dass x und y drin vorkommen?
Mein x und y, was ich benutzt habe, war nur schematisch gemeint. Du müsstest es dir beispielsweise in eine Liste abspeichern und mit Indizes arbeiten:

Liste list;
Ausdruck = (a + b * c -d / 4) / (x * y + 12) 

list[0] =  (a + b * c -d / 4)
list[1] = (x * y + 12) 

Ausdruck = list[0] / list[1]

Alle Klammern aufgelöst, also kann man die Liste durchgehen:
(ich schreibe jetzt immer Node(Operation,Linker Baum, Rechter Baum) )

- das erste + oder - suchen: Node(+, a, b * c -d / 4)
- rekursiv beide Teilbäume durchgehen:
- a ist ein Blatt, also Node(a,Nil,Nil)
- b*c-d/4: das erste + oder - suchen: Node(-, b*c, d/4)
....

list[0] wurde in einen (Teil)Baum überführt
list[1]: äquivalent

Nun lautet der Ausdruck list[0] / list[1], also bleibt die letzte Operation: Node(/,"Baum, der bei list[0] entstand", "Baum, der bei list[1] entstand");


Wie gesagt, mein Ansatz ist vielleicht nicht der beste, aber er funktioniert. Man muss sich bloß ein paar Gedanken machen, wie man die Klammerausdrücke findet (von innen nach außen), wie man sie abspeichert und wie man sie dann wieder rücksubstituiert.

Ansonsten bietet google auch so einiges: java parse mathematical expression - Google-Suche

 

[Runtime]

Ich warte besser mal bis Weihnachten, dann bekomme ich dieses Buch und kanns dann selbst machen .

 

[Ark]

Öhm, warum willst du ausgerechnet die erste Auflage des Buches von 1986 auf englisch, wo es auch eine zweite Auflage von 2008 gibt (wahlweise auch auf deutsch)?

Das verlinkte Buch habe ich übrigens auch, und ich finde es sehr gut; kann ich nur empfehlen.

Ark

 

[Runtime]

Ich bekomme schon die neueste Auflage auf Deutsch, das war einfach das erste Ergebnis, das ich in Google gefunden habe.

 

[Ark]

Ich bekomme schon die neueste Auflage auf Deutsch, das war einfach das erste Ergebnis, das ich in Google gefunden habe.

Gehörst du dann auch zu denen, die immer "facebook login" bei Google eingeben, den ersten Link anklicken und sich dann wundern, warum sie sich nicht einloggen können? --> Google Solves the Fafebook Problem :autsch:

SCNR

Ark

(Entschuldigung, aber dieser Vorfall war/ist einfach zu geil. :lol: )

 

[Runtime]

Nein, eigentlich mache ich das nicht, aber ich kenn mich auf anazon.de nicht aus und Google war schon offen.

 

[Morl99]

Nein, eigentlich mache ich das nicht, aber ich kenn mich auf anazon.de nicht aus und Google war schon offen.

Lustig, das klappt wirklich

Übrigens gibts ja auch einfach ein Suchfeld in welches man den Suchbegriff eingeben kann ;-)

@Ark: Thx für den Link, das kannte ich noch nicht. Ich habe aber zuhause auch zwei Internetbenutzer denen es so geht... Und es war schon genug Arbeit meinen Eltern google zu erklären ;-) Tatsache ist, über google kann man so ziemlich alle Funktionen des Webs (nicht aber des Internets ) erreichen...

(Thread ist ja soweit erstmal erledigt gell? Wollte nicht sinnlos einen Problemthread zuspamen, fand den Link aber grad zu geil )

 

[Runtime]

Ich hab mir nicht mal die Mühe gemacht auf Amazon zu gehen. (Wegen dem Rechtschreibfehler: hab erst kürzlich gelern richtig mit der Tastatur zu schreiben.)

 

[Ralf Pongratz]

[...]
ich möchte ein Term nach einer Baumstruktur aufbauen. Das soll wie unten beschrieben ablaufen. Der erste Teil habe ich schon, nur bein zweiten hab ich keinen Schimmer und wäre froh, wenn mir jemand eine Idee oder ein Ansatz liefen könnte, wie ich das angehen soll .[...]

Moin!

Was soll der Formel-Parser denn alles können? Ich habe vor kurzem ein wenig Langeweile gehabt und einen programmiert. War nicht schwer und nach ein paar Stunden erledigt. Neben den Standardoperatoren sind auch trigonometrische Funktionen, Absolutwert, Konstanten (PI, e) und Variablen (die für die Berechnung ersetzt werden können) möglich.

Die Idee, die ich umgesetzt habe, basiert auf Rekursion. Beim Aufbau des Baumes wird die Formel überprüft. Ist der Ausdruck eine Zahl oder eine Konstante, wird sie als Zahlenelement zurückgegeben. Sonst wird die Formel in 1-2 Teile aufgeteilt und als ein Formelelement zurückgegeben, nachdem für jeden der Teile der Algorithmus rekursiv aufgerufen wurde. Das ganze funktioniert ebenenweise von außen nach innen. Die eigentliche Kunst war nur, die Operatoren in der richtigen Reihenfolge abzufragen.

Als Beispiel hier der Teil der Addition:

// Addition
if (formel.charAt(i)=='+') {
	if (formel.substring(0,i).equals(""))
		// Ein führendes Pluszeichen
		e = new Addition(null,new Formel(formel.substring(i+1,formel.length()), variablen).parse());
	else
		// Eine tatsächliche Addition
		e = new Addition(new Formel(formel.substring(0,i), variablen).parse(),new Formel(formel.substring(i+1,formel.length()), variablen).parse());
	return e;
}

Viele Grüße, Ralf

P.S.: Der Code ist leider zu umfangreich, um ihn hier zu posten.

 

[Runtime]

Gib mal einen Baum aus, der dadurch produziert wurde.

 

[Ralf Pongratz]

Gib mal einen Baum aus, der dadurch produziert wurde.

Sollte ich damit gemeint sein? Eine Anrede wäre hier hilfreich und höflich...

Ich weiß nicht, was Du erwartest, aber meiner Meinung nach gibt es nur einen Baum, der für eine Formel erzeugt werden kann (von kleinen Variationen abgesehen).
3+sin(x) würde folgenden Baum ergeben:

    /-- 3
-- +
    \-- sin -- x

Gruß, Ralf

 

[Runtime]

Ja so ein Baum ist perfekt. Dürfte ich bitte den ganzen Code der Methode haben?

 

[SlaterB]

siehe auch
http://www.java-forum.org/allgemeines/12306-parser-fuer-mathematische-formeln.html

 

[Runtime]

Danke, hab ich mir aber schon angesehen. Der erste Parser funktioniert nicht, er parst jedes mal den String neu und wenn ich ein Programm schreibe lege ich Wert darauf dass es 100% von mir ist, d. h. nichts anderes ausser die Standardbibliothek benutzt wird.

 

[SlaterB]

> Der erste Parser funktioniert nicht, er parst jedes mal den String neu

du meinst dass es noch kein x im Baum gibt, welches mit aktuellen Funktionswert gefüllt wird?
tja, stimmt das fehlt noch, kann man ergänzen

> wenn ich ein Programm schreibe lege ich Wert darauf dass es 100% von mir ist,
aja:
> Dürfte ich bitte den ganzen Code der Methode haben?

 

[Runtime]

> wenn ich ein Programm schreibe lege ich Wert darauf dass es 100% von mir ist,
aja:
> Dürfte ich bitte den ganzen Code der Methode haben?

Damit mein ich natürlich dass alles selbst geschrieben ist, die Ideen sind nicht alle von mir.

du meinst dass es noch kein x im Baum gibt, welches mit aktuellen Funktionswert gefüllt wird?
tja, stimmt das fehlt noch, kann man ergänzen

Er funktioniert wirklich nicht, ich habe den Code mal ausprobiert.

 

[SlaterB]

bei mir gehts, wenn du das weiterverfolgen willst, müsstest du Fehler näher beschreiben,
aber muss ja nicht sein

weder die Idee noch die Code-Vorlage für einen solchen Parser wird von dir sein,
wenn du also irgendwas von irgendwo abschreibst, dann schlage ich eben diese Quelle vor,
ohne den noch nicht gesehenen Code von Ralf Pongratz abwerten zu wollen

 

[Runtime]

Sonst warte ich lieber auf das Buch, dort ist alles ein bisschen verständlicher, mit Tokenizen, Prüfen, Parsen, Optimieren...

 

[Wildcard]

Parser schreibt man heute normal nicht mehr per Hand sondern verwendet einen Parsergenerator.
IMO der mächtigste und gleichzeitig einfachste ist zZ Xtext. Eine Grammatik für arithmetrische Ausdrücke wird auch als Example ausgeliefert:

Addition returns Expression:
 Multiplication ({Addition.left=current} '+' right=Multiplication)*;

Multiplication returns Expression:
 Primary ({Multiplication.left=current} '*' right=Primary)*;

Primary returns Expression:
 NumberLiteral |
 '(' Addition ')';

NumberLiteral:
 value=INT;

Mehr brauchst du nicht, der Rest wird aus dieser Grammatik generiert. Erklärung und Quelle: Sven Efftinge's Blog: Parsing Expressions with Xtext

Xtext

Falls Xtext etwas too-much für deinen Use-Case ist würde ich stattdessen zu Antlr greifen.

 

[Runtime]

Gibts eigentlich schon solche, die Compiler für .class Dateien generieren können?

 

[Wildcard]

Gibts eigentlich schon solche, die Compiler für .class Dateien generieren können?

Bitte?

 

[Runtime]

Generatoren für Compiler. Was ist so komisch daran?

 

[Wildcard]

Aber warum willst du class Dateien kompilieren? Die sind bereits kompiliert. Oder willst du class Dateien erzeugen? Wenn ja, dann ist das kein trivialer Prozess da du die Semantik deiner Sprache auf die Semantik von Java Byte Code abbilden musst und das nimmt dir kein Generator ab.
That said ist besagtes Xtext tatsächlich ein komplettes Framework für domain specific languages.
Unter anderem wird dir ein Lexer, ein Parser, ein Linker, ein Serializer und ein Eclipse Editor mit Code Completion, Syntax Highlighting, Life Validierung, Folding, Outline, Hyperlinks,... generiert.
Zusätzlich bietet das Framework alles was du brauchst um Language Scoping, Cross References, Namespaces,... zu implementieren. Ausserdem gibt es bereits support für einen inkrementellen Compiler samt Autobuild Infrastruktur wie bei Java in Eclipse.
Für den Compiler musst du aber dann selbst Hand anlegen, denn kein Generator kann wissen wie dein Zielformat denn aussehen soll. Es gibt auch Beispiele für Xtext basierte Compiler die eine textbasierte Ausgangsstruktur erzeugen mit Xpand und MWE, aber class Files direkt zu erzeugen ist eher exotisch.

 

[Ralf Pongratz]

Ja so ein Baum ist perfekt. Dürfte ich bitte den ganzen Code der Methode haben?

Moin!

Ich würde die komplette Bibliothek als .jar zur Verfügung stellen. Allerdings werde ich erst am Wochenende dafür Zeit haben.
Und noch eins: Die Bibliothek erzeugt zwar intern einen Baum, auf dem Bildschirm kann man allerdings nur das Ergebnis der Berechnung als Zahl bzw. die Funktion als Formel anzeigen lassen. Eine visuelle Darstellung des Baumes gibt es nicht.

Ralf

 

[Runtime]

@Wildcard
Ja eigentlich meinte ich .xyz -> .class kompilieren.

@Ralf Pongratz
Ok danke.

 

[Ralf Pongratz]

@Ralf Pongratz
Ok danke.

Die Bibliothek findest Du unter Reaktivlichter. Dort steht auch eine kleine Anleitung.
Falls Du Fehler findest, wäre ich über einen Hinweis dankbar.

Viel Erfolg, Ralf

 

[Runtime]

Danke, leider gab es einen Fehler, als ich ihn ausprobiert habe:

Exception in thread "main" java.lang.NullPointerException
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:145)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:103)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:210)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:103)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:210)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:103)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:184)
        at de.reaktivlicht.utilities.formel.Formel.parse(Formel.java:112)
        at jizformulatest.Main.main(Main.java:18)
Java Result: 1

Hier der Code:
[Java]
package jizformulatest;

import de.reaktivlicht.utilities.*;
import de.reaktivlicht.utilities.formel.*;
import java.util.LinkedList;

public class Main {

public static void main(String[] args) {
String s = "2*P*I+13";
Formel formel = new Formel(s);

LinkedList<Tupel<String, Double>> variablen = new LinkedList<Tupel<String, Double>>();
variablen.add(new Tupel<String, Double>("P", 1.0));
variablen.add(new Tupel<String, Double>("I", 3.0));
variablen.add(new Tupel<String, Double>("PI", Math.PI));

Element element = formel.parse(variablen);

System.out.println(element.calculate());
}
}

[/code]

 

[Ralf Pongratz]

Danke, leider gab es einen Fehler[...]

Danke für die Info. Ich habe leider etwas in der Beschreibung vergessen. Bevor Du die Bibliothek im Programm das erste Mal nutzt, musst Du folgenden Befehl aufrufen:

[JAVA=42]import de.reaktivlicht.utilities.formel.Konfig;

[...]

Konfig.init()[/code]

In der Konfigurationsdatei wird das Zahlenformat initialisiert. Damit will ich später realisieren, dass auch das englische Zahlenformat genutzt werden kann.

Und noch eines am Rande: Mathematische Konstanten (Pi und e) sind schon definiert. Du must also keine entsprechende Variable definieren. Falls Du eine Variable mit dem gleichen Namen (aber einem anderen Wert) anlegst, hat die Variable aber Vorrang.