Write an algorithm to convert infix expression to postfix expression. Give a suitable example.

An algorithm to convert infix expression to postfix expression is:

INITIALLY:

‘stackop’ is an empty stack.

‘postfix’, is an empty string.

‘prcd(op1, op2)’, return TRUE if op1 has precedence over op2, FALSE otherwise.

1.   Start

2.   Input an infix expression in a string ‘infix’.

3.   Process:

while(not end of ‘infix’ string)

{

 ch= a character from ‘infix’ string

if(ch is an operand)

  add ‘ch’ to the end of ‘postfix’ string.

else

  {

    while(!empty (stackop) AND prcd (stacktop(stackop),ch) )

    {

    topch= pop(stackop);

    add ‘topch’ to the end of ‘postfix’ string.

    }

 push(stackop,ch);

}

}

4.   while( !empty(stackop))

{

  topch= pop(stackop);

  add ‘topch’ at the end of ‘postfix’ string.

}

5.   ‘postfix’ is the postfix expression of the input ‘infix’ string.

6.   END

TRACING THE ALGORITHM:

Infix string: A+B*C+D/E

Ch	postfix	stackop
A	A
+	A	+
B	AB	+
*	AB	+ ,*
C	ABC	+ ,*
+	ABC*	+, +
D	ABC*D	+, +
/	ABC*D	+, +, /
E	ABC*DE	+, +, /
	ABC*DE/	+, +
	ABC*DE/+	+
	ABC*DE/++

∴The postfix expression of A+B*C+D/E is ABC*DE/++.