UPN zum math. Terme parsen?

[Gast]

Hallo!

Schreibe gerade an einem mathematisch angehauchten Projekt und stehe nun vor der Aufgabe, mathematische Ausdrücke mit den 4 Grundrechenarten zu parsen. Einfaches Beispiel: (4+3)*5

Habe etwas recherchiert wie man sowas macht und bin dann auf die inverse polnische Notation gestoßen. Wenn man diese einmal hat, so braucht man ja nur noch einen Stack und die Sache ist gegessen.

Haltet ihr die IPN/UPN für ein gutes Mittel?

Mein Problem: ich dachte, ich hätte die UPN verstanden...

(4+3)*5 wären ja 4 3 + 5 *

Da pushe ich 4 und 3 auf meinen Stack, führe beim + die Addition mit 2 mal pop als Operanden durch und pushe das Ergebnis wieder auf den Stack, pushe die 5 drauf, poppe beim * 2 mal und multipliziere, Ergebnis auf den Stack und fertig.

Exakt solch ein Term ist das Standardbeispiel im Netz für die UPN, schon mehrmals gesehen - erst ne Klammer mit Addition drin und danach ne Multiplikation.

Wie würde die Notation aber bei 5*(4+3) aussehen? 5 4 * 3 + wird es ja nicht sein, sonst funktioniert Punkt vor Strich nicht...

Falls der Weg über Stack und UPN ein probates Mittel ist: die Hauptschwierigkeit ist dann wohl, die UPN überhaupt notiert zu bekommen. Gibt es da ein Schema, welches sich einfach erklären lässt?

Danke!

[Trap]

5*(4+3) wird zu 5 4 3 + *

Man kann auch die umgekehrte Variante mit Klammern nehmen, dann hat man die S-Expressions aus Lisp: (* 5 (+ 4 3))
Die haben den Vorteil, dass sie mit komplexeren Funktionen besser lesbar bleiben, aber für Grundrechenarten funktioniert UPN genauso.

In beiden Fällen bleiben die Zahlen in der gleichen Reihenfolge wie beim Infix-Ausdruck, die Operatoren bewegen sich entsprechend.

Achso: Um Infix-Ausdrücke in UPN zu wandeln erstellt man einen Term-Baum und durchläuft den in Postfix-Reihenfolge.

[Markus89]

Mann kann das auch in folgender Art parsen und in Code umsetzen.

Zuerst muss man die Eingabe in Symbole umsetzen können (Zahlen, Operatoren, Klammern, ...). Das geht ja auch noch ziemlich einfach.

Man teilt die Formel ein in Ausdruck, Term und Faktor, wobei:

Expression = [Sign] Term {Sign Term}
Term = Factor {* | / Factor}
Factor = Number | (Expression)

Um die Formel in Code umzusetzen muss man dann nurnoch einmal die Funktion aufrufen, die einem den Ausdruck umsetzt. Es wird dann automatisch die Postfix-Notation benutzt.

Der folgende Code benutzt GetNextSymbol(Symbol, IntegerValue) um das nächste Symbol aus der Formel zu holen. Falls dies eine Zahl ist, steht sie in IntegerValue und Symbol ist sbIntegerValue.


function Expression: Boolean;

function Term: Boolean;

function Factor: Boolean;
begin
Result:= False;
if (Symbol = sbIntegerValue) then begin
AppendCode(PUSH, IntegerValue);
GetNextSymbolSymbol, IntegerValue);
end
else if (Symbol = sbOpenBracket) then begin
GetNextSymbol(Symbol, IntegerValue);
Expression();
ExpectSymbol(sbCloseBracket);
GetNextSymbol(Symbol IntegerValue);
end;
Result:= True;
end;

// Term
var
Operation: TSymbol;
begin
Result:= False;
Factor();
while (Symbol in [sbMultiply, sbMod, sbDiv]) do begin
Operation:= Symbol;
GetNextSymbol(Symbol, IntegerValue);
Factor();
case Operation of
sbMultiply: AppendCode(MUL);
sbDiv: AppendCode(DIV);
sbMod: AppendCode(MOD);
end
end;
Result:= True;
end;

//Expression
var
Operation: TSymbol;
begin
Result:= False;
if (Symbol in[sbPlus, sbMinus]) then begin
Operation:= Symbol;
GetNextSymbol(Symbol, IntegerValue);
Term();
if (Operation = sbMinus) then
AppendCode(NEG)
end else
Term();
while (Symbol in[sbPlus, sbMinus]) do begin
Operation:= Symbol;
GetNextSymbol(Symbol, IntegerValue);
Term();
case Operation of
sbPlus: AppendCode(ADD);
sbMinus: AppendCode(SUB);
end;
end;
Result:= True;
end;

Vielleicht hilft es dir ja weiter.

[Gast]

Falls du Java oder C# oder sowas nutzt schau dir mal Groovy und/oder AntLR an, die bieten dir genau sowas und sind schnell auf kompliziertere Terme erweiterbar...

[Gnafoo]

Ich würde auch ANTLR empfehlen. Schau dir mal das Kurzintro in deren Wiki an. Das ist im Prinzip genau deine Aufgabenstellung:

http://www.antlr.org/wiki/display/ANTLR3/Five+minute+introduction+to+ANTLR+3