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
=======
***** Ab hier nur Überlegungen, noch nicht auf wirkliche Sinnhaftigkeit geprüft *****
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
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";
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
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
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
Hallo AlexanderT,
dass der Benutzer deines Formelparsers selbst definieren kann, welche Operatoren erlaubt sind.
herbivore
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
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
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...
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
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...
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
=======
***** Ab hier nur Überlegungen, noch nicht auf wirkliche Sinnhaftigkeit geprüft *****