Laden...

klitzekleiner Formelparser (mit RegEx und viel Lambda/LINQ)

Erstellt von zommi vor 14 Jahren Letzter Beitrag vor 13 Jahren 10.356 Views
zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren
klitzekleiner Formelparser (mit RegEx und viel Lambda/LINQ)

Beschreibung:
In letzter Zeit hab ich mich mehr mit Lambdas und LINQ beschäftigt. Darüberhinaus auch noch mit RegularExpressions. Und dort haben mich insbesondere die Gruppierungskonstrukte in .Net begeistert. Man kann sogar gefundene Gruppen auf virtuelle Stacks packen und wieder herunternehmen.
Somit kann man weit mehr erfassen, als nur reguläre Sprachen !
(Das macht auch das Erkennen von Klammerparen möglich - wie genau, zeigt exemplarisch das Ausgleichsgruppen - Beispiel auf msdn)

Und als erster Test wurde ein Formelparser draus:


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

namespace MathParser
{
    internal delegate double OpMethod(params double[] obj);

    internal struct Op
    {
        public Op(string n, string s, OpMethod m) { Name = n; Sign = s; Method = m; }
        public Op(string n, OpMethod m) :this(n,null,m) {}

        internal string Name; // Operatorname
        internal string Sign; // Infix-Operator-Zeichen
        internal OpMethod Method; // Methoden-Delegat
    }

    public abstract class Term
    {
        // Liste der bekannten Operationen (Infix-Operatoren nach dem Rang geordnet)
        static Op[] ops = new Op[]
        {
            new Op("pow", "^", (xs) => Math.Pow(xs[0],xs[1]) ),  
            new Op("mul", "*", (xs) => xs[0] * xs[1] ),  
            new Op("div", "/", (xs) => xs[0] / xs[1] ),  
            new Op("add", "+", (xs) => xs[0] + xs[1] ),  
            new Op("sub", "-", (xs) => xs[0] - xs[1] ),  
       
            new Op("sin", (xs) => Math.Sin(xs[0]) ),   
            new Op("cos", (xs) => Math.Cos(xs[0])),   
            new Op("tan", (xs) => Math.Tan(xs[0])),   
            new Op("sqrt", (xs) => Math.Sqrt(xs[0])),   
            new Op("sign", (xs) => Math.Sign(xs[0])),   
            new Op("ln", (xs) => Math.Log(xs[0])),   
            new Op("exp", (xs) => Math.Exp(xs[0])),   
            new Op("max", (xs) => Math.Max(xs[0], xs[1])),   
            new Op("min", (xs) => Math.Min(xs[0], xs[1])),   
            new Op("", (xs) => xs[0]),   
        };

        static string infixPattern =    @"^((:question:(?<O>\()|(?<-O>\))|[^\(\)])*)\s*(?(O)(?!)|{0})\s*(.*)$";
        static string praefixPattern =  @"^(?<name>[a-z]*)\((?<tail>.*)\)$";
        static string commaPattern =    @"(?<=(:question:(?<O>\()|(?<-O>\))|(?(O)[^\(\)]|[^\(\),]))*)(?(O)(?!)),";
        static string variablePattern = @"^[a-z]+(?![a-z\(])$";

        public static Term Parse(string s)
        {
            // 0.   Vorverarbeitung
            //      Infix Operatoren der höchsten Ebene in Präfix umwandeln
            //      (Infix Ops müssen zwangsläufig zwei-parametrig sein)
            foreach (Op o in ops.Reverse().Where((x) => x.Sign != null)) 
            {
                string opPattern = String.Format(infixPattern, Regex.Escape(o.Sign));
                s = Regex.Replace(s, opPattern, String.Format("{0}($1,$2)", o.Name));
            }

            // Ausgabe hier, zeigt den ParseBaum
             Console.WriteLine(s);

            // 1.   Eigentlichtes Parsen
            // 1.a) check ob Operation
            Match m = Regex.Match(s, praefixPattern);
            if (m.Success)
            {
                // neuen OperatorTerm erzeugen
                Operation result = new Operation();
                // konkreten Operationstyp zuweisen (anhand des Namens finden)
                result.O = ops.First((x) => (x.Name == m.Groups["name"].Value));
                // Parameter parsen (an Kommata splitten und einzeln parsen)
                result.SubTerms = Regex.Split(m.Groups["tail"].Value, commaPattern)
                                       .Select((x) => Parse(x))
                                       .ToArray();

                return result;
            }

            // 1.b) check ob Zahl
            double value;
            if (Double.TryParse(s, out value))
                return new Constant(value);

            // 1.c) check ob Variable
            if (Regex.IsMatch(s, variablePattern))
                return new Variable(s);

            // 1.d) sonst 0
            return new Constant(0);
        }

        public double Eval(params double[] xs)
        {
            // internes Eval aufrufen mit ausschließlich ungebundenen Variablen
            return Eval(new Dictionary<string, double>(), new Queue<double>(xs));
        }

        internal abstract double Eval(Dictionary<string, double> boundXs, Queue<double> unboundXs);
    }

    internal class Operation : Term
    {
        internal Op O;
        internal Term[] SubTerms;
        public override string ToString()
        {
            if (O.Sign != null) // falls Infix-Notation möglich
                return String.Join(O.Sign, SubTerms.Select((x) => x.ToString()).ToArray());
            else // sonst Prefix-Notation
                return String.Format("{0}({1})", 
                    O.Name, 
                    String.Join(",", SubTerms.Select((x) => x.ToString()).ToArray()));
            
        }
        internal override double Eval(Dictionary<string, double> boundXs, Queue<double> unboundXs)
        {
            return O.Method(SubTerms.Select((x) => x.Eval(boundXs, unboundXs)).ToArray());
        }
    }

    internal class Constant : Term
    {
        internal double Value;
        internal Constant(double v) { Value = v; }
        public override string ToString() { return Value.ToString(); }
        internal override double Eval(Dictionary<string, double> boundXs, Queue<double> unboundXs) 
        { return Value; }
    }

    internal class Variable : Term
    {
        internal string Name;
        internal Variable(string n) { Name = n; }
        public override string ToString() { return Name; }
        internal override double Eval(Dictionary<string, double> boundXs, Queue<double> unboundXs) 
        {
            // prüfen ob Variable bereits vergeben, sonst nächste schnappen
            if (!boundXs.ContainsKey(Name))
                boundXs.Add(Name, unboundXs.Dequeue());

            return boundXs[Name];
        }
    }
}

Also für nen Formel-Parser find ichs schon kompakt 🙂
Verwenden kann man ihn dann einfach per:


            string s = "sin(34-45)*54 +  45-(-34*x-exp(y-4))";

            Term t = Term.Parse(s);

            Console.WriteLine(t.ToString());
            Console.WriteLine(t.Eval(1, 5)); // Variablen in der Reihenfolge wie im string

            Console.ReadKey();

Weitere Beschreibungen folgen noch...

beste Grüße
zommi

Formel, Mathe, Parser, Regular Expressions

4.930 Beiträge seit 2008
vor 14 Jahren

Hey, da macht mir ja einer (wirklich) Konkurrenz -) Parser für mathematische Formeln

Könntest du mal schauen, wie performant deine Version ist (im Vergleich zu meiner - einfach mal mein Testprogramm aufrufen / anschauen)?
Und mal mit einigen Formeln testen... (durch die Optimierung von konstanten Ausdrücken wie z.B. bei deiner Testformel habe ich immer noch Vorsprung, aber das kannst du mal außen vor lassen -)

zommi Themenstarter:in
1.361 Beiträge seit 2007
vor 14 Jahren

Hier nun erstmal eine kleine Erklärung des obigen Codes.
(Wenn ich mich selbst nicht intensiv wieder in die RegExs reindenke, versteh ich sie nämlich auch selbst nich mehr 🙂)

Funktionsweise FormelParser:
Die fertig geparsete Formel ergibt einen Baum, bestehend aus Termen, von denen jeder Knoten entweder eine Variable, eine Konstante oder eine komplexere Operation ist, welche wiederum aus TeilTermen als Parametern besteht. (also wie immer)

Die Schwierigkeit beim Parsen ist bekanntlich das korrekte Entflechten der verschachtelten Strukturen (Klammerpaare) sowie das Erkennen der Operationen selbst, wobei auch Infix-Notationen möglich sein sollen.

Das Parsen läuft in zwei Schritten ab:

0. Vorverarbeitung
Die möglichen Infix-Operationen auf der höchsten Ebene werden in Präfix-Notation umgeformt: Also aus "14*x + cos(x/2)" wird "add(14, cos(x/2))". Hierbei muss natürlich die Operator-Rangfolge beachtet werden, was durch die Reihenfolge des Schleifendurchlaufs aber bereits korrekt erfolgt.

**1. Term-Erkennung (Operation / Variable / Konstante)***Da zuvor stets in Präfx-Notation umgeformt wurde, sehen die komplexen Operationen immer so aus "<name>(<param1>,<param2>,...)". Dies wird erkannt, anhand des Namens die Operation ermittelt und jeder Parameter für sich wiederum geparset. *Wenn es keine komplexe Operation ist, könnte es eine Zahl sein, was uns Double.TryParse sagt. *Wenn es weder eine Operation, noch einer Zahl ist, könnte es eine Variable sein, falls es ein Wort mit mindestens einem [a-z] ist. *Sonst wird "0" angenommen. Dies ermöglicht bisher die unären Operationen "-x" und "+x", da diese dann als "0-x" und "0+x" geparsed werden. Das ist aber noch nicht wirklich schön.

Funktionsweise der Regular Expressions:
Mit den RegEx-Erweiterungen des .NET-Frameworks lässt sich ziemlich zaubern. 8)
Normalerweise können Reguläre Ausdrücke ja nur Wörter aus Regulären Sprachen matchen. Ein bekanntes Beispiel, das keine reguläre Sprache ist, ist die Menge der Wörter

{a[sup]n[/sup]b[sup]n[/sup]} = {e, "ab", "aabb", "aaabbb", ...}

Denn dies ist eine kontextfreie und keine reguläre Sprache.
Das geht normalerweise mit regulären Ausdrücken nicht, aber in .NET schon!
Beginnen wir simpel mit dem RegEx ab
matched leider auch Wörter, die wir nicht wollen, da die Anzahl der as und bs nicht berücksichtigt wird. So gehts als nicht.

Aber schauen wir uns an, was .NET uns noch zur Verfügung stellt:
(Vieles davon ist unter [Artikel] Regex-Tutorial oder auch bei Sprachelemente für reguläre Ausdrücke nachzulesen)

Unbenannte Gruppen
(_[/b]subexpression[/i])
* ist eine Gruppierung innerhalb des RegEx, deren SubMatch später mit Match.Groups[0...].Value erfragt werden kann.

Benannte Gruppen
(?<_[/b]name[/i]>_[/b]subexpression
*[/i])** ist eine benannte Gruppe, die wiederum mit Match.Groups["name"].Value erfragt werden kann.
Zudem ist diese benannte Gruppe intern eigentlich ein Stack mit allen Treffern, die sie gefunden hat, was man auch über Match.Groups["name"].Captures ermitteln kann. Eine benannte Gruppe legt also den Teilmatch auch gleich auf den gleichnamigen Stack.

"negative" Gruppen
(?<-_[/b]name[/i]>_[/b]subexpression
*[/i])** macht genau das umgekehrte, es entfern das oberste Element des "name"-Stacks, sofern der Teilausdruck matched. (deshalb dürfen Gruppennamen auch nicht mit '-' beginnen)
*Positive und negative Lookarounds
(?=...) und (?!...) sowie (?≤...) und (?<!...) sind positives/negative Look-Aheads bzw Look-Behinds. Sie überprüfen, ob der SubRegEx davor/danach auftritt/nicht auftritt, aber ohne ihn in den resultieren Match aufzunehmen.

Um beispielsweise in einem Quellcode alle Anführungszeichen zu finden (für Stringerkennung), die jedoch nicht esacped sein dürfen (also keine '&quot;'), lassen sich super negative Look-Behinds nutzen. So prüft (?<!\) ob vorher _kein _Backslash auftrat. Somit gibt uns (?<!\)&quot; einen Match bei jedem "echten" Anführungszeichen.

*Leerer Regex
Der leere Regex "" matched immer. (das leere Wort Epsilon, kann eben überall gefunden werden)
Somit würde ein positive Look-Ahead nach dem leeren Wort ebenfalls immer erfüllt sein.
Somit ist (?=++++) immer erfüllt und könnte eigentlich weggelassen werden. Im Umkehrschluss bedeutet das, dass der negative Look-Ahead nach dem leeren Wort immer fehlschlägt, also (?!) nie erfüllt sein kann.

Alternativen
(?++++(_[/b]name[/i])_[/b]yesSubexpression
*[/i]|_[/b]noSubexpression**[/i])** ist so ein alternativer RegEx. Sie entspricht dem "yesSubexpression"-Teil, wenn die benannte Aufzeichnung eine Übereinstimmung hat. Andernfalls entspricht es dem "noSubexpression"-Teil. Oder in Stack-Sprech: je nachdem , ob der "name"-Stack leer ist oder nicht.

Nehmen wie also

(?[U][/U](stackname)a|b)

, was je nachdem, ob der "stackname"-Stack Elemente enthält oder nicht nach einem "a" oder einem "b" sucht, so können wir diesen anpassen, dass er immer matched, wenn der Stack leer ist, aber nie matched, wenn der Stack elemente enthält.
Nämlich (?(stackname)(?!)|(?=)), oder vereinfacht, also ohne else-Teil (?++++(stackname)(?!)).[/list]

Und mit diesen Hilfsmitteln können wir per RegEx nach anbn suchen.
mit (?<temp>a)+ packen wir bei jedem 'a' dieses auf den "temp"-Stack.
Mit (?<-temp>b)+ entfernen wir bei jedem 'b' ein Element vom "temp"-Stack.
Und mit (?++++(temp)(?!)) lassen wir den Match immer fehlschlagen, falls der Stack nicht-leer ist. (also unterschiedliche viele As und Bs vorhanden waren)

(?<temp>a)+(?<-temp>b)+(?[U][/U](temp)(?!))

Zurück zum Parsen.
Diese stack-orientierten Gruppen der regulären Ausdrücke sind der eigentliche Clou des Ganzen.

Für die Infix-Suffix-Umwandlung müssen wir beispielsweise das Operatorzeichen "+" zwischen korrekt geklammerten Ausdrücken suchen. Also in

(34+x)[B][COLOR]+[/COLOR][/B]sin(4+x+1)

wäre es das zweite Plus und eben nur dieses !
Das zweite Plus ist das gute, weil es das einzige ist, auf dessen linken Seite die Zahl der öffnenden und schließenden Klammern gleich ist. (Plusse in Sub-Ausdrücken haben links immer mehr öffnende als schließende Klammern)

Und danach können wir nun mit dem folgenden Regex suchen: (der lesbarkeit zeilenweise angegeben)

[pre]Stringanfang:		^ 
linker Operand:		((:question:(?<openBrackets>\()|(?<-openBrackets>\))|[^\(\)])*)(?(openBrackets)(?!))
 (korrekt geklammert)
Whitespace: 		\s*
Operatorsymbol:		\+
Whitespace: 		\s*
Rest (rechter Operand): (.*)
Stringende:		$[/pre]

Noch zur Erläuterung des "linken Operanden":
Dieser besteht aus öffnenden Klammern, die auf den Stack gepackt werden: (?<openBrackets>()
oder aus schließenden Klammern, die was vom Stack entfernen. (?<-openBrackets>))
oder aus Nicht-Klammer-Zeichen. [^()]
Und davon insgesamt beliebig viele. Allerdings muss der Klammernstack am Ende leer sein: (?++++(openBrackets)(?!))

(Der linke und rechte Operand sind nochmal in "(...)" gruppiert, damit ich auf diese einzeln zugreifen kann. So ergibt sich der Präfix-umgeformte Term schlicht aus

Regex.Replace("add($1,$2)")

mit Back-Referenzen $1,$2 auf diese beiden Gruppen)

Ich hoffe, ich konnte die Funktionsweise gut darlegen. Denn nach diesem Prinzip arbeitet dann auch der Rest.

@ Th69,
kanns gerne mal testen, wobei ich denke, dass dein Code schneller sein wird.

beste Grüße
zommi

A
118 Beiträge seit 2009
vor 13 Jahren

Hallo,

Ich finde die Idee, wie du das umgesetzt hast sehr interessant und ich habe den Lösungansatz in dieser Form noch nie gesehen, weshalb ich mir den Parser genauer angesehen habe. Dabei ist mir gleich aufgefallen, dass er einfache Terme, wie z.B.

3-2+5

falsch parst. Daraus wird durch den Aufbau der Schleife nämlich:

3-(2+5)

was so ja falsch ist. Ansonsten funktioniert alles, bis auf eine Kleinigkeit, nämlich dass es bei Leerzeichen Fehler gibt, aber diese zu entfernen ist ja keine grosse Sache.

Mfg Aratar