Thursday, June 27, 2013

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/++.

No comments:

Post a Comment