Ein Rechenausdruck kann wieder Operand sein:
Infix: 2+3*4
Postfix: 2 3 4 * +
| Stapel | 2 | 3 2 |
4 3 2 |
12 2 |
14 | (leer) |
| gelesenes Zeichen | 2 | 3 | 4 | * | + | . (Ausgabe in Forth) |
Diesen Taschenrechner gibt es auch als Programm im Internet: Auf der HP-Emulatorseite gibt es Freeware-Programme und Emulatoren zum Auslesen des eigenen Taschenrechner-ROMs.
| Zeichen, von der Eingabe gelesen | Aktion |
| Operand | In Ausgabe (Postfix) schreiben |
| Klammer auf ( | Auf Stapel legen |
| Klammer zu ) | Solange Stapel nicht leer, wiederhole: Holen eines Zeichens (Pop) Wenn Zeichen nicht (, schreib es auf Ausgabe Verlasse die Schleife, wenn Zeichen ( ist |
| Operator neuerOp | Wenn Stapel leer, Push(neuerOp) Sonst: Solange Stapel nicht leer, wiederhole: Holen eines Zeichens (Pop) Wenn Zeichen ( ist, lege es wieder auf den Stapel, oder Wenn Zeichen ein Operator opTop ist, und wenn opTop<neuerOp, so Push(opTop), oder wenn opTop>=neuerOp, so opTop zur Ausgabe Verlasse die Schleife, wenn opTop<neuerOp, oder das Zeichen ist ( Push(neuerOp) |
| keine weiteren Zeichen | Solange Stapel nicht leer, Pop(zeichen), zeichen zur Ausgabe |
Code (Oberon-2):
(*******Anfang*************Auswertung einer Eingabe*****************************)
PROCEDURE Operand_erhalten(neuerOp:CHAR;rang1:INTEGER);
(* Operator
neuerOp von der Eingabe gelesen, sein Rang ist rang1 *)
VAR opTop:CHAR; (*
Operator, vom Stapel zu holen; sein Rang ist rang2 *)
rang2:INTEGER; (*
Rang: +-...1; */...2 *)
BEGIN
IF Leer()
THEN Push(neuerOp) ; (* wenn
Stapel leer, dann neuerOp dorthin *)
ELSE (* nicht leer*)
REPEAT
Pop(opTop); (*
wenn nicht, dann Pop zum Vergleichen *)
IF opTop='('
THEN Push(opTop); (*
Klammer gleich wieder zurück *)
ELSE
IF ((opTop='+')
OR (opTop='-'))
THEN
rang2:=1
ELSE
rang2:=2
END;
IF rang2<rang1 (*
Operationszeichen vergleichen ihren Rang
*)
THEN
Push(opTop) (* Operation hatte Vorrang, warten *)
ELSE
Strings.AppendChar(ausgabe,opTop) (* kein Vorrang, herausschieben
...*)
END;
END; (*IF opTop='('*)
UNTIL ((rang2<rang1) OR (opTop='(') OR
Leer()) ;
(*
...bis Klammer oder höherer Rang oder leer *)
Push(neuerOp)
END (*IF Leer()*)
END Operand_erhalten;
PROCEDURE Klammerzu_erhalten(ch:CHAR); (* rechte
Klammer von der Eingabe erhalten*)
VAR chx:CHAR;
BEGIN
IF ~Leer() THEN
REPEAT (*
alles raus bis zur ( *)
Pop(chx);
IF chx#'(' THEN Strings.AppendChar(ausgabe,chx)
END
UNTIL chx='(' (*
Klammerebene erreicht*)
END;
END Klammerzu_erhalten;
PROCEDURE in_to_post; (*
Infixaudruck in Postfixausdruck wandeln*)
VAR i:INTEGER;
ch:CHAR; (* gelesenes Zeichen*)
BEGIN
ausgabe:='';
Out.String('Eingabe:');Out.String(eingabe);Out.Ln;
FOR i:=0 TO Strings.Length(eingabe)-1 DO
ch:=eingabe[i];
Out.String('Stapel für ');Out.Char(ch);Out.String('
->top: ');Stapel_anzeigen; HALT(0);
CASE ch OF
'+','-':Operand_erhalten(ch,1) |
'*','/':Operand_erhalten(ch,2) |
'(' :Push(ch) |
')' :Klammerzu_erhalten(ch)
ELSE Strings.AppendChar(ausgabe,ch)
END; (*CASE*)
END; (*FOR*)
WHILE ~Leer() DO
Pop(ch);
Strings.AppendChar(ausgabe,ch)
END;
Out.String('Stapel am Ende: ');Stapel_anzeigen;
END in_to_post;
(*******Ende*************Auswertung einer Eingabe*****************************)
| Zeichen, vom Ausdruck gelesen | Aktion |
| Operand | Auf den Stapel legen (Push) |
| Operator | Zwei Operanden vom Stapel holen, den Operator darauf anwenden und das Ergebnis auf den Stapel legen |
Code (Oberon-2):
(*******Anfang***********Berechnung eines Postfixausdrucks********************)
PROCEDURE ParsePostfix(postfixeingabe:zeichenkette):REAL;
(*
Eingabe: Postfix-Zeichenkette, Ausgabe: Ergebnis*)
VAR i:INTEGER; (*Zähler*)
ch:CHAR;
num1,num2,zwergebnis:REAL; (*Operanden, (Zwischen-)Ergebnis
der Rechnung*)
BEGIN
zahlStapel_init;
FOR i:=0 TO Strings.Length(postfixeingabe)-1 DO
ch:=postfixeingabe[i];
Out.String('Stapel (->top:');zahlStapel_anzeigen;
HALT(0);
IF ((ch>='0') & (ch<='9'))
THEN zahlPush(ORD(ch)-48) (*
Ziffer als REAL auf Stapel*)
ELSE
zahlPop(num2); (*wenn
keine Ziffer, dann 2 Operanden vom Stapel holen*)
zahlPop(num1);
CASE ch OF
'+':zwergebnis:=num1
+ num2 | (* Reihenfolge beachten *)
'-':zwergebnis:=num1
- num2 |
'*':zwergebnis:=num1
* num2 |
'/':zwergebnis:=num1
/ num2
ELSE
zwergebnis:=0.0
END; (*CASE*)
zahlPush(zwergebnis)
END; (*IF*)
END; (*FOR*)
zahlPop(zwergebnis);
RETURN zwergebnis
END ParsePostfix;
(*******Ende*************Berechnung eines Postfixausdrucks********************)