Funktionsparser

Hallo, arbeite zzt. an einem Parser, der mathematische Funktionen (x³+2x-5, als String vom Benutzer eingegeben) zum weiterverarbeiten auswertet. habe mir dazu schon einen guten Algorithmus überlegt, womit ich das in diese Form bringe :(Beispiel oben) 1x^3+0x2+2x^1-5x0.
Zuerst ermittle ich den Funktionsgrad, dann die explizit angegebenen degrees (beim beispiel: 2 und 1) und die Anzahl x'. Danach splitte Ich den String vor jedem "x" und speichere die einzelnen Strings in ein String-Array. Dann kann ich die Koeffizienten einfach ermitteln, da sie immer am Ende der Teilstrings stehen(wenn keiner da ist, ist der Koeffizient 1)

Jetzt mein Problem: Ich weiß nicht wie ich den Koeffizienten, der am Ende jedes Teilstrings steht, als double-Wert speichern kann. Meine Idee war die Teilstring nach dem letzten "+" bzw. "-" zu durchsuchen, damit ich die genaue Position des Koeffizienten bekommen.

Ich wäre dankbar wenn mir jmd. weiterhelfen kann bzw. Verbesserungsvorschläge hat, die Sache zu lösen.

Schönen Gruß

Th69

Hallo yamchu ,

du kannst dir ja mal meinen Funktionsparser unter http://www.c-plusplus.net/forum/p1780654#1780654 anschauen (einzig das Weglassen des '*'-Operators funktioniert nicht).
Den theoretischen Hintergrund zu dem Parser habe ich in diesem Artikel beschrieben: http://www.mycsharp.de/wbb2/thread.php?threadid=71995 (da ich ihn nochmals nach C# portiert habe). Stichwort: (E)BNF

Das String-"Gefrickel" hat diverse Nachteile (insbesondere bei Operatorprioritäten und evtl. Klammerung von Ausdrücken).

Solange deine Funktion jedoch immer als Polynom vorliegt, würde es wirklich reichen, nach den "+" bzw. "-"-Zeichen zu splitten und dann den Ausdruck "ax^b" auseinanderzunehmen. Sollen jedoch dann auch noch die mathematischen Funktionen, wie z.B. sin(x), cos(x) etc. dazukommen, so erfordert das dann einen großen Umbau deines Codes (mein Parser unterstützt daher von vorneherein alles: Operatoren, Funktionen, Konstanten und Variablen).

Rhombicosidodecahedron

yamchu, richtige mathematische Funktionen (sin cos tan & konstanten) oder "nur" Polynome?

danke erstmal,

ja vorerst will ich nur Funktionen ohne Konstanten, sin, cos, tan usw. verarbeiten.
Sonst lässt sich ja alles als Polynom darstellen. Gebrochenrationale Funktionen lassen sind ja auch als zwei Polynome darstellbar. Und Klammern kann man ausmultiplizieren, sodass man wieder auf die Polynomform kommt.
Ich wusste nicht, dass es so schwierig ist später Konstanten und Funktionen wie sinus und cosinus zu integrieren...

Das ist und bleibt Gefrickel.

Ein Rekursiv Absteigender Parser ist nicht sooo schwer zu verstehen und zu implementieren. Beschäftige Dich am Besten ein wenig mit Grammatiken und Du wirst einen sehr viel robusteren Parser bauen können, der nicht bei der ersten Erweiterung auseinanderfällt.

Das stimmt, mit einem rekursiven Parser ist es einfach und leicht verständlich. Aber ich möchte eine mathematische Formel nicht nach einer Variable (x) auflösen und berechnen, sondern die Formel zersplitten und strukturieren, sodass ich damit beispielsweise eine Nullstellenberechnung oder Polynomdivision machen kann. Sozusagen ein kleines Computer Algebra System. Ich weiß nicht wie ich das anders angehen soll, als den String mühevoll zu zerpflücken. wenn ich Sinus, und Cosinus einbaue, denke ich dass ich die Klammern dann rekursiv lösen kann (sinus(x) wird dann sinus(1x^1+0x0)). Ein Parser der die Funktion nach einer Variable auflöst bringt mich da aber leider nicht weiter...

yamchu schrieb:

[...] sondern die Formel zersplitten und strukturieren, sodass ich [...]

Und genau dafür benötigst Du eine geeignete Darstellung der Formeln: Einen Syntaxbaum. Und genau den bekommst Du mit einem sauber implementierten Parser.

Ein Parser hat in erster Linie nichts damit zu tun eine Formel nach x aufzulösen. Ich denke Du hast da eine falsche Vorstellung.

Du willst ein kleines CAS? Schau Dir Grammatiken, Rekursiv Absteigende Parser und Syntaxbäume näher an.
Wenn alles steht, ist die Erweiterung ein Kinderspiel. Zum Beispiel um Ableitungen zu berechnen.

okay, habe mir einen rekursiven Algorithmus überlegt und dazu eine Parser-Klasse geschrieben. die Funktion lasse Ich dazu in einen String eingeben und werte ihn von links nach rechts aus, dazu nehme Ich die ersten bei Zahlen und die ersten bei Operatoren aus dem String und packe sie in 2 verschiedene deques's. Jetzt will Ich die Zahlen und Operatoren die ich in die Deques kopiert habe vom String abschneiden, um wieder rekursiv den Parser aufzurufen. dazu muss Ich aber eine String-Referenz damit der String auch verändert wird an die Methoden (getdigit, getoperator) übergeben. An dieser simplen Übergabe komm ich nicht weiter, ist es nicht möglich string-Referenzen zu übergeben?

ok, habe es jetzt, dummer fehler von mir^^

yamchu schrieb:

okay, habe mir einen rekursiven Algorithmus überlegt und dazu eine Parser-Klasse geschrieben.

Ich möchte noch klarstellen, dass hinter dem Begriff "Rekursiv Absteigende Parser" ein festes Konzept steckt. Du kannst damit Parser für gewisse (einfache) Grammatiken nach Schema-F realisieren. Es geht nicht darum irgendeinen rekursiven Parser nach eigenen Ideen zu realisieren, sondern dieses erprobte Schema zu verwenden.

http://en.wikipedia.org/wiki/Recursive_descent_parser