Infix Postfix Prefix Expressions

Types of Expression( Infix, Prefix, Postfix)

            There are three types of expressions namely

1. infix
2. prefix
3. postfix

General form of infix expression is     “operand1   operator     operand2”

General form of prefix expression is   “operator    operand1   operand2”

General form of postfix expression is “operand1   operand2   operator”

Prefix expression is called as polish notation.  Postfix expression is called reverse polish notation or suffix.

      Evaluation of expression generally makes use of stacks.  Computer does not evaluate infix expression directly; this is because there is a repeated scanning problem.  If the infix expression is have 10 operations, then expression is called for 10 times.  Thus evaluation of infix expression takes long time.  In fact, most the time is spent on scanning.  To overcome this infix expression is converted into intermediate form.  This conversion is done compiler.  The intermediate form may be either prefix or postfix.  In the second stage, computer evaluates the intermediate form.  Note that evaluation of prefix or postfix requires only one scan and therefore it takes negligible time to evaluate the postfix.

Hierarchy of Operators

Operators	Priority	Assocaivity
(   )	Highest	Left to right
Unary, not, **	2nd	Right to left
@, /, Div, Mod, And	3rd	Left to right
+, -, OR	4th	Left to right
>,>=,<,<=,==, !=	5th	Left to right
=(assignment)	6th	Left to right

Consider an expression a+b*c –d/e.  This expression is converted into postfix as follows: Above expression contains 4 operators, so scanning takes 4 times. 

   = a+(bc*)-d/e

   = a+(bc*)-(de/)

   = (abc*+)-(de/)

   = (abc*+de/-)    à  this is postfix equivalent of given infix expression.

Let us convert above example to prefix

   = a+(*bc)-d/e

   = a+(*bc)-(/de)

   = (+a*bc)-(/de)

   = (-+a*bc/de)

Convert the following expression into prefix and postfix.

1. A+B+C

Prefix

      (+AB)+C 

      ++ABC

     Postfix

      (AB+)+C 

      AB+C+

2. A*B/C

Prefix

      (*AB)/C 

      /*ABC

     Postfix

      (AB*)/C 

      AB*C/

3. A**B**C

Prefix 

 A**(**BC) 

  **A**BC

Postfix

 A**(BC**) 

 ABC****

     

4. –A + B – C + D

Prefix   Where X=-A

  (+XB) – C + D 

  (-+XBC)+D  

 +-+XBCD 

 +-+-ABCD

Postfix

  (XB+) – C + D  

 (XB+C-)+D  

 XB+C-D+ 

 -AB+C-D+

5. A**-B+C

Prefix Where X=-B

 (**AX)+C 

 +**AXC 

 +**A-BC

Postfix

 (AX**)+C 

 AX**C+ 

 A-B**C+

    

6. (A+B)*D+E/(F+A*D)+C

Prefix

       (AB+)*D+E/(F+A*D)+C 

       (+AB)*D+E/(F+*AD)+C  

       (+AB)*D+E/(+F*AD)+C

       (*+ABD)+E/(+F*AD)+C

       (*+ABD)+(/E+F*AD)+C

       (+*+ABD/E+F*AD)+C

       ++*+ABD/E+F*ADC

     Postfix

      (AB+)*D+E/(F+A*D)+C

      (AB+)*D+E/(F+AD*)+C

      (AB+)*D+E/(FAD*+)+C

      (AB+D*)+E/(FAD*+)+C

      (AB+D*)+(EFAD*+/)+C

      (AB+D*EFAD*+/+)+C

      AB+D*EFAD*+/+C+

7. A and B or C or not(E>F)

Prefix 

A and B or C or not (>EF)    where X= not(>EF)

A and B or C or X

(and AB) or C or X

(or and ABC) or X

or or and ABCX

or or and ABC not >EF

Postfix

 (A and B ) or C or not(EF>)     where X=EF>

 (AB and ) or C or X

 (AB and C or) or X

 (AB and C or X or)

 AB and C or not EF> or

      

      Note:  Here we define two priorities for the operators namely ICP ( In Coming Priority) and ISP (In Stack Priority).  We assume that the infix expression ends with “#”.  This indicates the end of expression reached.  The ICP and ISP of operators is as follows:

         

Operators	ISP	ICP
+, -	1	1
*, /	2	2
**	3	4
(	0	4
)	-	-
!	-1	-

      Here we can express the expression from left to right.

1. if operand is encountered, print it.

2. if “)” (Closing Bracket)  is encountered, delete all elements above “(“ (Opening Bracket)  and print them from the stack.  Delete even opening bracket also from the stack but don’t print it.

3. if operator or opening bracket is encountered compare ICP with ISP of the TOP most element in the stack.  Otherwise delete the topmost element from the stack and print it.  Now compare again ICP and ISP.  Repeat this procedure until ICP>ISP.  if ICP>ISP push the operator or opening bracket into the stack.

4. if # is encountered, delete all elements from the stack and print them till ! (Exclamation  Mark) is encountered.

Here we assume the infix expression is stored in e.  Further we use a function called NextToken.  This function gets successive token’s from the infix expression e.

Convert infix expression (A+B)*D+E/(F+A*D)+C into postfix using above points

Token	ICP	Stack Contents	ISP	Output	Remarks
		!	-1		Puts ! in stack
(	4	!(	0		ICP>ISP i.e., 4>-1 push ‘(‘ in stack
A				A	Operand print it
+	1	!(+
B				AB
)	-	!	-1	AB+	Closing bracket encountered, deletes all elements above opening bracket and print them.  Also delete ‘(‘ opening bracket
*	2	!*	2
D		!*	2	AB+D
+	1	!+	1	AB+D*	if ICP(+) > ISP(*) then push operator else POP and print
E				AB+D*E
/	2	!+/	2	AB+D*E
(	4	!+/(	0	AB+D*E
F				AB+D*EF
+	1	!+/(+	1	AB+D*EF
A				AB+D*EFA
*	2	!+/(+*	2	AB+D*EFA
D				AB+D*EFAD
)	-	!+/	2	AB+D*EFAD*+
+	1	!+	1	AB+D*EFAD*+/+
C				AB+D*EFAD*+/+C
#				AB+D*EFAD*+/+C+

Convert infix expression A*(B+C)*D into postfix using above points

Token	ICP	Stack Contents	ISP	Output	Remarks
		!	-1		Puts ! in stack
A		!	-1	A
*	2	!*	2	A
(	4	!*(	0	A
B				AB
+	1	!*(+	1	AB
C				ABC
)	-	!*	2	ABC+
*	2	!*	2	ABC+*
D				ABC+*D
#		!		ABC+*D*

1. Convert infix expression A*B/C into postfix using above points

Token	ICP	Stack Contents	ISP	Output	Remarks
		!	-1		Puts ! in stack
A		!	-1	A
*	2	!*	2	A
B		!*	2	AB
/	2	!/	2	AB*
C		!/	2	AB*C
#		!	-1	AB*C/

Function or Procedure to infix expression to Postfix equivalent

Procedure PostfixConvert(expression e)

   X,Y : Tokens;

Begin

  Top=1;

   S[Top]=’!’;

  X=NextToken(e);

  While X <> ‘#’

  Begin

         If X is operand then

            Write(x);

         Else if X =’)‘ then

           Begin

               While s[Top] <> ‘(‘

                 Begin

                     Y=pop();    { delete all elements above opening bracket }

                      write Y;

                  end

                 Y=pop();   { delete opening bracket }

           end

          Else if ICP(x) > ISP(s[Top]) then

             Push(x);

           Else

             begin

               Repeat

                  Y=pop();

                  Write(Y);

               Until ICP(x) > ISP(s[Top])

              Push(x);

            end

      x=NextToken(e);

  end

          while  s[Top]<>’!’

           begin

                Y=pop();

                 Write(Y);

           End

           Write(‘#’);

   End