Parser UPN

[simonko]

Hab heute eine Methode gefunden mit der man ganz leicht einen Matheparser schreiben kann.
Es gibt eine sog. Postfix Notation. 2+2 währe dem nach 22+. Diese Notation macht klammern überflüssig.
und man kann von links nach rechts einfach durchrechnen. zahlen pushed man auf einem stapel. kommt ein rechenzeichen popt :) man die letzten zwei zahlen und führt die operation aus.
z.b
222+*
24*
8

Das einzige Problem ist jetzt einen normalen ausdruck in UPN umzuwandeln. Ist aber mit stapeln auch ganz leicht. man geht den ausdruck von links nach rechts durch. kommt eine zahl wird die einfach ausgegeben.
rechenzeichen werden auf einem stack gepusht insofern das erste rechenzeichen auf dem stapel nicht eine höhere priorität hat als das was hinzugefügt werden muss. hat es eine höhere priorität wird der stapel ausgegeben nach dem LIFO prinzip und das andere rechenzeichen gepusht.
am ende wird der stapel geleert.
Prioritäten:
+ - :1
* / :2
^3 :3

z.b 2+2*3
2
2 // + pushen
22
22 // * pushen
=>
223*+

[alcaeus]

Moin simonko,

schoen und gut, aber ich hab da noch eine Frage: was ist wenn ich 23+2 habe? Das wuerde ja 232+ geben. Sobald ich aber 232+ habe, weiss ich ja nicht mehr, wo das Rechenzeichen reinkommt. Da gibts dann 2 Moeglichkeiten: 23+2 bzw. 2+32. Wenn ich eine dreistellige Zahl habe, wirds nur noch komplizierter. Wie wuerde man sowas handhaben?

Greetz
alcaeus

[pirechner]

@alcaeus: Die einzelnen zahlen müssen dann halt in ein Array!

Was mir bei dem Verfahren, welches wir sogar im Infounterricht gelernt haben, noch Schwierigkeiten macht sind KLammern und Ausdrücke wie 'tan()' z.B.
Sonst ist das Verfahren der Umgekehrt Polnischen Notation sehr einfach!

[jbg]

Also mit EBNF und rekursiver Programmierung ist das eigentlich gar kein Problem.

Code:

  <Ausdruck> ::= <Term> { [ "+" | "-" ] <Term> }*

  <Term> ::= <Faktor> { [ "*" | "/" ] <Faktor> }*

  <Faktor> ::= <Zahl> | <Variable> | <Funktion> | "(" <Ausdruck> ")"

  <Funktion> ::= <Name> "(" <ParameterListe> ")"

[ a | b ] => a oder b
{ a }*    => 0 oder n Mal a

Damit hat man durch die Aufteilung von +|- und *|/ in zwei Bereiche neben der Klammersetzung auch gleich die Punkt-vor-Strich-Regel erschlagen.

Hier mal ein Ausschnitt dafür

Delphi-Quellcode:

function Term: IExprNode;
var
  op: IToken;
  fak: IExprNode;
begin
  Result := Faktor; // <Faktor>
  while Match([tkMultiply, tkDivide]) do // { [ "*" | "/" ] <Faktor> }*
  begin
    op := Look; // aktueller Token nach op
    Next; // nächster Token
    fak := Faktor;
    Result := TExprNodeBinOp.Create(op, Result, fak); // Baum-Knoten erzeugen und zurückliefern
  end;
end;

Man kann sich so einen Baum aufbauen, den man danach nur noch durchlaufen muss und die werte Ausrechnet. Alternativ kann man sich das Aufbauen des Baums sparen und gleich mit einer Variable, die man jeder Funktion als var-Parameter mitgibt, rechnen.

[Robert Marquardt]

tan() stellt ueberhaupt kein Problem dar.
Der Fehler liegt in den Klammern. UPN braucht nicht nur keine sondern darf keine haben.
"12 tan" ist der korrekte Ausdruck. Der Operator folgt immer dem Operanden (bzw den Operanden).

[alzaimar]

@jbg: Die Abarbeitung des Syntaxbaumes ist nichts anderes als das Ausrechnen nach UPN-Notation.
Die Implementierung, so wie sie simonko erfunden hat, entspricht der eines simple precedence parsers. Die ist genauso gut oder schlecht, wie die manuelle Programmierung der BNF.

Der EBNF von jbg fehlt noch die Beschreibung von Potenzen (a^y).

Heutzutage nimmt man sich aber eher spezielle Programme, die sog. "Compiler Generatoren" und lässt die dann die richtige Implementierung erzeugen. Alles, was man da machen muss, ist, für jeden BFN-Ausdruck die Übersetzungsregel anzugeben. Das können Assemblerbefehle sein, oder eben die UPN-Notation. Ein einfacher UPN-Kalkulator nimmt sich dann den Input und berechnet das Ergebnis ("Wir basteln uns einen [Byte-code]-Interpreter"). Aber Du kannst eben genausogut aus dem Term ein kleines Assemblerprogrämmchen generieren lassen, welches du das Ergebnis berechnet ("Compiler").

[mh166]

Die UPN scheint es ja wirklich zu geben, also im Sinne von richtig verwendet. Soll heißen es muss ja irgendeine geschriebene Lösung für das Problem mit den Zahlen>9 bzw. Zahlen<-9 geben. Und was is eigentlich mit Dezimalzahlen? Und gemeinen Brüchen? Wie schreibt man den ganzen Quark in "normaler", non-virtueller Schrift (d.h. mit Bleistift auf Papier ;) )?

mfg, mh166

[simonko]

@mh166 die zahlen werden einfach auf einem stack gelegt.
und wenn du es auf einem blatt papier schreibst läßt du einfach leerzeichen. :)

[alzaimar]

Checkt doch mal die Sprache 'FORTH' das ist nichts anderes! Vermutlich gibts das als Java-Applet.
Da werden die Token durch Leerzeichen getrennt:
22 33 + 100 *
Ergebnis : 155

1 2 swap /
Ergebnis 2 (swap vertauscht die oberen beiden Stackelemente)

Natürlich kann man eigene Befehle definieren. Wie das geht, hab ich vergessen.

Die Kamerasteuerung der ersten Starwars-Filme (und auch bei Tron) wurde übrigens auf einem HP9826 (Motorola 68k CPU) unter FORTH programmiert.. Nur so, als Anekdote

[marabu]

Hallo alzaimar,

Zitat:

Zitat von alzaimar

22 33 + 100 *
Ergebnis : 155

5500 kommt eher hin.

Freundliche Grüße vom marabu