Formeln sinnvoll parsen

  • VB.NET

Es gibt 17 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Formeln sinnvoll parsen

    Nabend,

    bin gerade dabei mir zu überlegen wie man am besten Funktionen parsen kann.
    Nur ersteckt sich das ganze im Moment irgendwie ins endlose.

    Ich hab es zuerst mit Substring, Split, usw. versucht, doch wird das ganze etwas viel zu lang.
    Lese mich gerade mal wieder in RegEx ein (hab dazu wieder alles vergessen :P).

    Naja zur frage, wie würdet ihr sinnvoll Funktionen parsen?
    Mit Funktionen sind noch erstmal die einfachen gemeint (Lineare; Quadratische, Ganzrationale 3. Grad aufwärts):

    f(x) = mx + b
    f(x)= a*(x-xs)+ys
    f(x)=ax^3+bx^2+cx+d
    f(x)=ax^5+cx^3+dx2+e

    Nur irgendwie finde ich keinen einheitlichen Weg, im Moment müsste ich für jede Funktion einen Sub schreiben.
    Und das ganze summiert sich auf vieeel zu vieeeeel Zeilen..

    Kennt ihr da eine bessere Lösung/Idee/Funfktion/.dll/sonstwas :P ?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Eistee“ ()

    Meinst Du mit parsen so:

    VB.NET-Quellcode

    1. Function f1(ByVal x As Double, ByVal m As Double, ByVal b As Double) As Double
    2. Return m * x + b
    3. End Function
    5. Function f2(ByVal x As Double, ByVal a As Double, ByVal s As Double, ByVal y As Double) As Double
    6. Return a * (x - x * s) + y * s
    7. End Function
    9. Function f3(ByVal x As Double, ByVal a As Double, ByVal b As Double, ByVal c As Double, ByVal d As Double) As Double
    10. Return a * x ^ 3 + b * x ^ 2 + c * x + d
    11. End Function
    13. Function f4(ByVal x As Double, ByVal a As Double, ByVal c As Double, ByVal d As Double, ByVal e As Double) As Double
    14. Return a * x ^ 5 + c * x ^ 3 + d * x ^ 2 + e
    15. End Function

    Oder dass man nur den String übergibt und das Programm erkennt selbst was gerechnet werden muss?
    Für letztere Variante gibt es eine Lib hier im Showroom. ExpressionParser oder so hieß die.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Eigentlich bäuchte ich alles einzelt, da der komplette Rechenweg in kleinsten schritten mit ausgegeben werden soll.
    Wie die Erklärungen auf Wikipedia:







    Quelle: Wikipedia.org - Quadratische Funktion Scheitelpunktbestimmung

    Dafür müsste ich alle einzelnen Teile haben, die Variablen m, x, b, a, c, d, ..., die Exponenten und die Operatoren je nach Funktion.
    Da ist der Parser von Quadsoft ehr nicht hilfreich.

    Ich glaube wohl, ich komm um den RegEx Berg nicht rum. :wacko:

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Eistee“ ()

    Eistee schrieb:

    RegEx Berg

    Vergiss es. Erstelle dir eine Grammatik, die alle Polynome, wie du sie meinst, produzieren kann. Vielleicht findest du auch was im Netz. Die Frage ist, ob du Ausdrücke vereinfachen oder auswerten willst. Auswerten ist einfach, Vereinfachen ist schwer. Dafür gibts nämlich Algebra-Programme. Eventuell kommst du um ein bisschen theoretische Informatik nicht drumherum. Siehe dazu Wikipedia: Formale Grammatik.

    Die Grammatik für Ausdrücke aus Zahlen und Operatoren könnte so aussehen:
    G = (N, T, P, S) mit N = {ZAHL, OP}, T = {Ganzzahlen, +, -}, P = {
    S --> ZAHL | ZAHL OP S,
    OP --> + | - }
    und S = S (Startsymbol).

    Das kannst du erweitern, in deinem Fall um Klammern, Potenzen, Variablen. Einen gegebenen Ausdruck kannst du mit dieser Grammatik in einen Syntaxbaum zerlegen. Beim Auswerten wars das schon. Zum Vereinfachen müsste man sich noch was überlegen.
    Gruß
    hal2000

    Ach so war das gemeint.
    Ja, das wird ein ganzer Haufen Code werden.

    Du müsstest etwas machen, was Zeichen für Zeichen einließt und verarbeitet. Dabei sollte alles so weit wie möglich abstrahiert werden.
    Versuche in ganz kleinen Schritten zu denken und die im Kopf in Programmlogik umzusetzen.
    Ich hätte da an sowas gedacht:
    Es wird zeichenweise der Eingabestring überprüft und immer neue Objekte in eine Liste eingefügt.
    Kopere den Code einfach mal in eine Solution und gucke im Einzelschrittdebugging was passiert.

    Die MessageBox zeigt dann einfach an, wie die Formel im Ursprungszustand ausgesehen hat (aber mit allen impliziten Operatoren (z.B. 2b -> 2*b)).
    Du müsstest dann so lange eine Schleife durchlaufen lassen, die alles soweit "normalisiert" wie möglich, bis alle Container nur noch 3 SubKeyWords haben: Operand, Operator und noch ein Operand. Dadurch kann, wenn es fixe Zahlen sind vereinfacht werden und aus dem ganzen Container wird eine fixe Zahl.
    Das Problem, bei dem ich selbst nicht durchblicke: Was bedeutet "Vereinfachen" für den Computer? Woher weiß er, dass a(b+c) einfacher ist als ab+ac? Oder wäre es anders doch besser?
    Das musst Du dann in die Logik der zweiten Schleife packen.
    Spoiler anzeigen

    VB.NET-Quellcode

    1. Sub Test() Handles Button1.Click
    2. Parse(TextBox1.Text)
    3. End Sub
    5. Sub Parse(ByVal Input As String)
    6. Dim NewFormula As New Formula
    7. For Each i As Char In Input
    8. Select Case True
    9. Case i = " "c
    10. 'Leerzeichen werden ignoriert
    11. Case Byte.TryParse(i, New Byte) 'Es handelt sich um eine Zahl
    12. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_FixedNumber Then
    13. 'Die letzte Zahl wird erweitert
    14. DirectCast(NewFormula.ContainerStack.First.SubKeyWords.Last, Formula.KeyWord_FixedNumber).Extend(i)
    15. Else
    16. 'Eine neue Zahl wird angelegt
    17. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Variable Then
    18. 'Wenn das letzte Element eine Variable ist wird ein Multiplikations-Operator hinzugefügt
    19. NewFormula.ContainerStack.First.SubKeyWords.Add(New Formula.KeyWord_Operator(Formula.KeyWord_Operator.OperatorType.Multiply))
    20. End If
    21. NewFormula.ContainerStack.First.SubKeyWords.Add(New Formula.KeyWord_FixedNumber(i))
    22. End If
    23. Case Formula.KeyWord_Operator.IsOperator(i)
    24. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Operator Then
    25. 'Zwei Operatoren aufeinander sind ungültig!
    26. Throw New Exception
    27. End If
    28. 'Ein neuer Operator wird angelegt
    29. NewFormula.ContainerStack.First.SubKeyWords.Add(Formula.KeyWord_Operator.FromChar(i))
    30. Case i = "("c
    31. 'Eine öffnende Klammer veranlasst, dass ein neuer Container in dem Container angelegt wird
    32. 'Dadurch werden zuerst Klammern berechnet
    33. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso (TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_FixedNumber OrElse TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Variable) Then
    34. 'Wenn eine Klammer auf eine Zahl oder Variable folgt wird ein Multiplikationsoperator hinzugefügt
    35. NewFormula.ContainerStack.First.SubKeyWords.Add(New Formula.KeyWord_Operator(Formula.KeyWord_Operator.OperatorType.Multiply))
    36. End If
    37. NewFormula.LevelDown()
    38. Case i = ")"c
    39. 'Eine schließende Klammer beendet den Container und es wird mit dem übergeordneten weitergearbeitet
    40. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Operator Then
    41. 'Eine schließende Klammer auf einen Operator ist ungültig
    42. Throw New Exception
    43. End If
    44. If NewFormula.LevelUp() Then
    45. Throw New Exception 'Es gibt nichts mehr zurückzuspringen (hier könnte eine schließende Klammer zu viel sein)
    46. End If
    47. Case Else
    48. 'Es handelt sich um eine Variable
    49. If NewFormula.ContainerStack.First.SubKeyWords.Count > 0 AndAlso (TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_FixedNumber OrElse TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Variable OrElse TypeOf NewFormula.ContainerStack.First.SubKeyWords.Last Is Formula.KeyWord_Contaier) Then
    50. 'Wenn eine Variable auf eine Zahl, eine andere Variable oder auf eine schließende Klammer folgt wird ein Multiplikations-Operator hinzugefügt
    51. NewFormula.ContainerStack.First.SubKeyWords.Add(New Formula.KeyWord_Operator(Formula.KeyWord_Operator.OperatorType.Multiply))
    52. End If
    53. NewFormula.ContainerStack.First.SubKeyWords.Add(New Formula.KeyWord_Variable(i))
    54. End Select
    55. Next
    56. MessageBox.Show(NewFormula.ToString)
    57. End Sub
    59. Class Formula
    61. Public Property MainKeyWordContainer As KeyWord_Contaier
    62. Public Property ContainerStack As New Stack(Of KeyWord_Contaier)
    64. Public Sub New()
    65. MainKeyWordContainer = New KeyWord_Contaier
    66. ContainerStack.Push(MainKeyWordContainer)
    67. End Sub
    69. Public Sub LevelDown()
    70. 'Es wird eine Ebene tiefer gegangen
    71. Dim NewContainer As New KeyWord_Contaier
    72. ContainerStack.First.SubKeyWords.Add(NewContainer)
    73. ContainerStack.Push(NewContainer)
    74. End Sub
    76. Public Function LevelUp() As Boolean
    77. If ContainerStack.Count > 1 Then 'Es darf nur zurückgesprungen werden, wenn dadurch nicht der MainContainer vom Stack geholt wird
    78. ContainerStack.Pop()
    79. Return False 'Es wird zurückgegeben, ob der Vorgang in nicht in Ordnung war
    80. Else
    81. Return True
    82. End If
    83. End Function
    85. 'Zur einfacheren Darstellung
    86. Public Overrides Function ToString() As String
    87. Return String.Join("", MainKeyWordContainer.SubKeyWords)
    88. End Function
    90. MustInherit Class KeyWordBaseClass
    92. End Class
    94. Class KeyWord_Variable
    95. Inherits KeyWordBaseClass
    97. Public Property VariableName As Char
    99. Public Sub New(ByVal Source As Char)
    100. VariableName = Source
    101. End Sub
    103. Public Overrides Function ToString() As String
    104. Return VariableName
    105. End Function
    107. End Class
    109. Class KeyWord_FixedNumber
    110. Inherits KeyWordBaseClass
    112. Public Property Number As Integer
    114. Public Sub New(ByVal Source As Char)
    115. 'Chars können nicht einfach so in Integer konvertiert werden. Strings schon.
    116. Number = CInt(Source.ToString)
    117. End Sub
    119. Public Sub Extend(ByVal NewChar As Char)
    120. 'z.B. "123" wird zu "1234"
    121. Number = Convert.ToInt32(Number.ToString & NewChar)
    122. End Sub
    124. Public Overrides Function ToString() As String
    125. Return Number.ToString
    126. End Function
    128. End Class
    130. Class KeyWord_Operator
    131. Inherits KeyWordBaseClass
    133. Public Enum OperatorType As Integer
    134. Add = 1
    135. Subtract = 2
    136. Multiply = 3
    137. 'Und so weiter
    138. End Enum
    140. Shared OperatorChars As New Dictionary(Of Char, OperatorType)
    142. Shared Sub New()
    143. 'Hier wird das Dictionary initialisiert (diese Sub New ist Shared!)
    144. OperatorChars.Add("+"c, OperatorType.Add)
    145. OperatorChars.Add("-"c, OperatorType.Subtract)
    146. OperatorChars.Add("*"c, OperatorType.Multiply)
    147. 'Und so weiter
    148. End Sub
    150. Public Property Type As OperatorType
    152. Public Sub New(ByVal NewType As OperatorType)
    153. Type = NewType
    154. End Sub
    156. Public Overrides Function ToString() As String
    157. Return OperatorChars.Where(Function(Duh) Duh.Value = Type).First.Key.ToString
    158. End Function
    160. Public Shared Function IsOperator(ByVal TestChar As Char) As Boolean
    161. Return OperatorChars.ContainsKey(TestChar)
    162. End Function
    164. Public Shared Function FromChar(ByVal Source As Char) As KeyWord_Operator
    165. If OperatorChars.ContainsKey(Source) Then
    166. Return New KeyWord_Operator(OperatorChars(Source))
    167. Else
    168. Throw New Exception 'Nicht zuordenbar (was eigentlich nie passieren kann, weil vorher überprüft wird, ob es überhaupt ein Operator ist)
    169. End If
    170. End Function
    172. End Class
    174. Class KeyWord_Contaier
    175. Inherits KeyWordBaseClass
    177. Public Property SubKeyWords As New List(Of KeyWordBaseClass)
    179. Public Overrides Function ToString() As String
    180. Return "(" & String.Join("", SubKeyWords) & ")"
    181. End Function
    183. End Class
    185. End Class
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Iwie brauchst Du eine iterative Funktion.
    Du musst Dich von einem Item bis zum kommunizierenden Item durchhangeln und dann diesen Ausdruck wieder untersuchen, bis Du auf das "Atom" gestoßen bist.
    Also:
    *, / bis *, /
    +, - bis +, -, *, /
    ( bis )
    usw.
    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!

    Wow was für eine Informationsflut! Danke erstmal für so viele Ansätze/Vorschläge und Beispiele! Alles was man sich nur wünschen kann.
    Werde mich mal von oben nach unten durch arbeiten und sehen was bei rum kommt.

    Nur ein paar Fragen hätte ich da noch:

    @hal2000: Hast Du zum erstellen und verwenden einer Grammatik weiterführende Infos?
    Konnte bis jetzt mit Google nichts erklärendes (sondern nur fragende) finden.
    Klingt total interessant eine "Grammatik erstellen".

    @RodFromGermany: "iterative Funktion" Schon wieder etwas neues wenn ich mich nicht
    irre, laut Wikipedia geht es bei solch einer Funktion um das abarbeiten mithilfe von Schleifen.
    Meinst Du damit ich sollte eine Funktion schreiben welche im ersten Durchgang z. B. nach
    den Operatoren sucht, im Nächten Durchgang nach den Variablen etc.? (Denke so ist es eher nicht gemeint, oder?)

    Genau.
    1. Input: a + (b + c) * (d + e)
    2. Input: (b + c)
    3. Input: (d + e)
    usw.
    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!

    Was soll dein Parser machen?
    Willst du Terme der Form zb ax^2 + bx + c wo a,b,c schon gegeben sind oder einen Parser, der wirklich oben genannten Term einliest? Letzteres ist nämlich ungleich schwieriger. Für ersteres könnte ich dir behilflich sein, habe auch hier im Showroom eine Library gepostet: [Release] Quadsoft.ExpressionParser - Ein Parser für mathematische Ausdrücke , die genau das kann (ersteres, also Terme wie 2,4x^2+4x+5 für gegebene x berechnen.)

    Nur als kleiner Einwurf: Vor einiger Zeit wollte ich mich hier reinlesen, hab's aber aus Zeitgründen bis jetzt rausgezögert.
    Expression Class
    Expressions-Sample

    VB.NET-Quellcode

    1. Imports System.Linq.Expressions
    3. Module Module1
    5. Sub Main()
    6. Dim multiplyXP As Expression = Expression.Multiply(
    7. Expression.Constant(5), Expression.Constant(9))
    9. Dim AddXP As Expression = Expression.Add(
    10. multiplyXP,
    11. Expression.Constant(4))
    13. Console.WriteLine(AddXP.ToString())
    14. Console.WriteLine(
    15. Expression.Lambda(Of Func(Of Integer))(AddXP).Compile()())
    17. Console.ReadKey()
    18. End Sub
    20. End Module

    Ist garantiert nicht die fertige Lösung, aber vielleicht ein weiterer Schritt in die Richtung.

    @Eistee:
    Mir ist soweit keine Seite bekannt (ich hab auch nicht direkt gesucht), die dir beim Erstellen einer Grammatik hilft. Das alles ist reine Theorie, die nur auf dem Papier / im Kopf entsteht. Ein guter Einstieg ist eventuell der Wikipedia-Artikel "Formale Grammatik". Dieser Thread könnte auch helfen: mikrocontroller.net/topic/150590. Am weitesten kommst du mit Uni-Vorlesungsskripten zum Thema Compilerbau. Alle Programmiersprachen und deren Compiler basieren auf einer formalen Grammatik, die vom Parser benutzt wird, um z.B. Syntaxfehler zu finden. Genauso kannst du dir eine Grammatik für mathematische Ausdrücke formulieren - einfach ein bisschen basteln. Verstehe aber bitte erst das Konzept, wie die sogenannten Terminale und Nichtterminale zusammenspielen, sonst geht das in die Hose.
    Gruß
    hal2000

    Und ich dachte der RegEx Berg wäre viel Arbeit :D
    Aber wenn man es macht, sollte man es schon min. halbwegs richtig machen.
    (Habwegs weil ich es nicht zu 100% so umsetzen kann wie es wohl richtig wäre).
    Sobald es Fortschritt gibt meld ich mich mal.

    Hihi - ich weiß schon, warum ich um selbstgebastelte Formel-Parserei immer schön ein Bogen mach. ;)
    Das ist mindestens ein Semester Vorlesung, das liest man sich nicht ma eben so an. Und hast du die Theorie formaler Sprachen begriffen, dann ist noch nix implementiert, da gibts dann iwas mit Tokenizer, Parser, dann wern womöglich ExpressionTrees gebildet, die dann letztendlich ein Ergebnis ausgeben können.
    Als (mich abschreckendes) Beispiel mag dienen: Calculate von Konrad Rudolph.
    Wie gesagt: ich bin lieber faul und mach wie in post#8 erwähnt.

Facebook
Telefonspende