Formel Parser

  • Formel Parser

    Für mein aktuelles Projekt muss ich Formeln, also z.B. 5+6, a/b+c usw. parsen. Für einfach Formeln, wie z.B. a+b sicherlich kein Problem, aber wie sieht die Sache dann bei ((a+b)*(c/2)+d)*3 aus? Ich könnte mich jetzt natürlich ein paar Tage oder eher Wochen hinsetzen und mir einen Formel Parser von Grund auf zusammen bauen, aber dafür muss es doch bestimmt fertige und ausgereifte Lösungen geben, oder etwa nicht? ?(

    Wenn jemand ein paar Tipps für einen fertigen Formel Parser hat, den man komplett, oder im Ansatz verwenden könnte, dann immer her damit. :))

  • RE: Formel Parser

    lad dir mal die Testversion von Mathematica - das ist ein recht guter "Formelparser" ;)
    Ansonsten lässt sich so eine Formel sehr sehr gut in einen binären Baum zerlegen! und dann sollte der Rest ja recht einfach sein *ggg*

    Max

  • RE: Formel Parser

    Original von snowman
    Ich würde das mit einem recursive descent parser machen. ist nicht so sehr schwer.

    Werde ich mir heute Abend auch mal anschauen. Da ich eh noch ein paar Erweiterungen in den Parser implementieren muss, werde ich mal schauen, welcher von beiden sich besser erweitern lässt. :))

  • RE: Formel Parser

    Vielleicht hilft auch NSScanner...

    Hier mal ein grobes Beispiel für recursive descent

    Quellcode

    1. - (id) scanAdd:(NSScanner *) sc
    2. {
    3. id left=[self scanMultiply:sc];
    4. while(YES)
    5. {
    6. if([sc scanString:@"+" intoString:NULL])
    7. {
    8. id right=[self scanMultiply:sc];
    9. left=... verarbeite left & right für "+"
    10. continue;
    11. }
    12. if([sc scanString:@"-" intoString:NULL])
    13. {
    14. id right=[self scanMultiply:sc];
    15. left=... verarbeite left & right für "-"
    16. continue;
    17. }
    18. else
    19. break;
    20. }
    21. return left; // Ergebnis von x+y-z...
    22. }
    24. - (id) scanMultiply:(NSScanner *) sc
    25. {
    26. id left=[self scanValue:sc];
    27. while(YES)
    28. {
    29. if([sc scanString:@"*" intoString:NULL])
    30. {
    32. ... gleiches Schema
    34. - (id) scanValue:(NSScanner *) sc
    35. {
    36. id value;
    37. double val;
    38. // hier kommt der Trick:
    39. if([sc scanString:@"(" intoString:NULL])
    40. {
    41. value=[self scanAdd:sc]; // und schon ist (1+2)*3 erlaubt
    42. if(![sc scanString:@")" intoString:NULL])
    43. error...
    44. return value;
    45. }
    46. // und hier die einfachen Werte
    47. if([sc scanDouble:&val])
    48. return [NSNumber numberWithDouble:val];
    49. else
    50. // wen keine Zahl dann vielleicht Variablename (geht mit scanCharactersFromSet:)
    51. error
    52. }
    Alles anzeigen

  • Wenn du nach UPN wandelst, hast du intern ja schon die Formelstruktur erzeugt. Dann brauchst du kein UPN mehr. Einfache Formeln, also welche nur mit binären Operatoren, ohne Vorzeichen, ohne Vorrangregeln lassen sich einfach implementieren. Aber das wird ihm nicht reichen. Und so etwas wie:

    "-5+a--3"

    ist dann nicht mehr ganz so einfach. Ich habe das mal eingeschränkt in GFA programmiert., vor Ewigkeiten. Demnächst kommt auch noch ein Parser für bool'sche Ausdrücke auf mich zu. Aber das ist _deutlich_ einfacher.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • Original von asrael
    Ich wuerde die Formel nach UPN wandeln, dann laesst sich das gut ausrechnen.

    In meinem Beispielcodefragment oben würde das heissen

    Quellcode

    1. left=... verarbeite left & right für "+"


    ersetzen durch

    Quellcode

    1. left=[NSString stringWithFormat:@"%@ %@ +", left, right]


    -- hns

  • Du musst sie gar nicht nach irgendwas wandeln. Um sie zu wandeln, musst du erst die "menschliche Schreibweise" analysieren. Dabei machst du dir ja irgendeinen Baum. Auf dem rechnest du. Eine Umwandlung nach UPN um dann wieder auf UPN zu rechnen, ist von hinten durch die Brust ins Auge. Übrigens dürfte die Baumstruktur ziemlich genau der >UPN-Notation entsprechen. ;)

    Ich weiß noch rudimentär wie ich es gemacht habe. Das Problem war, dass es Klammern, uniäre und binäre Opertaoren gab, so dass sich das nicht so einfach in left & right trennen ließ.

    Beispiel:

    5 * (-3 + sin(4+2))

    parse( formel )

    // Für einfache Klammerung auf höchester Ebene
    -> parse(Klammerstring) -> parse (-3 + sin(4))
    -> Ersetze Klammerstring durch parse-Ergebnis
    // Jetzt sind die Klammern weg. Tipp: Eine KLammerung erkennt man daran, dass dort der String beginnt oder ein Rechenzeichen davor ist.

    // Für Klammer-Funktion (Wurzel(), log(), sin() usw)
    -> parse(Klammerstring) in diesem Falle: 4+2 -> 6
    -> errechne Funktion für den errrecheten Klammerstring sin(6)
    -> Ersetze Klammerfunktion durch das Ergebnis
    // Jetzt sind keine Funktionen mehr da

    // Für _niederwertigste_ (+,-) Zeichen
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Errechne Ergebnis und setze für rechts und links ein.,

    // Für Multplikation/Division
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Errechne Ergebnis und setze für rechts und links ein.,

    // Für Potenzen
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Errechne Ergebnis und setze für rechts und links ein.,

    // Für Zahl mit Vorzeichen
    -> gebe -Zahl zurück

    // Für reine Zahl
    -> gebe Zahl zurück

    So war in etwa die Struktur.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • Tom, ich habe in der 10. Klasse für mein Info-Projekt genau so einen parser geschrieben, der genau so funktioniert hat. Damals war ich stolz hab meine 1 und die Lobe der Lehrer bekommen. Dann war ich an der Uni. Ich wollte das Projekt weiter machen und hab das nem Dozenten gezeigt. Zurück kam sowas wie: "Das könnte selbst mein Sohn besser und der ist 6." Ich hab's nicht verstanden, hab was mit OpenGL und fraktalen gemacht und mich nur mal kurz mit term-analyse beschäftigt. mein tip für so ein Problem: erst einen Baum machen und den dann ausrechnen - in echtzeit und so, aber nich rekursiv beim einlesen ;)
    Wenn man lustig ist, kann man dann auch noch parameter einbauen oder den term vereinfachen oder so. Ich bin auf dem Gebiet bei weitem kein Fachmann, aber es gibt sicher einige ressourcen da draußen im Internet, wo solche sachen und verschiedene Modelle erklärt werden...

    Max

  • Bei mir war es etwas die gleiche Zeit.

    Dein Prof hat aber sicher erkannt, dass es für den Algo ganz gleich ist, ob man einen Baum anlegt oder die (Teil-)ergebnisse gleich einsetzt, nicht wahr?

    War irgendwie ein komischer Prof. War das wirklich Informatik?
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • Computergrafik und Algebra, ich glaube, das war er. Hat auch nen Doktor über irgend so ein Thema geschrieben und ein Buch über die Integration von Mathematica und C. *Glaube* der hatte das drauf ;)

    Mit einem Baum kannst du viel mehr machen und es geht auch viel schneller, das dann auszurechnen, würde ich tippen. Außerdem ist es wesentlich sauberer :]

    max

  • Öhm, entweder du hast mich nich verstanden, oder dein Prof dich oder du deinen Prof. Nochmal: Das ändert nichts an dem Algo:

    Ob du nun schreibst

    // Für Multplikation/Division
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Errechne Ergebnis und setze für rechts und links ein.,

    Oder schreibst
    // Für Multplikation/Division
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Erzeuge Mul/Div-Knoten mit Nachfolgern rechts/links

    ist keine Frage des Algorithmusses.

    Meinetwegen kann er das auch loggen, streamen oder sonstwas tun. Der Algo bleibt der gleiche.

    Got it?
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • naja, nee. Der Unterschied ist ja, dass du bei der einen Methode erst den gesamten Term in einen Baum schreibst und dann einfach durchrechnest. Hier musst du erst Multiplikation und dann Addition machen, dort ist die Reihenfolge egal, da du ja einen baum hast. Außerdem könntest du mit einem Baum viel mehr machen. Du könntest dann recht einfach Variablen reinbringen und dann echt equivalent umformen oder zumindest vereinfachen. Das geht mit der anderen Methode nicht gut.

    Du ich glaube wir beide haben davon keinen blassen schimmer und deshalb würde ich sagen, dass die Diskussion nicht sehr viel bringt. Ich hatte die selbe methode, hab abererkannt, dass sie sch**** war und weiß es aber auch nicht besser. Im studium werd ich dass sicher noch bis zum abwinken machen ;)

    Max

  • Ich weiß jetzt nicht genau, wo der Unterschied leigt:
    Ob du nun schreibst

    // Für Multplikation/Division
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Errechne Ergebnis und setze für rechts und links ein.,

    Oder schreibst
    // Für Multplikation/Division
    -> Teile in rechts und links
    -> parse(rechts)
    -> parse(links)
    -> Erzeuge Mul/Div-Knoten mit Nachfolgern rechts/links

    ist keine Frage des Algorithmusses.

    Vielleicht kannst du mir das erklären. Die untere Variante erzeugt einen Baum!

    Ich glaube, einer von uns beiden hat davon keinen Schimmer. ;)
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • nehmen wir an du hast das hier:

    Quellcode

    1. 1 * (2 + 3)

    Dann wird als erstes der Baum erzeugt:

    Quellcode

    1. *
    2. / \
    3. 1 +
    4. / \
    5. 2 3


    und DANN wird gerechnet, wenn du damit fertig bist:
    Stufe 1:

    Quellcode

    1. *
    2. / \
    3. 1 5

    Stufe 2:

    Quellcode

    1. 5


    -> Ergebnis = 5
    Du versuchst gerade krampfhaft den Baum in deine syntax zu quetschen, was aber nicht geht, da du ganz anders rangehen musst! Ich bin da kein Profi, aber so in die richtung gehts

    Max