Wednesday, April 17, 2013

Convert an infix expression to postfix expression

This program shows how to convert an infix expression to postfix expression.An infix expression is accepted as input.The expression is pushed into the stack character by character.While pushing the expression,it is pushed as per the priority of the operants.Finally,when the expression is poped out of the stack,it gets converted into postfix expression.

#include
#include
#define max 50

void main()
{
   char exp[100],opt_stk[max],ch;
   int opt_top,i;
   clrscr();
   opt_top=-1;
   printf("\nEnter an infix exp \n");
   gets(exp);
   //Process the expression by taking one token(symbol) at a time
   for(i=0;exp[i]!='\0';i++)
   {
    if (exp[i]=='(')
    {
        push_opt(opt_stk,&opt_top,&exp[i]);
    }
    else if (exp[i]==')')
    {
        //while opt stk top operator is not an openeing
        //bracket pop an operator and print it on screen
        while(opt_stk[opt_top]!= '(')
        {
            pop_opt(opt_stk,&opt_top,&ch);
            printf("%c",ch);
        }
        pop_opt(opt_stk,&opt_top,&ch); //skip '('
    }
    else
    if (chk_opt(exp[i])==0) //current token is an operand
        printf("%c",exp[i]);
    else //current token is an operator
    {
        if(opt_top==-1)  //opt stack is empty
        {
            push_opt(opt_stk,&opt_top,&exp[i]);
        }
        else
        if (priority(exp[i]) > priority(opt_stk[opt_top]))
        {
            push_opt(opt_stk,&opt_top,&exp[i]);
        }
        else
        {
            while (priority (exp[i])<=priority(opt_stk[opt_top]))
            {
                if (opt_top == -1)
                    break;
                pop_opt(opt_stk,&opt_top,&ch);
                printf("%c",ch);
            }//while
            push_opt(opt_stk,&opt_top,&exp[i]);
        }//else
    }//else
   }//for
   while(opt_top!=-1)
   {
    pop_opt(opt_stk,&opt_top,&ch);
    printf("%c",ch);
   }//while
}//main

//check whether given character is an operator or not
//Return 1 if an operator else return 0
int chk_opt(char ch)
{
    switch(ch)
    {
        case '^':
        case '*':
        case '/':
        case '%':
        case '+':
        case '-': return(1);
        default : return(0);
    }//switch
}//chk_opt

//Return a priority of specific operator if a valid operator elese return 0
int priority (char opt)
{
    switch(opt)
    {
        case '^' : return(4);
        case '*' :
        case '/' :
        case '%' : return(3);
        case '+' :
        case '-' :return(2);
        case '(' : return(1);
        default : return (0);
    }//switch
}//priority

//Push an operator(ch) in opt_stack
int push_opt(char opt_stk[max],int *opt_top,char *ch)
{
    if(*opt_top==max-1)
    {
        return(-1);
    }
    else
    {
        (*opt_top)++;
        opt_stk[*opt_top]=*ch;
        return(1);
    }
}
//Pop an operator(ch) in opt_stack
int pop_opt(char opt_stk[max],int *opt_top,char *ch)
{
    if (*opt_top==-1)
    {
        return(-1);
    }
    else
    {
        *ch=opt_stk[*opt_top];
        (*opt_top)--;
        return(1);
    }

www.cprograms.in
www.cprograms.in

No comments:

Post a Comment