Algorithm for Infix to Postfix Conversion : Using Stack

Algorithm for Conversion Of An Expression From Infix to Postfix

```Consider -
Stack S
Char  ch
Char  element
while(Tokens are Available)
{
if(ch is Operand)
{
Print ch ;
}
else
{
while(Priority(ch) <= Priority(Top Most Stack))
{
element = Pop(S);
Print(ele);
}
Push(S,ch);
}
}
while(!Empty(S))
{
element = Pop(S);
Print(ele);
}
```

Explanation :

1. In this Algorithm we are reading token from Left to Right and Postfix expression is generated. [See What is Postfix ? ]
2. So Entered Token may be -
• Alphabet from A-Z or a-Z
• Numerical Digit from 0-9
• Operator
• Opening And Closing Braces ( , )
3. If Entered Character is Alphabet then Following Action Should be taken-
• Print Alphabet as Output
4. If Entered Character is Digit then Following Action Should be taken-
• Print Digit as Output
5. If Entered Character is Opening Bracket then Following Action Should be taken-
• Push ‘(‘ Onto Stack
• If any Operator Appears before ‘)’ then Push it onto Stack.
• If Corresponding ‘)’ bracket appears then Start Removing Elements [Pop] from Stack till ‘(‘ is removed.
6. If Entered Character is Operator then Following Action Should be taken-
• Check Whether There is any Operator Already present in Stack or not.
• If Stack is Empty then Push Operator Onto Stack.
• If Present then Check Whether Priority of Incoming Operator is greater than Priority of Topmost Stack Operator.
• If Priority of Incoming Operator is Greater then Push Incoming Operator Onto Stack.
• Else Pop Operator From Stack again goto Step 6.