Stacks können verwendet werden, um beliebige Terme in Postfix-Notation automatisch auszuwerten. Bevor Stacks entdeckt wurden, war unklar, wie Terme mit unbegrenzter Schachtelungstiefe automatisch auszuwerten sind. Tatsächlich war in frühen Programmiersprachen die Schachtelungstiefe für Klammerung begrenzt. Erst mit der Entdeckung von Stacks konnten solche Begrenzungen aufgehoben werden.
Zur Auswertung eines Terms in Postfix-Notation wird dieser rechts neben einen leeren Stack geschrieben. Als Beispiel betrachten wir die Auswertung unseres Beispielausdrucks für die Variablenbelegung x = 0.
| 3 0 2 ** 1 + math.sqrt +
Ist das am weitesten links stehende Symbol wie hier eine Konstante, wird es mit der Operation push auf den Stack gelegt und aus der Termdarstellung entfernt:
| 3 0 2 ** 1 + math.sqrt + # push(3)
3 | 0 2 ** 1 + math.sqrt + # push(0)
3 0 | 2 ** 1 + math.sqrt + # push(2)
3 0 2 | ** 1 + math.sqrt +
Ist das am weitesten links stehende Symbol wie hier ein Funktions- oder Operator-Symbol, werden zuerst Elemente entsprechend der Stelligkeit des Symbols mit pop() vom Stack entfernt und dann das Ergebnis der Anwendung der zum Symbol gehörigen (hier mathematischen) Funktion auf diese Argumente mit push() oben auf den Stack gelegt.
3 0 2 | ** 1 + math.sqrt + # pop(); pop(); push(0**2)
3 0 | 1 + math.sqrt +
Während ** in der Termdarstellung ein Funktionssymbol
(Syntax) bezeichnet, bezeichnet es im Argument von push() die
zugehörige mathematische Funktion zur Potenzierung (Semantik). Entsprechend steht nach der Abarbeitung dieses Schrittes
der Wert 0**2 = 0 oben auf dem Stack. Nun verfahren wir
gemäß dieser Regeln, bis der komplette Term abgearbeitet ist
und auf dem Stack nur noch ein einziger Wert steht.
3 0 | 1 + math.sqrt + # push(1)
3 0 1 | + math.sqrt + # pop(); pop(); push(0+1)
3 1 | math.sqrt + # pop(); push(math.sqrt(1))
3 1 | + # pop(); pop(); push(3+1)
4 |
Die Auswertung des Terms 3 + Math.sqrt(0**2 + 1) endet also mit dem Ergebnis 4.