Hallöchen,

ich möchte diesen Beitrag als eine Art Blog zum Projektfortschritt nutzen. Sollte es eine Blog-Funktion hier geben, habe ich sie nicht gesehen und bitte um den entsprechenden Hinweis. Wenn das doch in ein anderes Forum gehört, bitte verschieben.

Also, worum gehts?

Ich bin hier sicherlich nicht der Erste, der einen Formelparser schreiben will und meiner ist wohl auch nicht der beste aller Formelparser, aber er ist eben meiner . Dieser soll Kern eines Funktionsplotters werden, der später Ableitungen zeichnen kann, Kurvendiskussion, Integrale und und und...
Darum muss der Parser flexibel und auch möglichst performant sein. Folgendes habe ich mir gedacht und zum Teil auch schon umgesetzt:

Der Parser bekommt die Formel als String übergeben, im weiteren Term genannt. Dieser Term wird in seine Bestandteile zerlegt, wie Zahlen, Namen von Konstanten oder Funktionen, Klammern und Operatoren. Diese Elemente speichere ich in einer Liste, aus der sie zur Berechnung abgerufen werden. Das spart schon mal das ständige Neuaufdröseln des Terms bei der Berechnung in einer Schleife.

Vor der Berechnung überprüfe ich, ob für meinen Term Symbole definiert wurden, das sind Konstanten oder die Laufvariable, die vor der Eingabe des Terms vom User angegeben werden können. Wenn es diese Symbole gibt, ersetze ich deren Namen in meiner Liste der Term-Elemente mit den entsprechenden Werten. Gibt es eine Laufvariable, merke ich mir die Indizes in meiner Term-Liste, an denen die vorkommt. So kann ich später dort schnell den neuen Wert eintragen, z.B. bei einem Term wie "4*x^3+3*x^2-2*x+3". Dort gibt es vor der nächsten Berechnung an drei Stellen den aktuellen Wert für das x einzutragen.

Alles, was nach diesem Schritt noch in der Liste steht, sind Zahlen (Double), Operatoren (+, - *, /, ^), Klammern oder Namen von Funktionen, wie Sin oder Cos.
Jetzt macht sich eine Stackmaschine an die Arbeit, welche die Rechenregeln wie Punkt vor Strich und Klammerung kennt. Die Zahlen und Operatoren werden auf einen Variablen- und einen Operatoren-Stack gepusht und nach den Regeln von da abgeholt, ausgerechnet und Zwischenergebnisse wieder auf dem Stack abgelegt.
Das funktioniert inzwischen und wenn der Code vorzeigbar ist, bekommt ihr das im Showroom zum Testen angeboten.

Im Moment bastel ich an der Sache mit den Symbolen, also die zu speichern, zu bearbeiten und in den Term einzutragen.

Frage an die Mathematiker hier wäre, ob die von mir zur Zeit festgelegte Syntax für den Term korrekt ist?
Vorgegeben ist folgendes:
1. Um negative Zahlen immer eine Klammer, also "3*(-2)" statt "3*-2". Die Klammern um einzelne Zahlen entferne ich vor der Berechnung wieder aus der Termliste, aber es macht die Zerlegung des Terms sonst sehr viel komplizierter.
2. Keine implizite Multiplikation. Aus "3Sin(x)" wird der Name "3Sin", wenn dem kein Wert vorher zugewiesen wurde, fällt das irgendwann mit der Fehlermeldung "Unbekannter Operator" auf die Nase, weil dann versucht wird, eine Funktion namens "3Sin" zu berechnen.
3. Auf Funktionsnamen folgt immer eine öffnende Klammer, also "Sin(x)", statt "Sinx". Ihr ahnt es schon, Sinx würde als Name erkannt, wenn es dazu keinen definiertem Wert gibt... siehe Punkt 2.

Soweit ich den Inhalt der letzten Mathevorlesungen vor etwa 30 Jahren noch in Erinnerung habe, ist das korrekt. Sicher mögen sich manche mehr Bequemlichkeit bei der Eingabe wünschen, aber da wird es auch einen Dialog mit Buttons geben, in dem man sich den Term bequem zusammenklicken kann.

Gruß
Carbonunit

Sehr schön, die Umgekehrte Polnische Notation habe ich schon mal als Idee für die weitere Umsetzung notiert und so ganz nebenbei jetzt auch verstanden. Am Expression-Tree muss ich noch etwas herumdenken...

Ich habe hier ein paar garstige Formeln gefunden, mit denen mein Wunderwerk regelmäßig auf die Nase fällt. Konstrukte wie

(3-4^2)*1

oder

(2*2+2)*2

sind jeweils unterschiedlich zu behandeln. Kann ich jedem Parser-Bastler nur empfehlen, damit zu testen.
Vermutlich ist das sehr viel einfacher mit der Umgekehrten Polnischen Notation oder auch PostFix-Notation. Ich muss nur den Verschiebebahnhof bauen, um meine Tokens von InFix- zu PostFix-Notation umzurangieren. Diese Klammern nerven echt...
Der Code vom @ErfinderDesRades ist sicher super dafür, aber ich möchte mein Rad gerne selbst erfinden
Die Stacks für Operatoren und Zahlen als Abstellgleise gibt es ja schon, benutze ich die eben auch mal vor der eigentlichen Berechnung.

Ich denke mal, das gibt ein Re-Design. Ihr seid echt gut!
Folgendes ist angedacht: Die Token bekommen ein paar Eigenschaften mit auf den Weg, wie die Information, ob es eine Zahl ist oder nicht (Boolean), den Operatoren-Rang (im Moment 0 bis 4) und die Anzahl der Argumente, die der Operator braucht (0 bis 2).
Das Sortieren nach Operatoren-Rang muss ich moch überdenken, ich will es ja verstehen und nicht einfach abtippen.
Wenn dann alles in der korrekten PostFix-Notation abgelegt ist, wird es einfach: Operator holen, der sagt, wieviele Argumente er braucht, die auch holen, ausrechnen, Ergebnis auf den Stack, nächsten Operator holen, usw. bis Term Ende erreicht.
So verlagert sich die meiste Komplexität in den einmaligen Vorgang des Sortierens nach PostFix-Notation, danach kann da eine ziemlich dumme Rechenmaschine immer wieder drüberrattern, ich muss nur meine geänderte Laufvariable vorher an den richtigen Stellen eintragen.

Hier mal die Beschreibung meines Re-Designs etwas ausführlicher, auch um mir selber die Gedanken zu ordnen.

1. Eingabe des Terms. Wenn nötig, definiert der User vorher Symbole, die im Term verwendet werden sollen, zum Beispiel A = 3 oder x = 5. Die Eingabe des Terms erfolgt in InFix-Notation, weil die meisten User das so gewohnt sind, also zum Beispiel . Später kann es die Option geben, das alles in umgekehrt polnischer (PostFix-)Notation einzugeben für die absoluten Nerds.
Eingaberegeln bei InFix-Notation, wie im ersten Beitrag schon ausgeführt:
1.1. Negative Zahlen immer in Klammern
1.2. Funktionsargumente mmer in Klammern
1.3. Keine implizite Multiplikation, also statt immer .
Überlegungen dazu:
Leerzeichen erlauben? Die würde ich in einem der folgenden Schritte wieder eliminieren.

2. Zerlegung des Terms in Tokens
Tokens sind:
Operatoren "+-*/^", Klammern "()", Zahlen, Namen von Symbolen oder Funktionen
Die Tokens werden nach der Reihenfolge der Eingabe, also in InFix-Notation, in einer List(Of Tokens) gespeichert.
Es gibt dazu die OneToken-Klasse, welche die folgenden Eigenschaften des Tokens bei der Zuweisung festlegt:
TokenText - Inhalt des Tokens als String
TokenValue - Inhalt des Tokens als Double (0.0 wenn es keine Zahl ist)
TokenIsNumeric - Boolean, True wenn es eine Zahl ist
TokenOpRank - OperatorenRang des Tokens: 0 für "(", 1 für "+-", 2 für "*/", 3 für "^" und Funktionsnamen, 4 für ")", 5 für Zahlen
TokenArguments - Anzahl der Argumente, die der Operator zur Berechnung benötigt. Für Zahlen und Klammern ist der Wert Null,
für unäre Operatoren Eins und für binäre Zwei. Danach richtet sich, wieviele Argumente der Token vom Stack poppt in Schritt 6.

3. Eintragen der Werte an Stelle von Symbolen. Die Symbole und deren Werte (Beispiel: A = 3) werden vor der Eingabe des Terms vom User festgelegt. In diesem Schritt werden alle Tokens, deren Text-Repräsentation in der Liste der definierten Symbole gefunden wird, durch den numerischen Wert des Symbols ersetzt. Lediglich das als Laufvariable definierte Symbol erhält eine Sonderbehandlung. Dieses muss bis nach der Umsortierung in PostFix-Notation erhalten bleiben, um dann die Positionen der Laufvariablen in der Liste zu ermitteln und dort vor jeder Berechnung die geänderten Werte einzutragen. Bei Funktionen wie dieser: wird es später drei Stellen in der PostFix-Liste geben, an der die aktuellen Werte für x eingetragen werden müssen.
Nach diesem Schritt finden sich in der Token Liste: Die Laufvariable, zu behandeln als Zahl, konstante Zahlen, Funktionsnamen, Operatoren und Klammern

3. Entfernen von redundanten Klammern, also solchen um negative Zahlen ( - 34,56 ) oder um einzelne Zahlen wie bei Sin(4).

4. Neuordnung der Tokens-Liste von PostFix in InFix-Notation. An dem Schritt arbeite ich zur Zeit. Die vorher beschriebenen Schritte sind noch nicht komplett auf das neue Design umgestellt, mir ist aber klar, was da zu tun ist. Ich habe gesehen, dass es eine Stack(Of ...) Collection gibt. Die wird sicher gebraucht zur Zwischenspeicherung der Tokens bei deren Umrangieren von InFix zu PostFix. Der Vergleich mit einem Rangierbahnhof passt da sehr gut.
Wel jedes meiner Tokens seinen Rang kennt, kann ich sie danach umsortieren. Den Algorithmus dafür habe ich hier schon gesehen und wohl auch verstanden, ich will ihn aber selbst entwickeln, also quasi das Rad nochmal erfinden, der @ErfinderDesRades möge mir das verzeihen.
Nach der Neuordnung sollte der gesamte Term in PostFix-Notation vorliegen. Es finden sich darin die folgenden Arten von Tokens:
Zahlen, der Name der Laufvarablen, Operatoren

5. Alle Indizes, an denen in der PostFix-Notation der Name der Laufvariabken auftritt in einem Array speichern.

6. Zum Berechnen, auch in einer Schleife, den Wert der Laufvariablen an den in Schritt 5. ermittelten Stellen eintragen und die Berechnung starten. Dabei geht die Rechenmaschine durch die Liste der Tokens von links nach rechts, pusht alle gefundenen Zahlen auf den Stack, poppt von dort die nötige Anzahl an Argumenten, wenn ein Operator gefunden wird, berechnet diesen, pusht das Ergebnis auf den Stack etc, bis das Ende des Terms erreicht ist. Wenn alles gut gegangen ist, sollte das Ergebnis jetzt als einziger Wert auf dem Stack liegen.
Die Schritte 1. bis 5. werden dafür nur einmal ausgeführt, Schritt 6. in einer Schleife, wenn der Term eine Laufvariable enthält.

Überlegungen und Fragen dazu:
1. Meine OneToken-Klasse ermittelt bei jeder Zuweisung zur TokenText-Eigenschaft die übrigen Eigenschaften des Tokens neu. Das ist für Operationen in den Schritten 1 bis 5 nicht so relevant für die Performance, weil diese Schritte für jeden Term nur einmal ausgeführt werden. Im Schritt 6, also der eigentlichen Berechnung, kann das zu einem Thema werden, weil jetzt alles einige hundert- oder gar tausende Male ausgeführt wird und da macht jede Operation mehr sicher einen Unterschied.
Ich überlege also, die PostFix-Liste mit einer SimpleToken-Klasse aufzubauen, die nur noch die Eigenschaften TokenText, TokenValue und TokenArguments hat. Diese werden bei Zuweisung eines Tokens mit angegeben und nicht jedes Mal neu ermittelt. Bei TokenArguments = 0 wird TokenValue gelesen, sonst TokenText und TokenArguments bestimmt, wieviele Argumente das Token vom Stack poppt. Die Ermittlung der Eigenschaften erfolgt durch InStr-Vergleiche, ob mein Tokentext in einer bestimmten Konstanten gefunden wird. Oder kann man so etwas für die Performance vernachlässigen? Wahrscheinlich muss ich das testen.

Gruß
Carbinunit

So, der Rangierbahnhof für Tokens compiliert schon mal und funktioniert auch bei ersten Test, ohne auf die Nase zu fallen, aber es wird natürlich noch nicht richtig rangiert.

Ja klar, von wirklich "funktionieren" trennt mich und den Code noch einiges. Aber ich habe am offenen Herzen den Code von einem Konzept auf ein anderes umgestellt, da kann schon mal was vergessen werden. Bestimmt habe ich auch irgendwo noch was vertauscht, dass es fehlerfrei compiliert hat, erlaubte schon mal den Weg ins Heiabettchen.

Das Ganze sitzt in einem Test-Projekt, da kann ich mir den Inhalt der Tokenliste anzeigen lassen und wenn ich weiter umgestellt habe auch wieder den Inhalt des Rechenstacks. Das waren vorher zwei selbstgestrickte Stacks in einer Klasse, einer für Operatoren und einer für Variablen. Da gab es dann bei jedem Push oder Pop ein Event, in dem ich den aktuellen Inhalt des Stacks in einer Listbox angezeigt habe. Ich muss erstmal forschen, was die Stack(Of..) Klasse so bietet.
Wenn das dann mit ein paar fiesen Testformeln die Sache richtig auflöst, dann kommt ein Gerüst zum Testen drumherum und auch eine Berechnung in der Schleife mit geänderter Laufvariablen und Zeitmessung für weiteres Feintuning.
Zum automatischen Testen könnte ich den Term z.B an Excel schicken und mein Ergebnis mit dem von Excel vergleichen.

Nachdem ich mir diesen Link zu Wikipedia genauer angesehen habe, verstehe ich wohl besser, was mein Problem war.
Als alter Modellbahner kann ich natürlich mit einem Rangierbahnhof was anfangen. Ich dachte, man muss alle Waggons (sprich Tokens) über den Stack in die Ausgabe rangieren.
Das gilt aber nur für Operatoren. Die werden erst in das Stack-Gleis geschoben und dann daraus wieder, jetzt in umgekehrter Reihenfolge, an den Output-Zug (meine Postfix-Tokens) angekoppelt. Zahlen wandern direkt in die Ausgabe und nicht erst über den Stack.
Der Rangierbahnhof ist also ein Gleisdreieck mit dem InFix-Ast als Input, auf dem die Tokens (=Waggons) in InFix-Anordnung stehen, dem Stack-Ast, in den Operatoren vorwärts hineingeschoben werden und dem PostFix-Ast, in dem die Operatoren in PostFix-Anordnung stehen, also dem Output.

Nach diesem Beispiel müste dann 1 + 2 * 3 folgendermaßen umrangiert werden:
1. Die 1 direkt in den Output
2. Das + auf den Stack
3. Die 2 direkt in den Output
4. Das * auf den Stack
5. Die 3 direkt in den Output
6. Im letzten Schritt * und + in den Output. Da steht jetzt: 1 2 3 * +
Der Algorithmus zum Ausrechnen lädt jetzt alle Zahlen in den Stack, bis das erste Token gefunden wird, das keine Zahl ist. Jetzt liegen im Rechen-Stack von unten nach open 1 2 3. Wenn das * gelesen wird, holt der Operator 2 und 3 vom Stack, rechnet 6 aus und pusht das Ergebnis auf den Stack. Das Plus holt dann 6 und 1 vom Stack und rechnet beides zum Endergebnis 7 aus, das wieder auf dem Stack landet. Der Groschen scheint gefallen, muss jetzt mal coden...

Mit dem obigen Term "1 + 2 * 3" rechnet es schon mal richtig und sortiert auch die Tokens wie erwartet.
Das sagt natürlich noch nichts aus, dafür muss ich mehr testen, aber es ist ein erster Schritt mit besserem Ergebnis, als bisher.

Die Idee mit Excel als Vergleichsrechenmaschine, welche ja hier kritisiert wurde, hätte bei Umsetzung den Charme, dass ich die Vergleichsrechnung nicht erst hartcodieren muss. Ich tippe meinen Term ein, Excel rechnet das Ergebnis aus und mein Interpreter mit Namen Valf (nach einer Funktion auf meinem uralten CASIO-Taschenrechner) rechnet auch und dann wird verglichen. Wenns nicht stimmt, kommt ein Fehler ins Protokoll. Fällt mir ein neuer Term ein, ist der ohne vorheriges Coden gleich bereit zum Testen.
Ich kann dabei beliebigen Aufwand treiben, es steht kein Chef und kein Termin dahinter...

Bei dem Bild von dem Gleisdreieck in dem Wikipedia-Artikel war mir plötzlich alles klar und jetzt funktionierts anscheinend auch wie gewünscht. Muss natürlich noch eine Testmimik drumherum bauen.

Per Excel-Automation habe ich jetzt auch eine Referenz für das Ergebnis. Im Wesentlichen ein Sheet anlegen und darin den Term mit "=" davor eintragen an A1, Calculate aufrufen und den Value der Range ("A1", "A1") abrufen.

Was deeeennnn? Ich brauche doch irgendetwas, das meine Rechenergebnisse nachrechnen kann und das kann Excel ziemlich gut, nur bei den Funktionen ATN und SQR hakt es noch, weil die bei Excel anders heißen.