C Program which converts Infix to Prefix Expression

Algorithm:

1. Create a stack for operands, which contains ‘!’ as first element.
2. Create a stack for operators, which also contains ‘!’ as first element.
3. Create a function called ICP i.e., Incoming Priority
4. Accept/take infix expression i.e., E which ends with ‘#’.
5. Scan the infix expression E from left to right.
6. Now take first token from infix expression E i.e., a =nextToken(E)
7. while a<>’#’

        begin

           if a is operand then push it into operand stack.

           else if a is ‘(‘ then push it into operator stack.

           elseif a is ‘)’ then

a)     pop the operator from operator stack i.e., optr

b)     pop the operand from operand stack i.e., op1

c)      pop another operand from operand stack i.e, op2

d)     Here op1 is right operand of operator and op2 is left operand

      of the operator i.e., op2 op1 optr

e)   Push optr+op2+op1into operand stack.

 f)   Repeat the above a,b,c,d,e process until ‘)’ is encountered in operator stack.

                   g)   Delete ‘)’ from operator stack and don’t perform any action on

                          it.

                else if ICP(a)>ICP(instackoperator) then

                   push a into operator stack.

                else

a)  pop the operator from operator stack i.e., optr

b)     pop the operand from operand stack i.e., op1

c)      pop another operand from operand stack i.e, op2

d)     Here op1 is right operand of operator and op2 is left operand

      of the operator i.e., op2 op1 optr

e)  Push optr+op2+op1 into operand stack.

 f)  Repeat a,b,c,d,e until ICP(a)>ICP(instackoperator)

                 end

             a=nextToken(E)

             end

8. while operatorStack <>”!”

begin

a)  pop the operator from operator stack i.e., optr

b)     pop the operand from operand stack i.e., op1

c)      pop another operand from operand stack i.e, op2

d)     Here op1 is right operand of operator and op2 is left operand

      of the operator i.e., op2 op1 optr

e)   Push optr+op2+op1 into operand stack.

     end

9. pop the element from operand stack which is the postfix value and print it.

C program

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#define Max 20
char stOper[Max][Max], Opertop=-1;
char stOptr[Max][Max], Optrtop=-1;

void pushOperand(char ch[25])
{
  if (Opertop == Max-1)
   {
      printf("Operand Stack is full\n");
   }
   else
   {
     Opertop++;
     strcpy(stOper[Opertop],ch);
   }
}


char* popOperand()
{
   char ch[25];
     if (Opertop==-1)
      {
            printf("Operand Stack is empty\n");
      }
      else
      {
               strcpy(ch,stOper[Opertop]);
               Opertop--;
      }
      return ch;
}


void dispOperandstack()
{
  int k;
  printf("Operand stack Content: ");
  for (k=Opertop; k>=0; k--)
  {
    printf("%s, ", stOper[k]);
  }
  printf("\n");
}

void pushOperator(char ch[25])
{
  if (Optrtop == Max-1)
   {
      printf("Operator Stack is full\n");
   }
   else
   {
     Optrtop++;
     strcpy(stOptr[Optrtop],ch);
   }
}

char* popOperator()
{
   char ch[25];
     if (Optrtop==-1)
      {
            printf("Operator Stack is empty\n");
      }
      else
      {
               strcpy(ch,stOptr[Optrtop]);
               Optrtop--;
      }
      return ch;
}

void dispOperatorstack()
{
  int k;
  printf("Operator stack Content: ");
  for (k=Optrtop; k>=0; k--)
  {
    printf("%s, ", stOptr[k]);
  }
  printf("\n");
}

int ICP(char ch)
{
  int pre,pre1;
  pre=toascii(ch);
  if (pre==43 || pre==45) pre1= 1;      /*   + and -  */
  else if (pre==42 || pre==47) pre1= 2; /*   * and /  */
  else if (pre==33)  pre1=-1;   /* !                  */
  else if (pre==40)  pre1=0;   /* Closing parenthesis ) */
  return pre1;
}

char * Prefix(char s[25])
{
  char pre[25],preOpt[25],optr[25],op1[25],op2[25];
  int i,j;
  i=0; j=0;
  Optrtop=-1;
  Opertop=-1;
  pushOperator("!");
  pushOperand("!");

  while (s[i]!='\0')
  {
     /*if operand is countered print it */
    if ( (s[i]>=97 && s[i]<=122) || (s[i]>=65 && s[i]<=90) ||(s[i]>=48 && s[i]<=57) )
    {
      j=0;
      pre[j]=s[i];
      j++;
      pre[j]='\0';
      pushOperand(pre);
    }
    else if (s[i]=='(')
    {
      pushOperator("(");
    }
    else if (s[i]==')')
    {
       while (strcmp(stOptr[Optrtop],"(")!=0)
       {
             strcpy(optr,popOperator());
             strcpy(op2, popOperand());
             strcpy(op1, popOperand());
             strcpy(pre,optr);
             strcat(pre,op1);
             strcat(pre,op2);
             pushOperand(pre);
       }
       strcpy(optr,popOperator());   /* pop closing parenthsis but don't print it */
    }
    else if ( ICP(s[i]) > ICP(stOptr[Optrtop][0]) )
    {
       j=0;
       preOpt[j]=s[i];
       j++;
       preOpt[j]='\0';
       pushOperator(preOpt);
    }
    else
    {
       do
       {
             strcpy(optr,popOperator());
             strcpy(op2,popOperand());
             strcpy(op1,popOperand());
             strcpy(pre,optr);
             strcat(pre,op1);
             strcat(pre,op2);
             pushOperand(pre);
       }
       while (ICP(s[i])<= ICP(stOptr[Optrtop][0]) );
       j=0;
       preOpt[j]=s[i];
       j++;
       preOpt[j]='\0';
       pushOperator(preOpt);
    }
    i++;
   /* dispOperatorstack();
    dispOperandstack();
    getch();  */
  }
  while ( strcmp(stOptr[Optrtop],"!")!=0 )
  {
    strcpy(optr,popOperator());
    strcpy(op2, popOperand());
    strcpy(op1, popOperand());
    strcpy(pre,optr);
    strcat(pre,op1);
    strcat(pre,op2);
    pushOperand(pre);
  }
/*  dispOperatorstack();
  dispOperandstack();*/
  strcpy(pre,popOperand());
  return pre;
}



void main()
{
  char s[25],pre[25];
  clrscr();
  printf("enter a infix expression\n");
  scanf("%s",s);
  strcpy(pre,Prefix(s));
  printf("Prefix Expression = %s\n", pre);
  getch();
}