Page 157 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes A = 15 2 +
=17
B = 6 4 *
=24

A = 17 24 +
=41
We can write this sequence of operations as follows:
5 3 * 2 + 6 4 * +

This notation is known as postfix notation and is evaluated as described above. We shall shortly
show how this form can be generated using a stack.
Basically there are 3 types of notations for expressions. The standard form is known as the infix
form. The other two are postfix and prefix forms.
Infix: operator is between operands, that is, A + B

Postfix: operator follows operands., that is, A B +
Prefix: operator precedes operands, that is, + A B

Notes All infix expressions cannot be evaluated by using the left to right order of the
operators inside the expression. However, the operators in a postfix expression are
ALWAYS in the correct evaluation order.

Thus evaluation of an infix expression is done in two steps. The first step is to convert it into its
equivalent postfix expression. The second step involves evaluation of the postfix expression. We
shall see in this section, how stacks are useful in carrying out both the steps. Let us first examine
the basic process of infix to postfix conversion.

The steps for converting infix to postfix form are shown in the examples given below.

Example: Consider the Infix form as a + b * c. This is to note that precedence of * is higher
than of +.
1. a + (b * c) : convert the multiplication

2. a + ( b c * ) : convert the addition
3. a (b c * ) + : Remove parentheses

4. a b c * + : Postfix form
There is no need of parentheses in postfix forms.

Example:
1. ( A + B ) * C : Infix form
2. ( A B + ) * C : Convert the addition

150 LOVELY PROFESSIONAL UNIVERSITY