[Experimentell] Einfacher Formelparser

    • VB.NET

    Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von BiedermannS.

      [Experimentell] Einfacher Formelparser

      Hallo,

      bei diesem Parser handelt es sich um ein kleines Experiment. Nämlich mit möglichst wenig Code, so schnell wie möglich eine mathematisch korrekte Lösung zu bekommen.

      Für die, die sich fragen warum man so etwas macht:

      Vor etwas längerer Zeit, hat hier mal jemand nach dem kürzesten Code zum Rechnen unter Befolgung der Rechenregeln gefragt. Und ich hatte auch schon einen Ansatz dafür, der jedoch nur die vier Grundrechnungsarten konnte (ohne Klammern). Aber er war kompakt (41 Zeilen Code) und lief schnell (Im Schnitt, 0,0094ms für die Rechnung 3-4*2+1/2*7+5*4-3/2*6*4).

      Danach habe ich das Ganze eine Zeit lang nicht beachtet, aber vor Kurzem ist das Interesse aufgekommen, den Parser um das Potentzieren, Klammern, Funktionen, Variablen und Konstanten zu erweitern, aber trotzdem in den drei Kernpunkten gleich zu bleiben: Möglichst wenig Code, möglichst schnell und richtig.

      Dabei ist folgendes entstanden:
      Da der Code leider zu lang ist, hab ich ihn als Anhang hochgeladen: SimpleParser.vb

      Ohne Kommentare und Leerzeilen "nur" 468 Zeilen.

      Getestet habe ich mit 10000 Durchläufen
      Wenn man die Funktionen, Variablen, Klammerkorrektur, Konstanten deaktiviert, braucht er im Durchschnitt ca 0,028ms für folgende Rechnung: (3-4^2)*1/(((2*7+5)*4-3)/2)*6*4
      Ist alles aktiviert, außer Funktionen, benötigt er für die selbe Berechnung durchschnittlich ca. 0,032ms
      Und wenn alles aktiviert ist, benötigt er durchschnittlich ca. 0,05ms

      Wie gesagt, ist eher experimenteller Natur, aber vl Interessiert ja jemanden die Arbeitsweise oder jemand weiß, wo man noch etwas tunen könnte (Zeitmäßig, nicht Zeilenmäßig :)).
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      Hallo, sieht nach ner Menge Arbeit aus ;)
      (auch wenn ich der Meinung bin, dass man niemals einen Code schreiben sollte mit dem Ziel, dass dieser möglichst kurz und kompakt wird ;))
      Eine Frage hätte ich allerdings: Wie kommst du auf 0,028ms? Womit misst du solche genauen Werte? (ich meine, 0,028ms sind 28 millionstel einer Sekunde) Soweit ich weiß, gibt eine Stopwatch nur ganze Millisekunden aus, oder?
      lg

      Artentus schrieb:

      Diese gibt die verstrichene Zeit in "Ticks", also zehntel Mikrosekunden (10^-7s), an.

      ElapsedTicks ist von der Frequenz der Stopwatch abhängig.

      Nein, gemessen habe ich mit
      StopWatch.Elapsed.TotalMilliseconds

      suscurtl schrieb:

      (auch wenn ich der Meinung bin, dass man niemals einen Code schreiben sollte mit dem Ziel, dass dieser möglichst kurz und kompakt wird ;))

      Ich programmiere ja nicht immer so. Man sollte zwar auch auf Performance schauen und darauf, den Code nicht unnötig aufzublasen, aber hier ging es mehr um das verstehen an sich. Einfach einen Weg zu finden, wie man so einen Parser möglichst einfach programmieren kann und die Version, zu der ich den Link gepostet habe, mit der alles anfing, hatte gerade mal 45 Zeilen zur Befolgung der Rechenregeln bei Grundrechenarten.

      Aber das was mir bei dem Code am meisten gefällt ist, dass ein mathematischer Ausdruck gerechnet werden kann, ohne die die Formel als Ganzes zu betrachten, sondern Schritt für Schritt von links nach rechts. Das einzige was vorgreift sind die Funktionen zum Ersetzen(Variablen, Funktionen usw.) und die Klammerkorrektur. Der Rest könnte auch mit einem Stream rechnen, sofern alles korrekt gesendet wird, da es für die Berechnung egal ist, was weiter hinten in der Formel steht.

      suscurtl schrieb:

      sieht nach ner Menge Arbeit aus

      So schlimm wars nicht. Der Code war schnell geschrieben, nur das Fehlersuche war Horror. Da merkt man schon, warum man normalerweise mehr Struktur in den Programmen hat und gewisse Dinge auf mehrere Methoden aufteilt.
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      @BiedermannS: In Deiner Operators-Liste fehlt das Divisionszeichen für Integer-Division: "\"
      Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
      Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
      Ein guter .NET-Snippetkonverter (der ist verfügbar).
      Programmierfragen über PN / Konversation werden ignoriert!

      Es fehlt nicht, sondern wurde einfach nicht implementiert, da ich im großen und ganzen nur die Mathematischen Grundoperatoren eines Taschenrechners verwendet habe. Für alles andere gibt es Funktionen :)
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      scheint richtig zu rechnen, aber der Code ist schwer verbesserungsbedürftig.

      Dieses Konstrukt:

      VB.NET-Quellcode

      1. Select Case currentoperator
      2. Case "+"c
      3. numbers(level).Push(NewValue(value))
      4. Case "-"c
      5. numbers(level).Push(NewValue(value))
      6. Minus.Add(numbers(level).Peek.Key)
      7. Case "*"c
      8. If Minus.Contains(numbers(level).Peek.Key) Then
      9. Minus.RemoveAll(rem0)
      10. IsMinus = True
      11. End If
      12. numbers(level).Push(NewValue(numbers(level).Pop.Value * value))
      13. If IsMinus Then Minus.Add(numbers(level).Peek.Key)
      14. IsMinus = False
      15. Case "/"c
      16. If Minus.Contains(numbers(level).Peek.Key) Then
      17. Minus.RemoveAll(rem0)
      18. IsMinus = True
      19. End If
      20. numbers(level).Push(NewValue(numbers(level).Pop.Value / value))
      21. If IsMinus Then Minus.Add(numbers(level).Peek.Key)
      22. IsMinus = False
      23. Case "^"c
      24. If Minus.Contains(numbers(level).Peek.Key) Then
      25. Minus.RemoveAll(rem0)
      26. IsMinus = True
      27. End If
      28. numbers(level).Push(NewValue(Math.Pow(numbers(level).Pop.Value, value)))
      29. If IsMinus Then Minus.Add(numbers(level).Peek.Key)
      30. IsMinus = False
      31. End Select
      taucht 4 mal auf, also das muß man vom Code-Design her in eine Methode auslagern, und dein Code ist um ca 100 Zeilen kürzer.

      Auch blicke ich leider überhaupt nicht den Algorithmus, den du verwendest.
      Es gibt da iwie recht abenteuerliche Auflistungen, List(Of Stack(Of KeyValuePair(Of Int16, Double))), und noch eine Operator-Liste, und noch eine Minus-Liste, also ich hab Zweifel, dass das Datenmodell so kompliziert sein muß.

      Dabei gibts zum Thema doch einen Stand der Technik - kannste bei Wiki nachlesen:
      Erst den String in eine Liste von Tokens überführen, dann die Tokens in Postfix-Notation umsortieren, dann die Liste abarbeiten.
      Müsste ratzfatz gehen und auch verständlich sein.
      Vermutlich wäre eine kluge Token-Klasse zu schreiben.

      So, jetzt habichmich auch ordentlich verkünstelt. Ich fand dabei auch einen Ausdruck, den @BiedermannS:' Parser falsch rechnet:

      VB.NET-Quellcode

      1. Imports System.Diagnostics
      3. Public Module modMain
      5. Sub Main()
      6. Dim result = ((2 ^ 2 ^ 3 - 3) - 4) * 2 + 1 / 22 * (-7 + 5) * 4 - -3.3 / 2 * 6 * 4
      7. Dim xpr = "((2 ^ 2 ^ 3 - 3) - 4) * 2 + 1 / 22 * (-7 + 5) * 4 - -3.3 / 2 * 6 * 4"
      8. Dim r = (New SimpleParser).Calculate(xpr)
      9. End Sub
      11. End Module


      Ansonsten habich meinen Ansatz mitte Postfix-Notation umgesetzt.
      Also einen Tokenizer geschrieben, dann den Shunting-yard-Algorithmus implementiert, um die Tokens nach Postfix-Notation anzuordnen, und dann noch den "Ausrechner" für postfix-notierte Tokenlisten.
      Das geht in 100 Zeilen, inklusive viel Kommentar.

      Sehr interessant fandich, dass offensichtlich Microsoft selbst falsch rechnet!:
      Auf Wikipedia wird behauptet, dass der Potenz-Operator rechts-assoziativ sei.
      Also 2 ^ 2 ^ 3 entspreche 2 ^ (2 ^ 3)
      Microsoft rechnet aber linksassoziativ, also (2 ^ 2) ^ 3

      ?(
      Dateien

      ErfinderDesRades schrieb:

      taucht 4 mal auf, also das muß man vom Code-Design her in eine Methode auslagern, und dein Code ist um ca 100 Zeilen kürzer.

      Ist zwar für die Leserlichkeit und Wartbarkeit eher hinderlich, hat aber ne bessere performance. Aber habs jetzt erst mal umgebessert.

      ErfinderDesRades schrieb:

      Auch blicke ich leider überhaupt nicht den Algorithmus, den du verwendest.

      Gerechnet wird nach folgenden Regeln:

      + : Schieb den Wert auf den Stack
      - : Schieb den Wert auf den Stack und merk dir dass das ne minus rechnung war
      / : Hole den letzten Wert vom Stack, dividiere durch den aktuellen, schiebe das Ergebnis auf den Stack
      * : Hole den letzten Wert vom Stack, multipliziere mit dem aktuellen, schiebe das Ergebnis auf den Stack

      ( : Erstelle einen neuen Stack auf dem gerechnet wird
      ) : Schließe den aktuellen Stack und rechne ihn zum vorherigen dazu

      Die List(of Stack) dient für die einzelnen Stacks. (Für jede offene Klammer einer) die KeyValuePairs dienen der Identifizierung der Zahlen, damit man sich merken kann, welche Zahl eine Subtraktion ist.

      ErfinderDesRades schrieb:

      Dabei gibts zum Thema doch einen Stand der Technik - kannste bei Wiki nachlesen:

      Darum ist das Ganze auch experimentell. Ich habe einfach versucht einen Algorithmus zu schreiben, der schnell und einfach ist. Und mit Zettel und Stift wars auch einfach, den Algorithmus durchzuführen. Nur gabs halt immer wieder ein paar Problemchen, die aber nun auch behoben sind.

      Ich weiß natürlich, dass alle aktuellen Parser anders arbeiten, jedoch war mein Ziel auch nicht einen vorhandenen Parser nachzuprogrammieren.

      ErfinderDesRades schrieb:

      Ich fand dabei auch einen Ausdruck, den @BiedermannS:' Parser falsch rechnet:

      Danke für den Hinweis. Wurde auch schon ausgebessert.

      Der neue Code befindet sich im Anhang: SimpleParser.vb

      P.S.: Die Frequenz der Stopwatch hängt von der Hardware ab
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D