Lecture Note on Prefix Infix and Postfix Notations

Prefix, Infix and Postfix Notations

We are familiar with writing an expression like

(2 + 3) * 7

When we do so, we are actually using the infix notation. This is not the only notation that can be used. In using the infix notation, we write the operator that is to operate on the operands in between the operands. In the example above, the expression contains two sub-expressions, namely

operand operator operand
   2       +        3

and

operand operator operand
 (2+3)     *        7

Intuitively, instead of writing expressions so that an operator appears in between the operands it is to operate on, we can also write them so that the operator appears before or after the operands. These two alternative ways correspond to the prefix notation and postfix notation, respectively.

For the above example, using the prefix notation results in

operator operand operand
   +        2       3

and

operator operand operand
   *      + 2 3     7

On the other hand, using the postfix notation results in

operand operand operator
   2       3       +

and

operand operand operator
 2 3 +     7       *

Notice that I have conveniently dropped the parentheses for the expressions written in the prefix and postfix notations. This is because they are not needed, which is an advantage that the two alternative notations have over the usual infix notation. Another advantage that is enjoyed by the postfix notation is that expressions written using the notation are particularly easy to evaluate. Some computers internally use postfix notation because of this ease of expression evaluation. Before we examine how easy it is to evaluate a postfix expression, here is a more complex example of an expression written in the three notations:

( 7 + ( 3 * 5 ) ) - 4     (infix)
7  3  5  *  +  4  -       (postfix)
-  +  7  *  3  5  4       (prefix)

Using Stacks to Evaluate Postfix Expressions

The assumptions:

Operands are non-negative numbers.
Operands are separated by spaces.
All operators are binary operators.

The key characteristic:

It uses only one stack (for storing numbers --> numbers stack).
There's no need for an operators stack because each operator is used as soon as it is read.

The algorithm:

Scan input from left to right
   if (input is a number)
      push it onto the stack
   else if (input is an operator)
      obtain 2 numbers from, and pop them off, the stack
      peform the operation (NOTE: 2nd number obtained must
                                  be made the left operand)
      push the result onto the stack
   else
      do nothing (simply discard input)
The stack now contains the desired result

E.g.: Use a stack to evaluate 5 3 2 * + 4 - 5 +

(NOTE: In the following, the stack has the top to the right.)
Symbol   Stack   Remarks
------   -----   -------
5        5
3        5 3
2        5 3 2
*        5 6     3 * 2 = 6
+        11      5 + 6 = 11
4        11 4
-        7       11 - 4 = 7
5        7 5
+        12      7 + 5 = 12
                 Answer: 12

(Click here to print the above algorithm and example on one page for quick reference.)

Using Stacks to Translate from Infix to Postfix (Fully Parenthesized Case)

The assumptions:

Operands are either numbers or variables
All operators are binary operators
Infix expression is fully parenthesized

The key idea:

Move each operator to the location of the ')' corresponding to the operation and then remove all parentheses.

Some technical details:

Must read infix expression from left to right.
Must store operators until they are ready to be moved.
Must determine the corresponding ')' for each operator.

Some observations:

Operands in the equivalent postfix expression are in the same order as in the given infix expression; this means that the algorithm can simply copy the infix expression operands, omitting parentheses and inserting operators at the correct locations.
An operator is inserted into output each time a ')' is encountered.
Any time an operator is needed, it is always the last one that was seen; this means that if the operators are pushed onto a stack, the operator that is needed at any time is always at the top of the stack.

The algorithm: (uses one stack for storing operators and parentheses)

Scan infix expression from left to right
   if (input is a left parenthesis)
      push it onto the stack
   else if (input is an operand)
      write it to output
   else if (input is an operator)
      push it onto the stack
   else // input is a right parenthesis (spaces are simply discarded)
      discard input
      if (top of the stack contains an operator)
         read from the stack and write the operator read to output
         pop the operator off the stack
      else // too few operators in the infix expression
         print error message and exit
      if (top of the stack contains a left parenthesis)
         pop the stack
      else // infix expression doesn't have balanced parentheses
         print error message and exit
Check error status
   if (the stack is empty)
      all done
   else // infix expression is not fully parenthesized
      print error message and exit

E.g.: Use a stack to translate ( ( ( A + 7 ) * ( B / C ) ) - ( 2 * D ) ) to postfix

(NOTE: In the following, the stack has the top to the right.)
Symbol   Stack           Output
------   -----           ------
(        (
(        ( (
(        ( ( (
A        ( ( (           A
+        ( ( ( +         A
7        ( ( ( +         A 7
)        ( (             A 7 +
*        ( ( *           A 7 +
(        ( ( * (         A 7 +
B        ( ( * (         A 7 + B
/        ( ( * ( /       A 7 + B
C        ( ( * ( /       A 7 + B C
)        ( ( *           A 7 + B C /
)        (               A 7 + B C / *
-        ( -             A 7 + B C / *
(        ( - (           A 7 + B C / *
2        ( - (           A 7 + B C / * 2
*        ( - ( *         A 7 + B C / * 2
D        ( - ( *         A 7 + B C / * 2 D
)        ( -             A 7 + B C / * 2 D *
)                        A 7 + B C / * 2 D * -
                         (Stack is empty: all done)

(Click here to print the above algorithm and example on one page for quick reference.)

Using Stacks to Translate from Infix to Postfix (General Case)

The assumptions:

Operands are either numbers or variables.
All operators are binary operators.

No longer assume:

Infix expression is fully parenthesized

Key to overcoming "missing" parentheses:

Use precedence rules to help determine the order of operations that are "missing" parentheses.

C++ rules for evaluating arithmetic expressions that are not fully parenthesized:

Parenthesized operations are evaluated first.
Non-parenthesized operations are evaluated next, in the order of operator precedence from high to low.
Arithmetic operations of equal precedence are evaluated from left to right, unless overridden by parentheses.

The algorithm: (uses one stack for storing operators and parentheses)

Scan infix expression from left to right
  if (input is a left parenthesis)
    push it onto the stack
  else if (input is an operand)
    write it to output
  else if (input is an operator)
    do until (stack is empty OR
              top of stack is a left parenthesis OR
              top of stack is an operator w/ lower precedence than input)
      read the stack and write the result to output
      pop the stack
    push input onto the stack
  else // input is a right parenthesis (spaces are simply discarded)
    discard input
    do until (stack is empty OR
              top of stack is a left parenthesis)
      read the stack and write the result to output
      pop the stack
    if (stack is empty) // unbalanced parentheses
      print error message and exit
    else // top of stack is a left parenthesis
      pop the stack
Finish up and check error status
  do until (stack is empty)
    if (top of stack is a left parenthesis) // unbalanced parentheses
      print error message and exit
    else
      read the stack and write the result to output
    pop the stack

E.g.: Use a stack to translate 3 * X + ( Y - 12 ) - Z to postfix

(NOTE: In the following, the stack has the top to the right.)
Symbol   Stack           Output
------   -----           ------
3                        3
*        *               3
X        *               3 X
+        +               3 X *
(        + (             3 X *
Y        + (             3 X * Y
-        + ( -           3 X * Y
12       + ( -           3 X * Y 12
)        +               3 X * Y 12 -
-        -               3 X * Y 12 - +
Z        -               3 X * Y 12 - + Z
                         3 X * Y 12 - + Z -
                         (Stack is empty: all done)

(Click here to print the above algorithm and example on one page for quick reference.)

Textbook Reading

Section 7.4.