Aside — Postfix

  • Postfix expression evaluation is one of the classic stack examples

Postfix Expressions

  • Humans prefer infix notation for writing mathematical expressions

    • 3 + 4 * 2 = 11

    • (7 + 2) / 3 = 3

  • However, this infix notation is just a convention

  • Other notations exist, such as postfix notation

    • Postfix notation has some advantages for computers

  • The above infix expressions can be expressed with postfix notation as follows

    • 3 4 2 * + = (3 (4 2 *) +) = 11

    • 7 2 + 3 / = ((7 2 +) 3 /) = 3

Pseudocode for Evaluating Postfix Expressions

1For each symbol in expression
2    If symbol is an operand
3        PUSH symbol onto stack
4
5    If symbol is an operator
6        POP twice from the stack
7        Apply operator to the two popped operands
8        PUSH result onto stack

Evaluate

  • With the pseudocode, evaluate 7 4 -3 * 1 5 + / *

../../_images/stack_postfix.png

Example evaluation of the postfix expression 7 4 -3 * 1 5 + / * using a stack. For brevity, only six of the ten states that the stack would have are shown; multiple sequential operand pushes are not shown.

  • Notice that, once again, the idea of a stack can be used to solve a problem despite not knowing its implementation