Mathematische Ausdrücke parsen

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.