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)
 {
     ch = Read(Token);
     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.