Laden...

Formelparser

Erstellt von AlexanderT vor 14 Jahren Letzter Beitrag vor 14 Jahren 11.415 Views
AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren
Formelparser

Beschreibung:

Ich habe einen relativ leicht erweiterbaren und im Moment noch recht simplen Formelparser für mathematische Formeln geschrieben.

Er unterstützt im Moment folgende Operanden: + | - | * | / | ^ | ( | )

Der Parser ist relativ Syntax-unabhängig soweit man das sagen kann:
Whitespaces werden ignoriert '.' als auch ',' werden für Komma-Zahlen akzeptiert.

Edit:
Nutzung:


using MathExprParser;

Parser.Parse("10.5-3.5+2.5*2.5+(3*4-(-7)*3)");

Die TODO-List für die nächste Zeit beinhaltet folgendes:

Scanner.cs:


namespace MathExprParser
{
    public enum Operand
    {
        Addieren,
        Subtrahieren,
        Dividieren,
        Multiplizieren,
        Potenzieren,
        OpenBracket,
        CloseBracket
    }

    internal class Scanner
    {
        private static Dictionary<char, Operand> operands = new Dictionary<char, Operand> {
            { '+', Operand.Addieren },
            { '-', Operand.Subtrahieren },
            { '*', Operand.Multiplizieren },
            { '/', Operand.Dividieren },
            { '^', Operand.Potenzieren },
            { '(', Operand.OpenBracket },
            { ')', Operand.CloseBracket }
        };

        static internal List<object> Scan(string input)
        {
            List<object> Tokens = new List<object>();

            bool Negotate = false;

            if (input.Length < 3)
            {
                //Werfe ScannerException, String zu kurz. 
            }

            for (int index = 0; index < input.Length; index++)
            {
                if (Char.IsDigit(input[index]))
                {
                    if (Negotate)
                    {
                        Tokens.Add(Double.Parse("-" + ScanNumber(input, ref index)));
                        Negotate = false;
                    }
                    else
                    {
                        Tokens.Add(ScanNumber(input, ref index));
                    }
                }
                else if (IsOperator(input[index]))
                {
                    if (Tokens.Count > 0)
                    {
                        if (Tokens[Tokens.Count - 1] is Operand)
                        {
                            Operand LastOp = (Operand)Tokens[Tokens.Count - 1];

                            if (ScanOperator(input[index]) == Operand.Subtrahieren)
                            {
                                Negotate = true;
                            }
                            else if (ScanOperator(input[index]) == Operand.OpenBracket || LastOp == Operand.CloseBracket)
                            {
                                Tokens.Add(ScanOperator(input[index]));
                            }
                        }
                        else
                        {
                            Tokens.Add(ScanOperator(input[index]));
                        }
                    }
                    else
                    {
                        if (ScanOperator(input[index]) == Operand.Subtrahieren)
                        {
                            Negotate = true;
                        }
                        else if (ScanOperator(input[index]) == Operand.OpenBracket)
                        {
                            Tokens.Add(Operand.OpenBracket);
                        }
                    }
                }
            }

            return Tokens;
        }

        static private Double ScanNumber(string input, ref int index)
        {
            string temp = "";

            for (int i = index; i < input.Length; i++)
            {
                if (char.IsDigit(input[i]) || input[i].Equals('.') || input[i].Equals(','))
                {
                    if (input[i].Equals(','))
                    {
                        temp += '.';
                        continue;
                    }
                    temp += input[i];
                    index = i;
                }
                else
                {
                    break;
                }
            }

            return Double.Parse(temp, System.Globalization.CultureInfo.InvariantCulture);
        }

        static private bool IsOperator(char c)
        {
            return operands.ContainsKey(c);
        }

        static private Operand ScanOperator(char c)
        {
            if (operands.ContainsKey(c))
            {
                return operands[c];
            }
            throw new FormatException("Dieser Operand ist nicht bekannt.");
        }
    }
}

Parser.cs:


namespace MathExprParser
{
    public class Parser
    {
        public static double Parse(string input)
        {
            List<object> Tokens = Scanner.Scan(input);

            for (int i = 0; i < Tokens.Count; i++)
            {
                if (Tokens[i] is Operand)
                {
                    Operand Op = (Operand)Tokens[i];

                    if (Op == Operand.OpenBracket)
                    {
                        for (int j = 0; j < Tokens.Count; j++)
                        {
                            if (Tokens[j] is Operand)
                            {
                                Op = (Operand)Tokens[j];

                                if (Op == Operand.OpenBracket)
                                {
                                    i = j;
                                }

                                if (Op == Operand.CloseBracket)
                                {
                                    Tokens[i] = ResolveExpression(Tokens.GetRange(i + 1, j - (i + 1)));
                                    Tokens.RemoveRange(i + 1, j - (i));
                                    i = -1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }

            return ResolveExpression(Tokens);
        }

        static internal Double ResolveExpression(List<object> tokens)
        {
            ResolveExpressionHelper(ref tokens, Operand.Potenzieren);
            ResolveExpressionHelper(ref tokens, Operand.Dividieren);
            ResolveExpressionHelper(ref tokens, Operand.Multiplizieren);
            ResolveExpressionHelper(ref tokens, Operand.Subtrahieren);
            ResolveExpressionHelper(ref tokens, Operand.Addieren);

            if (tokens.Count != 1)
            {
                //TODO: ParsingException werfen
            }

            return Double.Parse(tokens[0].ToString());
        }

        private static void ResolveExpressionHelper(ref List<object> tokens, Operand OpTarget)
        {
            for (int i = 0; i < tokens.Count; i++)
            {
                if (tokens[i] is Operand)
                {
                    Operand Op = (Operand)tokens[i];

                    if (Op == OpTarget)
                    {
                        tokens[i - 1] = ResolveOperand(tokens[i - 1], Op, tokens[i + 1]);
                        tokens.RemoveRange(i, 2);
                        i = 0;
                    }
                }
            }
        }

        static private double ResolveOperand(object left, Operand op, object right)
        {
            switch (op)
            {
                case Operand.Addieren:
                    return Double.Parse(left.ToString()) + Double.Parse(right.ToString());
                case Operand.Subtrahieren:
                    return Double.Parse(left.ToString()) - Double.Parse(right.ToString());
                case Operand.Dividieren:
                    return Double.Parse(left.ToString()) / Double.Parse(right.ToString());
                case Operand.Multiplizieren:
                    return Double.Parse(left.ToString()) * Double.Parse(right.ToString());
                case Operand.Potenzieren:
                    return Math.Pow(Double.Parse(left.ToString()), Double.Parse(right.ToString()));
                default:
                    throw new FormatException("Operand nicht auflösbar.");
            }
        }
    }
}

Das sind bisher rund 250 Zeilen.

Zur Performance:

nach einigen schnellen und sicherlich unvollständigen Tests bin ich je nach Länge und Komplexität 10-40% schneller als Th69's Parser 😃)

Verbesserungsvorschläge sowie Ideen für Erweiterungen sind selbstverständlich erwünscht 😉

=======
Roadmaps
=======

v1.0 Beta 2 Roadmap:

  • AST implementieren
  • Mathematische Funktionen implementieren

v1.0 Beta 3 Roadmap:

  • Fehlerbehandlung vervollständigen / korrigieren
  • Definition eigener Funktionen implementieren

v1.0 RC 1 Roadmap:

  • Dynamische Operatoren(siehe Beta 3-> eigene Funktionen
  • Spiegelung relevanter Implementierungen auf den statischen Parser für einfache Funktionen
  • umfassende Tests aller Funktionen und Geschwindigkeiten.
  • Verlauf auf github spiegeln

Release v1.0 Roadmap:

  • vollständig debuggt

***** Ab hier nur Überlegungen, noch nicht auf wirkliche Sinnhaftigkeit geprüft *****

v1.1 Beta 1 Roadmap:

  • implementieren eines Primzahlenrechners

v1.1 Beta 2 Roadmap:

  • implementieren eines DezToOktal-Parsers
  • implementieren eines DezToDez-Parsers
  • implementieren eines DezToHex-Parsers

v1.1 Beta 3 Roadmap:

  • implementieren eines HexaToBinary-Parsers
  • implementieren eines HexaToOktal-Parsers
  • implementieren eines HexaToDez-Parsers

v1.1 Beta 3 Roadmap:

  • implementieren eines BinaryToOktal-Parsers
  • implementieren eines BinaryToDez-Parsers
  • implementieren eines BinaryToHex-Parsers

v1.1 Beta 4 Roadmap:

  • implementieren einer Hexa-Version des Formelparsers
  • implementieren einer Binär-Version des Formelparsers

v1.1 RC 1 Roadmap:

  • Tests auf neue Parser erweitern

v1.1 Release Roadmap:

  • vollständig debuggt
  • Termin unbekannt, 01.03 angepeilt

Falls ich etwas wichtiges vergessen habe bitte ich um Nachsicht, es ist mein erstes Snippet 😃

Gruß Alex

P.S.: Im Anhang ist der Parser samt TestProjekt zum ausprobieren und/oder Debuggen.

Schlagwörter: Formelparser, Tokens, Scanner

N
203 Beiträge seit 2008
vor 14 Jahren
     static private bool IsOperator(char c)
        {
            if (c.Equals('+'))
                return true;
            else if (c.Equals('-'))
                return true;
            else if (c.Equals('*'))
                return true;
            else if (c.Equals('/'))
                return true;
            else if (c.Equals('^'))
                return true;
            else if (c.Equals('('))
                return true;
            else if (c.Equals(')'))
                return true;
            else
                return false;
        }

        static private Operand ScanOperator(char c)
        {
            switch (c)
            {
                case '+':
                    return Operand.Addieren;
                case '-':
                    return Operand.Subtrahieren;
                case '*':
                    return Operand.Multiplizieren;
                case '/':
                    return Operand.Dividieren;
                case '^':
                    return Operand.Potenzieren;
                case '(':
                    return Operand.OpenBacket;
                case ')':
                    return Operand.CloseBracket;
                default:
                    throw new FormatException("Dieser Operand ist nicht bekannt.");
            }
        }

Wäre das nicht einfacher mit einem Dictionary<char, Operand> zu ersetzen?

public class Scanner
{
     private Dictionary<char, Operand> _operands;

    public Scanner()
    {
        _operands = new Dictionary<char, Operand>();
        _operands.Add('+', Operand.Addieren);
        _operands.Add('-', Operand.Subtrahieren);
    }

    private bool IsOperator(char c)
    {
        return _operands.ContainsKey(c);
    }

    private Operand ScanOperator(char c)
    {
        if (_operands.ContainsKey(c))
        {
            return _operands[c];
        }
        throw new FormatException("Dieser Operand ist nicht bekannt.");
    }
}

Signatur.Text = "Greetz, Neals";

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren

Sowas hatte ich auch schon im Kopf, hatte es dann aber wieder verworfen weil ich es irgendwie nicht so recht hinbekommen wollte. Ich sehe auch gerade warum das so war: Ich habe alle Methoden statisch deklariert(ich füge mal flugs oben noch die Nutzung ein). Deshalb war das nicht so umzusetzen. Ich hab die Redundanz aber im Blick. Danke trotzdem, ich werde mich damit nochmal beschäftigen.

So geht es:



        private static Dictionary<char, Operand> operands = new Dictionary<char, Operand> {
            { '+', Operand.Addieren },
            { '-', Operand.Subtrahieren },
            { '*', Operand.Multiplizieren },
            { '/', Operand.Dividieren },
            { '^', Operand.Potenzieren },
            { '(', Operand.OpenBacket },
            { ')', Operand.CloseBracket }
        };

        static private bool IsOperator(char c)
        {
            return operands.ContainsKey(c);
        }

        static private Operand ScanOperator(char c)
        {
            if (operands.ContainsKey(c))
            {
                return operands[c];
            }
            throw new FormatException("Dieser Operand ist nicht bekannt.");
        }


Gruß

Alex

1.346 Beiträge seit 2008
vor 14 Jahren

gefällt mir gut. du hast das prinzip eines compilers genutzt. ein verbesserungsvorschlag währe noch eine dynamiche erweiterung um mehr operatoren. dann noch einsetzen in eine variable.

Gruß pdelvo

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren

Danke, ja am Compiler habe ich mich orientiert, ich habe neulich (weil ich gerne zum Üben eine ScriptSprache entwicklen möchte) nach "Compiler-Anleitungen" gesucht und bin auf Bernd Marquardt's Nightcast "Ein neuer Compiler in einer Stunde" gestoßen. Davon habe ich mich dann leiten lassen und meinen MatheParser komplett neugeschrieben(ich hatte eine alte Version die String-Basiert, doppelt so lang, halb so schnell und fast nicht erweiterbar war).

An den Variablen werde ich mich definitiv auch mal versuchen. Was meinst du mit dynamische Erweiterung um mehr Operatoren? Das verstehe ich nicht so ganz...

Gruß

Alex

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo AlexanderT,

dass der Benutzer deines Formelparsers selbst definieren kann, welche Operatoren erlaubt sind.

herbivore

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren

Ahh ok. Ja kommt auch auf die Liste, Danke!

Gruß

Alex

4.931 Beiträge seit 2008
vor 14 Jahren

Oh, ein Konkurrent -)

Und wenn du dann deine ganzen ToDo's noch implementiert hast, dann wollen wir noch mal einen Geschwindigkeitsvergleich machen...
Insbesondere wenn bei meinem Parser der "Optimize"-Modus aktiviert ist.

P.S. Du hast noch einen Schreibfehler drin: OpenBracket

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren

Es ist doch nur Spaß 😉
Obgleich ich versuchen werde schneller zu bleiben/sein als du, aber wir werden sehen.
Ich würde gerne mal gegen "optimize" testen, wie kann ich es denn anschalten?

Auch wenn meine Todos implementiert sind, wird das Parsings eines Strings wie im Beispiel oben (hoffentlich) nicht sonderlich länger dauern, ich möchte ja die Geschwindigkeit beibehalten und würde nach Möglichkeit die Methoden als Extra-Methoden implementieren, sofern ich das ohne Redundanz hinbekomme. Wir werden sehen.

Schreib-Fehler behoben.

Gruß

Alex

4.931 Beiträge seit 2008
vor 14 Jahren

Hallo Alexander,

den Optimierungs- sowie den Vorberechnungsmodus habe ich unter "Edit #2" in meinem Beitrag beschrieben.

Durch den Einbau von Operatoren mit beliebiger Länge (d.h. ≥ 1) mußte ich einen kleinen Trick anwenden (um den Enumerator zu speichern), so daß die Performance damit etwas gelitten hat.
Mein Einsatzgebiet ist aber besonders für mehrmaliges Aufrufen von Formeln (d.h. wo sich dann nur die Variablen ändern - die du ja noch nicht implementiert hast).

Insbesondere ging es mir bei meinem Beitrag auch um den theoretischen Hintergrund (den Parser sowie das Graph-Programm hatte ich ursprünglich in C++ entwickelt - und dieser entstand aus einem Compiler für eine an C und BASIC angelehnte Sprache, den ich vor ca. 18 Jahren erst in Assembler und später dann in C auf dem legendären Amiga entwickelt hatte).
Gerade bei Grammatiken und Sprachen muß man einfach den Begriff (E)BNF kennen - und dies war leider bei vielen Implementierung, die ich vorher gesehen hatte, nicht gegeben - daher meine Motivation für die Umsetzung nach C#.

Viel Erfolg wünsche ich dir aber - denn ich möchte selber gerne auch von anderen Leuten lernen.
Mein langfristiges Ziel wäre es nämlich, ein Parser-Framework à la boost::spirit (C++) zu schaffen...

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren
Eval, Variablenauflösung und Performance

Hi,

So, ich habe soeben Beta 1 von MathExprParser 0.2 fertig gestellt.

Changelog:
unterstützung von E und pi/Pi/pI/PI für Math.E und Math.PI
neue Klasse Eval
Variablen können impliziet multipliziert werden: 3x = 3*x
(Klammern sollen das in Beta 2 auch beherrschen)
Fehlerbehandlung begonnen(Feinheiten fehlen noch)
EDIT:
Fehler behoben der verursachte das keine Variable am Anfang stehen konnte.
DivideByZeroException implementiert

(Alle Cahnges gelten atm leider nur für Eval, werden (soweit Sinnvoll) aber auch noch im statischen Parser für einfache Formeln integriert).

Eval ist gedacht um Formeln mit Variablen schnell zu parsen.

Die Nutzung ist recht Simpel:


Eval test = new Eval("1x+1", new Variable[] { new Variable('x', 1m) });
decimal MeinErgebnis = test.Resolve();

Wie schon zu sehen erwartet Eval im Regelfall eine Formel als string, und ein Array vom mitgelieferten Typ Variable welcher wiederum einen char (das Formelzeichen) und einen decimal-Wert erwartet. Resolve() löst die Formel komplett auf und gibt das Ergebnis als decimal zurück. Es Scannt falls IsScanned auf false steht, sonst nicht. Wen IsResolved auf true stand(weil bereits Resolved wurde aber sich nichts geändert hat) tut sie auch nichts, man kann das Ergebnis auch über .Result erreichen allerdings ist dies ein Decimal? Welches es am Anfang, sowie nach Änderung der Formel auf null steht.

Es existiert außerdem die Grundfunktion Scan() welche auf ohne Auflösen aufgerufen werden kann. Diese setzt IsScanned natürlich auf true, wenn IsScanned bereits auf true stand tut sie nichts. Wenn man die Werte der Variablen ändern will muss man ChangeVariable() aufrufen und den index(zukünftig anstelle dessen auch das Formelzeichen) und den neuen Wert übergeben.

Die Funktionsweise ähnelt dem des statischen Parsers, aber sofern nur die Variablen geändert werden so werden die Tokens beibehalten d.h. es muss kein ReScanning durchgeführt werden(was 80% der Zeit des normalen parsings beansprucht hat)

Momentan werden nur char.IsLetter==true als Formelzeichen angenommen, man kann also nur maximal 26 Variablen in einer Formel haben, findet ihr das reicht oder sollte ich lieber Unterstützung für Formelwörter ala "GeschwindigkeitDesZuges"( 😁 ) möglich machen(Man könnte solche Formeln ja auch zur Laufzeit und nicht vollständig vom User als Input erstellen)?

Ich habe wieder ein Speedtest-Projekt ängehängt und würde gerne wissen ob bei euch die Zeiten auch bei <500-1000 ms liegen und mein Test richtig ist ⚠. Ich traue mir nämlich gerade selbst nicht, da das für 100.000 Iterationen mit sich ändernder Variable einfach verdammt schnell ist(oder ?( )

Bei Fragen/Anmerkungen oder Verbesserungsvorschlägen gilt wie bisher: Immer her damit.

Gruß

Alex

4.931 Beiträge seit 2008
vor 14 Jahren

Hallo Alexander,

... bei euch die Zeiten auch bei <500-1000 ms liegen und mein Test richtig ist ⚠

leider nein, denn du hast einen Fehler in deiner Zeitmessung:

watch.ElapsedTicks / 10000m + "ms"

Obwohl bei mir ca. 900ms angezeigt werden, sind es ca. 3 Sekunden Ausführungszeit.

Entweder

watch.ElapsedTicks / watch.Frequency + "s"

oder gleich

watch.ElapsedMilliseconds + "ms"

-)

Und dann wäre dein Expr-Parser doch langsamer als meiner:
hier die Ergebnisse von meinem MathParser mit der von dir verwendeten Formel:
normal: ~2,9 Sek (also etwa gleichschnell mit deinem Parser).
vorberechnet (Evaluate/Optimized): 0,3 Sekunden

Mir ist jedoch durch den Test ein kleiner Fehler bei meinem aufgefallen, den ich demnächst beheben werde...

AlexanderT Themenstarter:in
70 Beiträge seit 2009
vor 14 Jahren
Falscher Test

Ich habs mir schon fast gedacht. Der Fehler kam weil ich dachte das DateTime.Tick == StopWatch.Tick, und dem ist nicht so.
Na dann bin ich wenigstens gleich schnell 😃) freut mich als C#-"Frischling" auch schon ^^ Ich lebe ja kaum so lange wie du schon programmierst^^ (bin 18 und programmiere ca. 1 Jahr).

Ich ändere allerdings bei jedem Durchlauf den Wert der Variable (test.ChangeVariableValue(0, i + 1) ), wodurch er den Endwert jedes mal neu Berechnet. Ich bin mir nicht sicher, aber macht dein Test das auch? Wenn man den Aufruf nämlich rausnimmt komme ich auch bei ~20-30 ms an(weil ja nur einmal berechnet und danach nur noch das Ergebnis zurückgegeben wird), das wäre aber als Speedtest nicht wirklich sinnvoll.

Ich werde jetzt aber mal einen AST implementieren, so dürfte noch etwas Performance erreicht werden.

Ich nheme mal an der Endeckte Fehler war das du keine "implizite Multiplikation" unterstützt?

Als Ausblick für jene, die es interessiert(Auch im Eingangspost):

=======
Roadmaps
=======

v1.0 Beta 2 Roadmap:

  • AST implementieren
  • Mathematische Funktionen implementieren

v1.0 Beta 3 Roadmap:

  • Fehlerbehandlung vervollständigen / korrigieren
  • Definition eigener Funktionen implementieren

v1.0 RC 1 Roadmap:

  • Spiegelung relevanter Implementierungen auf den statischen Parser für einfache Funktionen
  • umfassende Tests aller Funktionen und Geschwindigkeiten.
  • Verlauf auf github spiegeln

Release v1.0 Roadmap:

  • vollständig debuggt

***** Ab hier nur Überlegungen, noch nicht auf wirkliche Sinnhaftigkeit geprüft *****

v1.1 Beta 1 Roadmap:

  • implementieren eines Primzahlenrechners

v1.1 Beta 2 Roadmap:

  • implementieren eines DezToOktal-Parsers
  • implementieren eines DezToDez-Parsers
  • implementieren eines DezToHex-Parsers

v1.1 Beta 3 Roadmap:

  • implementieren eines HexaToBinary-Parsers
  • implementieren eines HexaToOktal-Parsers
  • implementieren eines HexaToDez-Parsers

v1.1 Beta 3 Roadmap:

  • implementieren eines BinaryToOktal-Parsers
  • implementieren eines BinaryToDez-Parsers
  • implementieren eines BinaryToHex-Parsers

v1.1 Beta 4 Roadmap:

  • implementieren einer Hexa-Version des Formelparsers
  • implementieren einer Binär-Version des Formelparsers

v1.1 RC 1 Roadmap:

  • Tests auf neue Parser erweitern

v1.1 Release Roadmap:

  • vollständig debuggt
  • Termin unbekannt, 01.03 angepeilt