Page 159 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The process stops when there are no more operator left in the string. The result of evaluating the
expression is obtained just by popping off the single element.

Converting an Infix Expression to Postfix

A stack can also be used to convert an infix expression in standard form into postfix form. We
shall assume that the expression is a legal one (i.e. it is possible to evaluate it). When an operand
is read, it will be placed on output list (printed out straight away). The operators are pushed on
a stack. However, if the priority of the top operator in the stack is higher than the operator being
read, then it will be put on output list, and the new operator pushed on to the stack. The priority
is assigned as follows.
1. ( Left parenthesis in the expression
2. * /
3. + –

4. (Left parenthesis inside the stack
The left parenthesis has the highest priority when it is read from the expression, but once it is on
the stack, it assumes the lowest priority.

To start with , the stack is empty. The infix expression is read from left to right. If the character
is an OPERAND, it is not put on the stack. It is simply printed out as part of the post fix
expression.
The stack stores only the OPERATORS. The first operator is pushed on the stack. For all subsequent
operators, priority of the incoming operator will be compared with the priority of the operator
at the top of the stack.
If the priority of the incoming-operator is higher than the priority of topmost operator-on the
stack, it will be pushed on the stack.
If the priority of the incoming-operator is same or lower than the priority of the operator at the
top of the stack, then the operator at top of the stack will be popped and printed on the output
expression.
The process is repeated if the priority of the incoming-operator is still same or lower than the
next operator-in-the stack. When a left parenthesis is encountered in the expression it is
immediately pushed on the stack, as it has the highest priority. However, once it is inside the
stack, all other operators are pushed on top of it, as its inside-stack priority is lowest.
When a right parenthesis is encountered, all operators up to the left parenthesis are popped
from the stack and printed out. The left and right parentheses will be discarded. When all
characters from the input infix expression have been read, the operators remaining inside the
stack, are printed out in the order in which they are popped.

Here is an algorithm for converting an infix expression into its postfix form.

Algorithm:

while there are more characters in the input
{
Read next symbol ch in the given infix expression.
If ch is an operand put it on the output.

152 LOVELY PROFESSIONAL UNIVERSITY