Lineare Datenstrukturen (Der Stack 2 )

Anwendung 

Ein stapelverarbeitender Taschenrechner verwendet einen Stack zur Auswertung von arithmetischen Ausdrücken. Dazu muss dem Taschenrechner ein gültiger Postfix-Ausdruck übergeben werden.

gültige Postfix - Ausdrücke 

Eine Folge von Operanden (Zahlen) und Operatoren (

,

,

,

) ist ein gültiger Postfix-Ausdruck, wenn

• die Zahl der Operanden genau um eins größer ist als die Zahl der Operatoren und
• es links von jeder Position mindestens einen Operanden mehr gibt als Operatoren.

Welche der folgenden Postfix-Ausdrücke sind gültig?

 

Wie wertet ein stapelverarbeitender Taschenrechner einen Postfix-Ausdruck aus?

Arbeitsweise 

Die Folge von Operanden und Operatoren wird von links nach rechts abgearbeitet:

• ein Operand wird immer auf den Stack gelegt (push).
• liegt ein Operator vor, so werden die letzten beiden Operanden vom Stack geholt (pop) und mit dem Operator verknüpft.
• Das Ergebnis wird wieder auf den Stack gelegt (push).
• Am Ende enthält der Stack genau eine Zahl: die Auswertung des Postfix-Ausdrucks.

Beispiel 

Der Postfix-Ausdruck 6 5 2 + * 7 / 4 - entspricht z. B. dem gewöhnlichen (Infix-) Ausdruck ((6*(5+2))/7)-4.

Postfix-Ausdrücke sind eine elegante Notation für arithmetische Ausdrücke. Sie kommen ganz ohne Klammern aus!

 Dank

Übergib dem Taschenrechner einen Postfix-Ausdruck (z. B. 6 5 2 + * 7 / 4 -) und werte ihn dann aus!
Vorsicht: Als Operanden sind bei uns nur die Zahlen 0 bis 9 zugelassen.

Übrigens: ungültige Postfix-Ausdrücke werden erkannt.

 

Versuche jetzt einmal, Infix-Ausdrücke in Postfix-Ausdrücke zu wandeln.

 Dank

Seite 6/9