Algorithm for Infix to Postfix Conversion Of An Expression

July 30, 2024 1 Comment » Hits : 383





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.

Incoming search terms:

  • Stron

    Hi there, You’ve done an excellent job. I will definitely digg it and personally suggest to my friends. I’m confident they’ll be benefited from this website.