Entwickler-Ecke

Basistechnologien - Formel Parser

→Tobi - Sa 07.02.09 21:50
Titel: Formel Parser

Ich habe schon versucht ein solches Projekt umzusetzen. Also einen Parser in C#, der eine mathematische Gleichung auflöst. Ich habe zwar schon ein paar Grundkonzepte gefunden, aber noch nicht umsetzen können.

Also ich möchte zuerst die eingeklammerten Ausdrücke suchen. Diese muss ich dann ersetzen. Allerdings weiß ich da schon nicht weiter: Durch was soll ich diese ersetzen? Wie soll ich die ersetzen?

Also wenn ich beispielsweise die Zeichenkette "2 + 3 - (5 + 2)" habe. Ich wäre für einen konkreten Code dankbar.

CarpeDiem - Sa 07.02.09 22:03

Schau mal da! http://www.java-forum.org/de/viewtopic.php?t=13378

jaenicke - Sa 07.02.09 22:04

Was willst du jetzt eigentlich? Selbst einen Parser schreiben oder einen fertigen Code?
Fertige Parser findest du im Internet viele, z.B. hier:
http://www.bestcode.com/html/bcparser_net.html
http://www.codeproject.com/KB/cs/MathParser.aspx

→Tobi - Sa 07.02.09 23:05

Also der erste Link hat mir schon geholfen. Vom Verständnis her. Leider ist der Code in Java und ich weiß nicht ob es für jeden Befehl ein Synonym in C# gibt.

Ich möchte eigentlich einen eigenen Parser entwickeln.

Kennt jemand eine Übersicht über die Operatoren und Methoden von Strings?

Edit: Ok. Dumme Frage. Wofür gibts IntelliSense.

→Tobi - So 08.02.09 12:48

Weiß jemand wie ich die Zahl vor und nach einem bestimmten Zeichen bestimmen kann, diese einklammere oder etwas in der Art. Zum Beispiel:

( 200 - ( 25 + 15 * 5 ) ) --> ( 200 - ( 25 + ( 15 * 5 ) ) )

Kha - So 08.02.09 14:00

Hab mir den Java-Artikel nicht durchgelesen, aber da müsste das doch behandelt werden?
Wobei die String-Ersetzen-Methode natürlich etwas naiv ist; falls du tiefer in die Materie eintauchen willst, könntest du dir ein Skript anschauen, das user profile icon

miniC# vor kurzem gepostet hat: http://www.itu.dk/people/kfl/parsernotes.pdf (kein Java :mrgreen: )

→Tobi - So 08.02.09 14:04

Ich hab schon ne Idee: mit einer Schleife das nächste Zeichen links und rechts vom gesuchten Zeichen suchen und diesen Teil ( zwei Zahlen und ein Zeichen ) einklammern und ausrechnen lassen. Das Suchen nach den beiden Zeichen mach ich wie gesagt mit einer Schleife und einem Vergleich des jeweiligen Zeichens mit einem Array, in dem die definierten Zeichen ( Rechenoperatoren ) enthalten sind.

Alles noch Theorie. Aber ich werds versuchen.

Welchen Namen hat eigentlich die Vorgehensweise dieses Algorithmus?

Kha - So 08.02.09 15:13

→Tobi hat folgendes geschrieben :

Welchen Namen hat eigentlich die Vorgehensweise dieses Algorithmus?

Ich glaube nicht, dass es einen gibt. Alle Standardalgorithmen suchen nicht gezielt nach einem Token wie "*", sondern gehen stur von links nach rechts (nämlich LL oder LR) durch die Eingabe. Der einfachste standardmäßige Parser für mathematische Terme ist ein Recursive Descent (bzw. Predictive) Parser [http://en.wikipedia.org/wiki/Recursive_descent_parser], wird wahrscheinlich auch in dem Skript von oben verwendet.

AdrianK - So 08.02.09 17:14

Hallo, ich entwickle gerade auch einen Formelparser in C# und ich hab's so gelöst:
Als erstes wird der Term in eine List<String> aufgeteilt, z.B. so:

Quelltext

1:
2:

3+43*5 =
[3][+][4][3][*][5]

Danach werden Zahlen und Kommas zusammengefasst:

Quelltext

1:	[3][+][43][*][5]

Jetzt ist es kein Problem mehr den Term zu berechen, einfach nach allen *, /, + und - suchen und sie berechen. Ungefähr so:

C#-Quelltext

1:
2:
3:
4:

int position = term.IndexOf("*");
term[position-1] = Convert.ToString(Convert.ToDouble(term[position-1])*Convert.ToDouble(term[position-1]));
term.RemoveAt(position);
term.RemoveAt(position);

Mit Rekursion sind dann auch Klammern kein Problem mehr. Hoffe ich konnte dir helfen :)

JüTho - So 08.02.09 17:27

@Adrian
Das Verfahren gefällt mir überhaupt nicht, weil ständig zwischen String und Zahl konvertiert werden muss; beachte außerdem die "zwangsläufigen" Rundungsfehler bei Berechnungen mit double.

Wenn überhaupt, dann sind zwei Listen zu verwenden: List<decimal> mit den Zahlen und List<char> mit den Rechenzeichen und Klammern. Aber vermutlich gibt es in den vielen Links gute/bessere Vorschläge.

Gruß Jürgen

→Tobi - So 08.02.09 20:04

Mhh... Ja, die Idee hatte ich auch schon. Ich war mir nur nicht ganz sicher wie ich dann die drei Elemente im Array durch eines, nämlich das Ergebnis ersetze. Wobei ich natürlich nicht ständig mit diesem Array arbeiten muss. Ich müsste es nur nach jedem Durchgang (zwei Zahlen miteinander verrechnen) neu bilden. Dauert das nicht ziemlich lange?

Wenn nicht: Gute Idee. Wäre einen Versuch wert, vor allem weil es mein erster konkreter Ansatz mit Beispielcode wäre.

Danke.

JüTho - So 08.02.09 21:15

→Tobi hat folgendes geschrieben :

Ich war mir nur nicht ganz sicher wie ich dann die drei Elemente im Array durch eines, nämlich das Ergebnis ersetze. Wobei ich natürlich nicht ständig mit diesem Array arbeiten muss. Ich müsste es nur nach jedem Durchgang (zwei Zahlen miteinander verrechnen) neu bilden. Dauert das nicht ziemlich lange?

Richtig. Deshalb solltest Du auch keinesfalls Arrays verwenden, sondern List<T>, wo Du jederzeit Elemente entfernen und z.B. 2 Zahlen durch das Ergebnis der aktuellen Teilrechnung ersetzen kannst (genauer: eine Zahl wird durch das Ergebnis ersetzt, die zweite Zahl gestrichen, der Operator in der zweiten Liste ebenfalls).

Jürgen

UGrohne - So 08.02.09 22:12

Mal ein kleiner Hinweis am Rande: Vor ein paar Tagen bin ich einige C#-Features durchgegangen und da sind mir Ausdrucksbäume aufgefallen. Und ich habe mir so gedacht, dass sich das eventuell eignen würde, einen eigenen Formelparser zu schreiben.

Vielleicht will sich ja mal jmd mit dem Thema beschäftigen und das erruieren?! ;)

Kha - So 08.02.09 23:43

Expression Trees, hach... Ja, da hab ich schon länger etwas geplant :mrgreen: . Projekt Abi hat aber leider erstmal höhere Priorität :( .
Zur Klarstellung: Beim Parsen helfen die nichts. Der große Nutzen liegt im eingebauten LCG[meta]Lightweight Code Generation - DynamicMethod[/meta]-Compiler, mit dem sich ein interessanter kompilierender Matheparser bauen lassen sollte.

UGrohne - Mo 09.02.09 09:45

Kha hat folgendes geschrieben :

Yapp, genau daran dachte ich nämlich auch ... aber die Zeit ... die fehlt einfach immer :(

jaenicke - Mo 09.02.09 11:11

Kha hat folgendes geschrieben :

Der große Nutzen liegt im eingebauten LCG[meta]Lightweight Code Generation - DynamicMethod[/meta]-Compiler, mit dem sich ein interessanter kompilierender Matheparser bauen lassen sollte.

Ja, das geht. Als ich das hier gelesen hatte und MSDN über Expression Trees [http://msdn.microsoft.com/en-us/library/bb397951.aspx] befragt hatte, habe ich mich vorhin mal drangesetzt und das ausprobiert. Jetzt (2 Stunden später ;-)) habe ich das so weit verstanden und einen Parser hinbekommen, der die Grundrechenarten ohne Klammern oder Punkt vor Strich in einen Expression Tree übersetzt und dann mit verschiedenen Variablenwerten gefüttert werden kann. :mrgreen:
Ich überlege noch wie ich die Variablenwerte einfacher in der GUI einfüttern lassen kann (also variabel was die Anzahl etc. angeht).

Leider fehlen mir noch etliche Kenntnisse in C#, deshalb habe ich ein wenig Probleme mit einer guten Umsetzung. Z.B. wusste ich bis heute Morgen auch nicht was delegates sind, wie ich Eigenschaften genau definiere, usw., aber ich werde im Laufe des Tages vielleicht noch ein wenig Zeit haben da weiter zu basteln und dann das Ergebnis posten. ;-)

AdrianK - Mo 09.02.09 17:24

→Tobi hat folgendes geschrieben :

Geht nicht sehr lange: einfache Berechnungen auf nem P4 2,4 Ghz (z.B. 3^2,43345+4,345) unter 1ms, kompliziertere mit mehreren klammern etc. so um die 10-30ms.

→Tobi - Mo 09.02.09 18:04

Danke für die vielen guten Antworten.

Also ich denke ich gebe meine Idee mit dem Parser, der nach den Zeichen mit höchster Priorität sucht auch. Der ist doch sehr viel komplizierter zu realisieren als ich dachte. Ich habe es jetzt endlich mit Mühe und Not geschafft eine halbwegs funktionierende Punkt-Vor-Strich-Rechnung zu integrieren. Aber der Code ist bestimmt 300 Zeilen lang und absolut verbugt. Außerdem denke ich, dass die andere Methode effektiver ist (sonst hätte man meine Idee ja schon irgendwann mal umgesetzt ^^).

Also noch mal zusammenfassend:

Ich erzeuge eine Variable Liste mit Strings, die dann nach und nach in das Ergebnis umgeformt wird. Diese Liste geht der Parser durch. Wenn er nun eine öffnende Klammer findet geht fängt er dort erst mal an sie zu lösen. Wenn er eine Buchstabenkette findet, überprüft er ob damit eine Funktion (z.B. Sinus) gemeint ist, oder eine Variable.

Was genau ist so ein LCG-Compiler? Ist der für einen simplen Compiler wichtig? (Ich will überhaupt erst mal einen hinbekommen!^^)

Das ist zwar noch sehr, sehr hochgegriffen - aber wäre es möglich ein Programm zu schreiben, dass eine Formel vereinfacht? Zum Beispiel "225x - 175x + (-45x)". Der Zweck meines Programms ist nämlich einen Graphen zu zeichnen. Und der Parser soll später für ein bestimmtes Intervall die y-Werte in Abhängigkeit von x bestimmen. Da wäre eine verkürzte Formel ja wesentlich effektiver.

Also dann werd ich mal versuchen diese Idee umzusetzen.

jaenicke - Mo 09.02.09 18:13

→Tobi hat folgendes geschrieben :

Was genau ist so ein LCG-Compiler? Ist der für einen simplen Compiler wichtig? (Ich will überhaupt erst mal einen hinbekommen!^^)

Sowas brauchst du nicht, du kannst es auch einfacher machen. ;-)
Und das hat mit dem Parsen auch nichts zu tun sondern danach mit der Auswertung.

AdrianK - Mo 09.02.09 18:16

Das mit dem Sin Cos Tan Rnd etc. kannst du vereinfachen, indem du bevor du irgendwas berechnest die Sinuse usw. durch z.b. S ersetzt. Meinen Parser nutze ich übrigens auch um Graphen zu zeichnen.

→Tobi - Mo 09.02.09 18:35

Ok. Also wenn ich nun anfange die Elemente der Liste mit den ganzen Zeichen zusammenzufassen - also "2", "6", "+", "7" wird zu "26", "+", "7" - wie mach ich das am besten? Eine Möglichkeit wäre ja ein Zahlenarray festzulegen, zu prüfen ob das Zeichen in diesem enthalten ist - also eine Zahl ist. Wenn das bei aufeinanderfolgenden Zeichen zutrifft, werden sie zusammengefügt. Meine Frage: Gibt es einen schnelleren Weg?

AdrianK - Mo 09.02.09 18:41

Dazu hab ich mir eine kleine Funktion CheckNumber geschrieben (Char.IsNumber)
Das ersetzen machst du einfach mit List.Repleace

→Tobi - Mo 09.02.09 18:51

Genau so etwas habe ich gesucht! Eben eine Funktion wie 'Char.IsNumber()'.

JüTho - Mo 09.02.09 19:09

→Tobi hat folgendes geschrieben :

Genau so etwas habe ich gesucht! Eben eine Funktion wie 'Char.IsNumber()'.

Na sowas, wieso hast Du das nicht selbst schnell gefunden? Ein Blick in die SDK-Doku/MSDN unter "Char-Struktur / Alle Member" liefert u.a. IsNumber und IsDigit. Jürgen

Kha - Mo 09.02.09 19:17

JüTho hat folgendes geschrieben :

Na sowas, wieso hast Du das nicht selbst schnell gefunden?

Na, zur Verteidigung: Nenne mir einen Grund, warum diese komische Methode statisch ist ;) . Aber Google sollte natürlich ebenso schnell zur gleichen Methode führen.

JüTho - Mo 09.02.09 20:03

Kha hat folgendes geschrieben :

Nenne mir einen Grund, warum diese komische Methode statisch ist

Weil MS bei manchen Sachen gewürfelt hat, wie es zu realisieren ist? Jürgen

→Tobi - Mo 09.02.09 21:42

Also für alle die auf der Suche nach der Lösung für einen Parser sind (so wie ich). Hier kommt Teil 1: Das Spalten der Eingabe in Zahlen und Rechenzeichen: (für die Konsole)

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Parser
{
    class Program
    {
        static void Main(string[] args)
        {
            // Version 0.01 - Eingabe verarbeiten

            int i = 0;
            String Term = "";
            List<String> Teile = new List<string>();
            bool IstZahl = false;

            Term = Console.ReadLine();

            // Eingabe in ein dynamisches Array schreiben
            for (i = 0; i < Term.Length; i++)
            {
                Teile.Add(Term.Substring(i, 1));
            }

            // Array durchlaufen und Zahlen verknüpfen
            for (i = 0; i < Teile.Count; i++)
            {
                if (Char.IsNumber(Teile[i], 0))
                {
                    if (IstZahl)
                    {
                        Teile[i] = Teile[i - 1] + Teile[i];
                        Teile.RemoveAt(i - 1);
                        i--;
                    }
                    IstZahl = true;
                }
                else
                {
                    IstZahl = false;
                }

            }

            Console.ReadLine();
        }
    }
}

Ich hoffe es macht niemandem etwas aus, dass ich hier eine Art schrittweise Anleitung schreibe. Ich meine es wäre wohl nicht sinnvoll wenn ich direkt ein ganzes HowTo schreibe. Aus dem einfachen Grund, dass ich es selbst noch nicht kann^^. Also ergänze ich einfach immer den vorherigen Code mit meinem neuen Wissen - gewonnen aus den Kommentaren.

Man bin ich ein toller Autor! ^^

JüTho - Di 10.02.09 11:36

Hallo,

für alle, die hier Kommentare schreiben wollen: Ich wollte eigentlich wie folgt eine Änderung vorschlagen.
*******************************************************************

die erste for-Schleife und die List<string> kannst Du Dir schenken:

C#-Quelltext

1:
2:
3:
4:
5:

// Eingabe in ein dynamisches Array schreiben
for (i = 0; i < Term.Length; i++)
{
    Teile.Add(Term.Substring(i, 1));
}

Ein String kann auch wie ein char-Array behandelt werden. Du kannst also an allen folgenden Stellen (wie im folgenden Ausschnitt) Teile bzw. Teile[i] durch Term bzw. Term[i] ersetzen:

C#-Quelltext

1:
2:
3:
4:

// Array durchlaufen und Zahlen verknüpfen
for (i = 0; i < Term.Length; i++)
{
    if (Char.IsNumber(Term[i]))

*******************************************************************
Aber diese Änderung bringt nichts. Tobi möchte die Zahlen in der List<string> zusammensetzen und zwischenspeichern. Für dieses Verfahren braucht er natürlich Strings und kann nicht (wie mein Ansatz) mit Chars auskommen.

Ich würde es nicht so machen, sondern so schnell wie möglich die Substrings in "echte" Zahlen konvertieren. Aber es ist ein möglicher Weg; dann bringt die "Verkürzung" über Term[i], d.h. den String als char-Array zu behandeln, nichts.

Jürgen

Th69 - Di 10.02.09 16:26

Sorry, aber ich kriege immer die Krise, wenn irgendwelche Halbprofis versuchen, selber einen Parser zu entwickeln.

Zuersteinmal sollte man sich mit dem Begriffen "EBNF (Enhanced Backus Naur Form)" und "Grammatik" auseinandersetzen und daraus dann einen möglichst einfachen Parser entwickeln (z.B. Top-Down 1 Step-Ahead). Unter C++ würde ich dafür jetzt 'boost.spirit' empfehlen, aber leider gibt es so etwas noch nicht für C#.

Das ganze Rumfrickeln mit Strings und Klammerung etc. führt meistens immer in eine Sackgasse, da die Operator-Prioritäten ja auch noch bedacht werden müssen...

PS: Einen Beispielparser (in C++ mit dem BCB entwickelt) könnt ihr euch mal unter http://www.bitel.net/dghm1164/downloads/FctParser-Sources.zip ansehen.

Noch ein PS:

Zitat:

Das ist zwar noch sehr, sehr hochgegriffen - aber wäre es möglich ein Programm zu schreiben, dass eine Formel vereinfacht? Zum Beispiel "225x - 175x + (-45x)".

Hierfür reicht ein Parser nicht aus, sondern dann benötigt man den schon erwähnten Expression Tree. Und anhand von Rechenregeln werden dann Baum-Umformungen durchgeführt und zum Schluß erst wieder in einen Text zurücktransformiert. So ein Programm habe ich damals als Studi (noch in C) geschrieben, jedoch den Source irgendwo zuhause auf einem Rechner (bei Interesse könnt ich ihn ja mal rauskramen...)

jaenicke - Di 10.02.09 18:08

Th69 hat folgendes geschrieben :

Zuersteinmal sollte man sich mit dem Begriffen "EBNF (Enhanced Backus Naur Form)" und "Grammatik" auseinandersetzen und daraus dann einen möglichst einfachen Parser entwickeln (z.B. Top-Down 1 Step-Ahead).

Ja, sowas habe ich im Studium gelernt. Das war eine der (fand ich) schwereren LV. :mrgreen:

Th69 hat folgendes geschrieben :

Ja, mit dem Expression Tree werkele ich gerade ein wenig herum. Sowas hatte ich letztlich vor. Wenn man das richtig macht, dauert das aber ne Weile, vor allem, wenn man C# noch nicht so gut kennt. ;-)

Aber ich arbeite mich gerade in C# und parallel PHP besser ein, da ist das ne ganz gute Übung, weil es auch interessant ist.

→Tobi - Mo 16.02.09 22:32

Nun gut. Hier kommt endlich der zweite Teil: Strichrechnung mit Klammern. Ich weiß - es gibt bestimmt ein Dutzend Möglichkeiten es besser zu machen. Und über Verbesserungsvorschläge bin ich auch dankbar. Sie sollten bloß in den Grenzen des Machbaren für einen Schüler liegen ^^.

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Parser
{
    class Program
    {
        static void Main(string[] args)
        {
            // Version 0.02 - Strichrechnung

            int i = 0, Anfang = 0;
            String Term = "";
            List<String> Teile = new List<string>();
            bool IstZahl = false;
            double Zahl1 = 0, Zahl2 = 0, Ergebnis = 0;

            Term = Console.ReadLine();

            // Eingabe in ein dynamisches Array schreiben
            for (i = 0; i < Term.Length; i++)
            {
                Teile.Add(Term.Substring(i, 1));
            }

            // Array durchlaufen und Zahlen verknüpfen
            for (i = 0; i < Teile.Count; i++)
            {
                if (Char.IsNumber(Teile[i], 0))
                {
                    if (IstZahl)
                    {
                        Teile[i] = Teile[i - 1] + Teile[i];
                        Teile.RemoveAt(i - 1);
                        i--;
                    }
                    IstZahl = true;
                }
                else
                {
                    IstZahl = false;
                }

            }

            // Strichrechnung
            while (Teile.Count > 1)
            {
                try
                {
                    if (Teile[Anfang + 2] == "(")
                    {
                        Anfang += 3;
                        continue;
                    }
                }
                catch
                {
                }

                if (Teile[Anfang + 1] == ")")
                {
                    Teile.RemoveAt(Anfang - 1);
                    Teile.RemoveAt(Anfang);
                    Anfang = 0;
                    continue;
                }
                Zahl1 = Convert.ToDouble(Teile[Anfang]);
                Zahl2 = Convert.ToDouble(Teile[Anfang + 2]);
                if (Teile[Anfang + 1] == "+") Ergebnis = Zahl1 + Zahl2;
                if (Teile[Anfang + 1] == "-") Ergebnis = Zahl1 - Zahl2;
                Teile[Anfang + 2] = Convert.ToString(Ergebnis);
                Teile.RemoveAt(Anfang);
                Teile.RemoveAt(Anfang);
            }

            Console.WriteLine(Teile[0]);
            Console.ReadLine();
        }
    }
}

Es gibt nur ein paar kleine Hacken:
- Man darf die gesamte Rechnung nicht in Klammern schreiben.
Bsp: (12+(12-35+(35+4))). Richtig wäre: 12+(12-35+(35+4))
- Klammern müssen richtig gesetzt werden. Man darf auch keine weglassen

Klar. Das sind Kleinigkeiten, die man leicht beheben kann. Sie machen den Code bloß unnötig unübersichtlich. Darum habe ich sie weggelassen. Über einen Try-Block um die Schleife wäre allerdings noch mal nachzudenken damit das Programm bei falscher Eingabe nicht einfach den Geist aufgibt. :)

Th69 - Mo 01.06.09 12:44

Ich habe nun auch meinen Formel-Parser nach C# übersetzt:
http://www.mycsharp.de/wbb2/thread.php?postid=3545284#post3545284
(gesamte Projekt als Dateianhang im Hauptbeitrag)

Dieser darf dann gerne als Referenzprojekt angesehen werden...

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!