Infix to Prefix Conversion





















#include<stdio.h>
#include<conio.h>

struct stack
{
char optr;
struct stack *next;
};
typedef struct stack stack;

int isoperand(char c)
{
 return((c>='A'&&c<='Z')||(c>='a'&&c<='z'));
}

int canbepushed(stack* top,char optr)
{
  if(!top)
  return 1;
  if(optr=='(')
  return 1;
  if(optr==')')
  return 0;
  if(top->optr=='(')
  return 1;
  switch(optr)
  {
  case '*':
  case '/':if(top->optr=='+'||top->optr=='-')
           return 1;
  }
  return 0;
}

stack* makenode(char optr)
{
    stack *nn=(stack*)malloc(sizeof(stack));
    nn->optr=optr;
    nn->next=NULL;
    return nn;
}

stack* push(stack* top,stack* nn)
{
    nn->next=top;
    return nn;
}

stack* pop(stack *top)
{
    stack *tmp;
    if(!top)
    return top;
    tmp=top;
    top=top->next;
    free(tmp);
    return top;
}

void main()
{
int i,j;
char infix[50],postfix[50],tmp;
stack *top=NULL,*nn;
printf("\nEnter the expression [Infix Mode]:");
gets(infix);
for(i=0;infix[i]!='\0';i++);
for(i=i-1,j=0;j<i;j++,i--)
{
    tmp=infix[i];
    infix[i]=infix[j];
    infix[j]=tmp;
}
  for(i=j=0;infix[i];i++)
  {
    if(isoperand(infix[i]))
     postfix[j++]=infix[i];
    else
     {
       while(!canbepushed(top,infix[i]))
       {
         if(top->optr=='(')
         {
          top=pop(top);
          break;
         }
         postfix[j++]=top->optr;
         top=pop(top);
       }
       if(infix[i]!=')')
       {
       nn=makenode(infix[i]);
       top=push(top,nn);
       }
     }
  }
while(top)
{
    postfix[j++]=top->optr;
    top=pop(top);
}
postfix[j]='\0';

for(i=0;postfix[i]!='\0';i++);
for(i=i-1,j=0;j<i;j++,i--)
{
    tmp=postfix[i];
    postfix[i]=postfix[j];
    postfix[j]=tmp;
}

printf("\nPrefix:%s",postfix);
getch();
}

                                                                                                                                             Code By:
                                                                                                                                           Jatin Kumar


No comments: