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

An algorithm to convert infix expression to prefix expression is:

INITIALLY:

‘stackop’ is an empty stack.

‘prefix’, 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 start of ‘infix’ string)

{

 ch= a last character from ‘infix’ string

if(ch is an operand)

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

else

  {

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

    {

    topch= pop(stackop);

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

    }

 push(stackop,ch);

}

}

4.   while( !empty(stackop))

{

  topch= pop(stackop);

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

}

5.   reverse the ‘prefix’ string in the string ‘finalprefix’

6.   ‘finalprefix’ is the prefix expression of the input ‘infix’ string.

7.   END

TRACING THE ALGORITHM:

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

Ch	prefix	stackop
E	E
/	E	/
D	ED	/
+	ED/	+
C	ED/C	+
*	ED/C	+, *
B	ED/CB	+, *
+	ED/CB*	+, +
A	ED/CB*A	+, +
	ED/CB*A+	+
	ED/CB*A++

Reverse of ED/CB*A++ is ++A*BC/DE.

∴The prefix expression of A+B*C+D/E is ++A*BC/DE.