Mathematische Ausdrücke parsen

Rab-Bit

Guten Morgen,

ich überlegen schon seit einiger Zeit, wie man am besten mathematische Ausdrücke parsen kann; also Ausdrücke mit den vier Grundrechenzeichen und Klammern, wie zum Beispiel 5*(2+2) .

Aber irgendwie fehlt mir eine gute Denkanregung. Mir ist klar, dass ich zuerst die Klammern und dann eben das Ganze ausrechnen muss (natürlich je Punkt-vor-Strich). Aber wie soll man das am besten umsetzen? Die Klammern können ja theoretisch unendlich verschachtelt sein ...

Eine Überlegung war es, dass ich sozusagen einen Stack (z.B. als verkettete Liste) aufbaue und Rechenoperationen darauf ablegen, solange die nächste Operation Vorang hat, beispielsweise wegen einer Klammer. Bei gleicher Priorität werden die Rechenoperationen vom Stack dann ausgeführt.
Oder ich analysiere erst die Klammern, d.h. suche mir zu jeder geöffneten die schließende Klammer, berechne die eingeklammerte Länge und fange dann an, die kürzeste Klammer aufzulösen usw. bis eben keine Klammer mehr vorhanden ist und dann muss ich nur noch die einfache Rechnung mit den Grundrechenarten auflösen.

Aber ich bin mir eben nicht sicher, ob diese Wege gut geeignet sind oder totaler Aufwand-Overkill. Deshalb würde es mich freuen, wenn jemand von euch einige gute Ideen zu dem Thema hat oder sich damit eventuell schon mal befasst hat.

Rab-Bit

knivil

Die Tutorials zu lex+yacc oder aber flex+bison sollten dir helfen.

mazal

Die Tutorials zu lex+yacc oder aber flex+bison sollten dir helfen.

Übertreib mal nicht. Sind ja nur mathematische Ausdrücke

Informier dich mal über "rekursiv absteigende Parser" bzw. "recursive descent parser", sollte für deine Zwecke vollkommen ausreichen.

Gruß

knivil schrieb:

Die Tutorials zu lex+yacc oder aber flex+bison sollten dir helfen.

na, diese dinger spucken richtig fette codes aus.
Rab-Bit: wenn du was fertiges suchst: google "expression evaluation filetype:c"
wenn dich die theorie interessiert: ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf

pointercrash**

Das hatten wir letztens schon einmal. Schau Dir mal den simple arithmetic expression evaluator an. Der ist sogar nachvollziehbar und nicht wirklich "oversized". Danke an +fricky, der den Link mal ausgegraben hat

knivil

Ich habe flex + bison damals genau dafuer benutzt, der produzierten Code ist auch nicht zum Verstaendnis gedacht, weil er eben automatisch generiert wurde (aber das was man in seine parser.y schreibt ist verstaendlich). Aber genau diese Sachen stehen halt im Manual bei den Beispielen, 2.1 Reverse Polish Notation Calculator, 2.2 Infix Notation Calculator oder 2.5 Multi-Function Calculator. Und das was an simple arithmetic expression evaluator nachvollziehbar ist, frage ich mich bei Funktionen mit 9 Parametern. Auch werden die wenigsten von symbolic expression (kurz: sexpr) gehoert haben (wo wir wieder bei Lisp waeren). Schaut man sich die Interna an, ... naja, die hier haben es etwas konsistenter geloest: http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ (Folge 7a und 7b glaube)

ich hab das schon mal auf mehrere arten gemacht:
- auf reiner stringersetzungsbasis
- auf levelbasis ( jede oeffnende klammer leitet einen neuen level ein )
- reverse polish notation

das effektivste, was ich kenne, ist die letztere variante.

Bashar

Rab-Bit schrieb:

Eine Überlegung war es, dass ich sozusagen einen Stack (z.B. als verkettete Liste) aufbaue und Rechenoperationen darauf ablegen, solange die nächste Operation Vorang hat, beispielsweise wegen einer Klammer. Bei gleicher Priorität werden die Rechenoperationen vom Stack dann ausgeführt.

Das nennt sich Google: operator precedence parser.

Oder ich analysiere erst die Klammern, d.h. suche mir zu jeder geöffneten die schließende Klammer, berechne die eingeklammerte Länge und fange dann an, die kürzeste Klammer aufzulösen usw. bis eben keine Klammer mehr vorhanden ist und dann muss ich nur noch die einfache Rechnung mit den Grundrechenarten auflösen.

Klingt nach wildem gefrickel

Bashar schrieb:

Oder ich analysiere erst die Klammern, d.h. suche mir zu jeder geöffneten die schließende Klammer, berechne die eingeklammerte Länge und fange dann an, die kürzeste Klammer aufzulösen usw. bis eben keine Klammer mehr vorhanden ist und dann muss ich nur noch die einfache Rechnung mit den Grundrechenarten auflösen.

Klingt nach wildem gefrickel

jepp!
das gefrickel kann man etwas weniger wild machen, indem man zuerst die letzte oeffnende klammer findet. die erste schliessende klammer muss dann zur letzten öffnenden zugehören. zeugs auswerten, zeugs 'ruchtscht' somit automatisch in das nächst äußere klammernpaar, ... etc.

icke wa ey schrieb:

ich hab das schon mal auf mehrere arten gemacht:
- auf reiner stringersetzungsbasis
- auf levelbasis ( jede oeffnende klammer leitet einen neuen level ein )
- reverse polish notation
das effektivste, was ich kenne, ist die letztere variante.

ja, für maschinen.

+fricky schrieb:

ja, für maschinen.

kennst du eine schnellere variante als die upn-notation ?

i.w.e. schrieb:

kennst du eine schnellere variante als die upn-notation ?

für was schnell? zum parsen?

+fricky schrieb:

i.w.e. schrieb:

kennst du eine schnellere variante als die upn-notation ?

für was schnell? zum parsen?

jo, zum parsen und zum berechnen.

Rab-Bit

Vielen Dank für die vielen Antworten. Ich habe den normalen Ausdruck (Infix) jetzt also erst mal mit dem Shunting-Yard Algorithmus in die Umgekehrte Polnische Notation umgewandelt und diese dann ausgerechnet. Funktioniert auch soweit.
Ist es sinnvoll das so zu machen? Ein bisschen überflüssig ist es ja doch, dass ich das Ganze nun zweimal auswerten muss (zuerst als Infix und dann als UPN). Das zweite könnte ich mir vielleicht auch sparen, wenn die die Berechnung gleich in den Shunting-Yard Algorithmus einbaue, oder? Also wenn ich einen Rechenoperator zum Output hinzufügen würde, könnte ich ihn auch gleich auf die letzten zwei Operanden anwenden. Denn dass es zweimal geparst werden muss, ist ja eine frevelhaften Ressourcenverschwendung.
Also vielen Dank für die Hilfe. Die verlinkten Seiten werde ich mir auch noch mal anschauen. Und wenn mein jetziger Weg ganz verkehrt ist, bitte noch mal korrigieren.

mazal

Vielen Dank für die vielen Antworten. Ich habe den normalen Ausdruck (Infix) jetzt also erst mal mit dem Shunting-Yard Algorithmus in die Umgekehrte Polnische Notation umgewandelt und diese dann ausgerechnet. Funktioniert auch soweit.

Glückwunsch

Ist es sinnvoll das so zu machen? Ein bisschen überflüssig ist es ja doch, dass ich das Ganze nun zweimal auswerten muss (zuerst als Infix und dann als UPN). Das zweite könnte ich mir vielleicht auch sparen, wenn die die Berechnung gleich in den Shunting-Yard Algorithmus einbaue, oder? Also wenn ich einen Rechenoperator zum Output hinzufügen würde, könnte ich ihn auch gleich auf die letzten zwei Operanden anwenden. Denn dass es zweimal geparst werden muss, ist ja eine frevelhaften Ressourcenverschwendung.

Wenns funktioniert ist doch gut. Du wirst ja denk ich mal keine solchen Monster parsen, dass das zu einem Problem wird. Zu Shunting-Yard kann ich leider nix sagen, da ich den nicht kenne.

Hab mal schnell ein nettes Tutorial zu LL(k)-Parsing ergooglet. Mit LL(k)-Parsing, kriegt man ein bischen mehr hin, als nur so eine poplige Term-Grammatik hin. Ist zwar C# aber das kriegst du schon hin

http://www.itu.dk/people/kfl/parsernotes.pdf

Gruß

der shunting yard algo dient doch dazu, um aus dem term die upn form zu machen.
da kannst du nicht einfach zwischendurch ein paar werte berechnen.
erst wenn alles auf dem stack ist, kannst du evtl. teilweise vereinfachen.

ist das dingen erstmal in der upn, ist deine berechnunsmaschine unschlagbar. angenommen du möchtest einen funktionsgraphen plotten, dann brauchst du nur die zeiger der parameter zu holen und die werte direkt auf dem upn-stack zu ändern, ohne den ganzen term neu parsen zu müssen.

Rab-Bit

@mazal
Danke, ich werde mir das mal anschauen. Aber so komplex ist es nicht, was ich letztendlich parsen will.

i.w.e. schrieb:

der shunting yard algo dient doch dazu, um aus dem term die upn form zu machen.
da kannst du nicht einfach zwischendurch ein paar werte berechnen.
erst wenn alles auf dem stack ist, kannst du evtl. teilweise vereinfachen.

Es muss nicht alles auf dem Stack sein. Sobald man dem Output einen Operator hinzufügt, steht doch schon fest, auf welche Zahlen er angewandt werden muss (idR auf die letzten beiden Zahlen). Also kann man das auch gleich machen. Funktioniert gut und ist eben kürzer als Infix -> UPN -> Ergebnis. Man hat mit meiner Methode eben zwei Stacks, einen für die Zahlen und einen für die Operatoren. Und bei korrekter Eingabesyntax ist der Operatorenstack um Schluss leer und auf dem Zahlenstack liegt das Ergebnis.