Tuesday, 16 June 2015

To Convert From Infix to Prefix Expression Using stack

/* Only Applicable for correct input string */
#include<stdio.h>
#include<ctype.h>
#include<string.h>
void push(char *,int *,char []);
char pop(int *,char []);
void display(int *,char []);
int precedence(char);
void in_to_pre(char[],char []);
main()
{
   char infix[50],prefix[50];
   printf("\n..ENTER THE INPUT STRING..")'
   scanf("%s",infix);
   printf("\n..THE PREFIX FORMAT IS GENERATED AND YOU CAN SEE THE SEQUENCE OF STACK..\n");
   in_to_pre(infix,prefix);
}
void push(char *symbol,int *top,char s[50])
{
   s[++(*top)]=*symbol;
}
char pop(int *top,char s[50])
{
   return s[(*top)--];
}
void display(int *top,char s[50])
{
   int i;
   for(i=*top;i>=0;i--)
   {
       printf("%c",s[i]);
   }
}
int precedence(char symbol)
{
   switch(symbol)
   {
       case '+':
                return 1;
       case '-':
                return 1;
       case '*':
                return 2;
       case '/':
                return 2;
       case '^':
                return 3;
       case ')':
                return -1;                              
   }
}

void in_to_pre(char infix[50],char prefix[50])
{
   int i;
   char symbol,x;
   char s[50];
   int top=-1;
   int j=-1;
   strrev(infix);
   for(i=0;infix[i]!='\0';i++)
   {
   symbol=infix[i];
          if(isalpha(symbol))
          {
             prefix[++j]=symbol;
          }
          else
          {
              if(top==-1)
                 {
                push(&symbol,&top,s);
              }
               else
                   {
                     if(symbol=='(')
                         {      
                         x=pop(&top,s);
                             while(x!=')')
                          {
                             prefix[++j]=x;
                                   x=pop(&top,s);
                             }
                                    }
                                    else
                                   {
                                       if(symbol==')')
                                       {
                                           push(&symbol,&top,s);
                                       }
                                       else
                                       {
                                  while(precedence(symbol<=precedence(s[top]))
                                                   {
                                                       prefix[++j]=pop(&top,s);
                                                   }                               
                                                   push(&symbol,&top,s);
                                       }
                                         
                                   }
                          }
          }
          printf("\n");
          display(&top,s);
   }
   while(top!=-1)
   {
       prefix[++j]=pop(&top,s);
   }
   prefix[++j]='\0';
   strrev(prefix);
   printf("\n%s",prefix);
}



No comments:

Post a Comment