Friday, August 23, 2013

Implement Stack as an ADT using Array.Use this ADT to Perform expression conversion and evaluation.


/*---------------------------------------------------------------------------------------------
Program  : Implement Stack as an ADT using Array.Use this ADT to Perform
                    expression conversion and evaluation.
                     (Infix to prefix,infix to postfix,
                     prefix to infix,prefix to postfix,
                     postfix to infix & postfix to prefix)

Created By : JABIR DAUD PATHAN
Branch     : COMPUTER ENGINEERING
-----------------------------------------------------------------------------------------------*/

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<string.h>
#define SIZE 25

/*------------<< GLOBAL DECLARATION >>------------*/
typedef struct stack
 {
   int data[SIZE];
   int top;
 }stack;

char stk[SIZE][SIZE];
int top1,ans;

/*------------<< GLOBAL DECLARATION OF FUNCTIONS >>---------------*/

int prec(char);
void stkinit(stack *);
int stkempty(stack *);
int stkfull(stack *);
int stkpop(stack *);
void stkpush(stack *,int);
void display(stack*s);
int top(stack *);
void in_to_pre(char in[],char pre[]);
void in_to_post(char in[],char post[]);
void pre_to_in(char pre[],char in[]);
void pre_to_post(char pre[],char post[]);
void post_to_in(char post[],char in[]);
void post_to_pre(char post[],char pre[]);
void convert_post(char x);
void convert_in(char x);
void convert_pre(char x);
void convert_in1(char x);
int eval_pre(char pre[]);
int eval_post(char post[]);
int eval(char x,int op1,int op2);


/*--------------<< MAIN FUNCTION >>--------------*/

void main()
{
 char in[SIZE],pre[SIZE],post[SIZE];
 char ans;
 int ch,n;
 stack s;
 do
  {
   clrscr();
   printf("\n\n\t\t-----<< MAIN MENU >>------");
   printf("\n\t\t1.Push an element");
   printf("\n\t\t2.Pop an element");
   printf("\n\t\t3.Conversion");
   printf("\n\t\t4.Evaluation");
   printf("\n\t\t5.Exit");
   printf("\n\t\t--------------------------");
   printf("\n\n\t\tEnter your choice==>");
   scanf("%d",&ch);
   switch(ch)
    {
     case 1:
                   printf("\nEnter the element to be pushed==>");
                   scanf("%d",&n);
                   stkpush(&s,n);
                   display(&s);
                   break;

     case 2:
                    if(stkempty(&s))
                    {
                            printf("\n\tThe stack is empty");
                    }
                    else
                    {
                            printf("\n\tThe poped element is %d",stkpop(&s));
                            display(&s);
                    }
                    break;
     case 3:
                   do
                   {
                    clrscr();
                    printf("\n\n\t\t-------<< CONVERSION MENU >>-------");
                    printf("\n\t\t1.Infix to Prefix and Postfix");
                    printf("\n\t\t2.Prefix to Infix and Postfix");
                    printf("\n\t\t3.Postfix to Infix and Prefix");
                    printf("\n\t\t4.Exit");
                    printf("\n\n\t\t---------------------------------------------");
                    printf("\n\n\t\tEnter your choice==>");
                    scanf("%d",&ch);
                    switch(ch)
                     {
                                    case 1:
                                                   printf("\n\nEnter Infix exp=");
                                                   scanf("%s",&in);
                                                   in_to_pre(in,pre);
                                                   printf("\n\nPrefix = %s",pre);
                                                   in_to_post(in,post);
                                                   printf("\n\nPostfix = %s",post);
                                                   break;
           
                                    case 2:
                                                  printf("\n\nEnter Prefix exp=");
                                                  scanf("%s",&pre);
                                                  pre_to_in(pre,in);
                                                  printf("\n\nInfix = %s",in);
                                                  pre_to_post(pre,post);
                                                  printf("\n\nPostfix = %s",post);
                                                  break;
                                    case 3:
                                                 printf("\n\nEnter Postfix exp=");
                                                 scanf("%s",&post);
                                                 post_to_in(post,in);
                                                 printf("\n\nInfix=%s",in);
                                                 post_to_pre(post,pre);
                                                 printf("\n\nPrefix=%s",pre);
                                                break;
                                    case 4:
                                                 exit(0);
                                                 break;
                   }
                    printf("\n\nDo you want to continue(Y/N)?==>");
                    ans=getch();
                  }while(ans=='Y'||ans=='y');
                   break;

     case 4:
                    do
                      {
                       clrscr();
                              printf("\n\n\t\t-------<< Evaluation menu >>-------");
                              printf("\n\t\t1.Evaluation of Prefix");
                              printf("\n\t\t2.Evaluation of Postfix");
                              printf("\n\t\t3.Exit");
                              printf("\n\t\t-------------------------------------------");
                              printf("\n\n\t\tEnter your choice==>");
                              scanf("%d",&ch);
                              switch(ch)
                               {
                                       case 1:
                                                             printf("\n\nEnter Prefix Exp=");
                                                             scanf("%s",pre);
                                                              ans=eval_pre(pre);
                                                             printf("\n\nValue of prefix exp=%d",ans);
                                                             break;          
                                case 2:
                                                             printf("\n\nEnter Postfix Exp=");
                                                             scanf("%s",post);
                                                             ans=eval_post(post);
                                                             printf("\n\nValue of postfix exp=%d",ans);
                                                              break;
                                       case 3:
                                                              exit(0);
                                                              break;
                       }
                               printf("\n\nDo you want to continue(Y/N)?==>");
                               ans=getch();
                             }while(ans=='Y'||ans=='y');
                              break;
           
                case 5:
                                     exit(0);
                                     break;
               default:
                                    printf("\n\tinvalid choice");
                                    break;
           
    }
     printf("\n\nDo want to go to main menu(Y/N)?==>");
     ans=getch();
  }while(ans=='Y'||ans=='y');
   getch();
 }

/*------------------<< INTIALISE STACK >>--------------------*/

void stkinit(stack *s)
 {
  s->top=-1;
 }

/*---------------<< CHECK EMPTY CONDITION OF STACK >>-----------*/

int stkempty(stack *s)
 {
  if(s->top==-1)
    return(1);
  return(0);
 }

/*--------------<< CHECK CONDITION FOR FULL STACK >>------------*/

int stkfull(stack *s)
 {
  if(s->top==SIZE-1)
    return(1);
  return(0);
 }

/*-------------<< INSERT CONTENT IN STACK >>-------------------*/

void stkpush(stack *s,int x)
 {
  s->top=s->top+1;
  s->data[s->top]=x;
 }

/*--------------<< POP ELEMENT FROM STACK >>----------------*/

int stkpop(stack *s)
 {
  int x;
  x=s->data[s->top];
  s->top=s->top-1;
  return(x);
 }
/*------------------<< DISPLAY CONTENT OF STACK >>-----------*/

void display(stack*s)
 {
  int i;
  printf("\n\nContent of stack are ==>");
  for(i=s->top;i>0;i--)
   {
    printf("\n%d",s->data[i]);
  }
 }

/*------------------<< TOP OF STACK >>--------------------*/

int top(stack *p)
 {
  return(p->data[p->top]);
 }

/*-----------------<< INFIX TO PREFIX >>----------------*/

void in_to_pre(char in[],char pre[])
 {
  int i,j;
  char temp,in1[SIZE];
  for(i=strlen(in)-1,j=0;i>=0;i--,j++)
  in1[j]=in[i];
  in1[j]='\0';
  for(i=0;in1[i]!='\0';i++)
   {
    if(in1[i]=='(')
     in1[i]=')';
    else
     if(in1[i]==')')
      in1[i]='(';
   }
   in_to_post(in1,pre);
   for(i=0,j=strlen(pre)-1;i<j;i++,j--)
    {
     temp=pre[i];
     pre[i]=pre[j];
     pre[j]=temp;
    }
  }


/*--------------<< INFIX TO POSTFIX >>-----------------*/

void in_to_post(char in[],char post[])
  {
   stack s;
   char x,token;
   int i,j=0;
   stkinit(&s);
   for(i=0;in[i]!='\0';i++)
    {
     token=in[i];
     if(isalnum(token))
      {
       post[j++]=token;
      }
     else
      {
       if(token=='(')
            {
             stkpush(&s,'(');
            }
       else
            {
             if(token==')')
              {
               while((x=stkpop(&s))!='(')
                {
                 post[j++]=x;
                }
              }
             else
              {
               while(prec(token)<=prec(top(&s))&&!stkempty(&s))
                {
                 x=stkpop(&s);
                 post[j++]=x;
                }
               stkpush(&s,token);
              }
            }
     }
   }
   while(!stkempty(&s))
    {
     x=stkpop(&s);
     post[j++]=x;
    }
    post[j]='\0';
  }


/*--------------------<< CHECK PRESENDENCE >>------------------*/

int prec(char x)
 {
  if(x=='(')  return(0);
  if(x=='+'||x=='-')  return(1);
  if(x=='*'||x=='/'||x=='%')  return(2);
  return(3);
 }


/*-----------------<< PREFIX TO INFIX >>--------------------*/

void pre_to_in(char pre[],char in[])
 {
  char x,str1[SIZE];
  int i;
  top1=-1;
  for(i=strlen(pre)-1;i>=0;i--)
   {
    x=pre[i];
    if(isalnum(x))
     {
      str1[0]=x;
      str1[1]='\0';
      top1=top1+1;
      strcpy(stk[top1],str1);
     }
    else
     {
      convert_in(x);
     }
   }
   strcpy(in,stk[top1]);
  }

/*------------------<< CONVERT TO INFIX >>-----------------*/

void convert_in(char x)
 {
  char str1[SIZE],str2[SIZE];
  str1[0]='(';
  str1[1]='\0';
  strcat(str1,stk[top1]);
  str2[0]=x;
  str2[1]='\0';
  strcat(str1,str2);
  strcat(str1,stk[top1-1]);
  str2[0]=')';
  str2[1]='\0';
  strcat(str1,str2);
  top1=top1-1;
  strcpy(stk[top1],str1);
 }

/*----------------<< PREFIX TO POSTFIX >>--------------------*/

void pre_to_post(char pre[],char post[])
 {
  char x,str1[SIZE];
  int i;
  top1=-1;
  for(i=strlen(pre)-1;i>=0;i--)
   {
    x=pre[i];
    if(isalnum(x))
     {
      str1[0]=x;
      str1[1]='\0';
      top1=top1+1;
      strcpy(stk[top1],str1);
     }
    else
     {
      convert_post(x);
     }
   }
  strcpy(post,stk[top1]);
 }

/*-----------------<< CONVERT POSTFIX >>---------------------*/

void convert_post(char x)
 {
  char str1[SIZE],str2[SIZE];
  str2[0]=x;
  str2[1]='\0';
  strcpy(str1,stk[top1]);
  strcat(str1,stk[top1-1]);
  strcat(str1,str2);
  top1=top1-1;
  strcpy(stk[top1],str1);
 }

/*------------------<< POSTFIX TO INFIX >>----------------*/

void post_to_in(char post[],char in[])
 {
  char x,str1[SIZE];
  int i;
  top1=-1;
  for(i=0;post[i]!='\0';i++)
   {
    x=post[i];
    if(isalnum(x))
     {
      str1[0]=x;
      str1[1]='\0';
      top1=top1+1;
      strcpy(stk[top1],str1);
     }
    else
     {
      convert_in1(x);
     }
   }
  strcpy(in,stk[top1]);
 }

/*--------------<< CONVERT INFIX >>----------------*/

void convert_in1(char x)
 {
  char str1[SIZE],str2[SIZE];
  str1[0]='(';
  str1[1]='\0';
  strcat(str1,stk[top1-1]);
  str2[0]=x;
  str2[1]='\0';
  strcat(str1,str2);
  strcat(str1,stk[top1]);
  str2[0]=')';
  str2[1]='\0';
  strcat(str1,str2);
  top1=top1-1;
  strcpy(stk[top1],str1);
 }

/*--------------<< POSTFIX TO PREFIX >>-------------*/

void post_to_pre(char post[],char pre[])
 {
  char x,str1[SIZE];
  int i;
  top1=-1;
  for(i=0;post[i]!='\0';i++)
   {
    x=post[i];
    if(isalnum(x))
     {
      str1[0]=x;
      str1[1]='\0';
      top1=top1+1;
      strcpy(stk[top1],str1);
     }
    else
     {
      convert_pre(x);
     }
   }
   strcpy(pre,stk[top1]);
 }

/*--------------------<< CONVERT PREFIX >>-----------------*/

void convert_pre(char x)
 {
  char str1[SIZE];
  str1[0]=x;
  str1[1]='\0';
  strcat(str1,stk[top1-1]);
  strcat(str1,stk[top1]);
  top1=top1-1;
  strcpy(stk[top1],str1);
 }

/*---------------<< EVALUATION OF PREFIX EXPRESSION >>-------------*/

int eval_pre(char pre[])
 {
  stack s;
  char x;
  int op1,op2,val,i;
  stkinit(&s);
  for(i=strlen(pre)-1;i>=0;i--)
   {
    x=pre[i];
    if(isalpha(x))
     {
      printf("\n\nEnter the value of %c=",x);
      scanf("%d",&val);
      stkpush(&s,val);
     }
    else
     {
      op1=stkpop(&s);
      op2=stkpop(&s);
      val=eval(x,op1,op2);
      stkpush(&s,val);
     }
   }
   val=stkpop(&s);
   return(val) ;
  }

/*-----------------<< EVALUATION OF POSTFIX >>-------------*/

int eval_post(char post[])
 {
  stack s;
  char x;
  int op1,op2,val,i;
  stkinit(&s);
  for(i=0;post[i]!='\0';i++)
   {
    x=post[i];
    if(isalpha(x))
     {
      printf("\n\nEnter the value of %c=",x);
      scanf("%d",&val);
      stkpush(&s,val);
     }
    else
     {
      op2=stkpop(&s);
      op1=stkpop(&s);
      val=eval(x,op1,op2);
      stkpush(&s,val);
     }
   }
   val=stkpop(&s);
   return(val) ;
  }

/*---------------<< EVALUATION >>---------------*/

int eval(char x,int op1,int op2)
 {
  if(x=='+')
   return(op1+op2);
  if(x=='-')
   return(op1-op2);
  if(x=='/')
   return(op1/op2);
  if(x=='*')
   return(op1*op2);
  }




/*-----------------<< OUTPUT SCREEN  >>-------------------*/

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>1

Enter the element to be pushed==>1

Content of stack are ==>
1

Do want to go to main menu(Y/N)?==>Y

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>1

Enter the element to be pushed==>2

Content of stack are ==>
2
1

Do want to go to main menu(Y/N)?==>Y



                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>1

Enter the element to be pushed==>3

Content of stack are ==>
3
2
1

Do want to go to main menu(Y/N)?==>Y

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>2

        The poped element is 3

Content of stack are ==>
2
1

Do want to go to main menu(Y/N)?==>Y

                                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>2

        The poped element is 2

Content of stack are ==>
1

Do want to go to main menu(Y/N)?==>Y

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>3

                -------<< CONVERSION MENU >>-------
                1.Infix to Prefix and Postfix
                2.Prefix to Infix and Postfix
                3.Postfix to Infix and Prefix
                4.Exit
                ----------------------------------------------------
                Enter your choice==>1

Enter Infix exp=A+B*C

Prefix = +A*BC

Postfix = ABC*+

Do you want to continue(Y/N)?==>Y

                -------<< CONVERSION MENU >>-------
                1.Infix to Prefix and Postfix
                2.Prefix to Infix and Postfix
                3.Postfix to Infix and Prefix
                4.Exit
                ----------------------------------------------------
                Enter your choice==>2

Enter Prefix exp=+A*BC

Infix = (A+(B*C))

Postfix = ABC*+

Do you want to continue(Y/N)?==>Y

                -------<< CONVERSION MENU >>-------
                1.Infix to Prefix and Postfix
                2.Prefix to Infix and Postfix
                3.Postfix to Infix and Prefix
                4.Exit
                ----------------------------------------------------
                Enter your choice==>3

Enter Postfix exp=ABC*+

Infix=(A+(B*C))

Prefix=+A*BC

Do you want to continue(Y/N)?==>N

Do want to go to main menu(Y/N)?==>Y

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>4


                -------<< Evaluation menu >>-------
                1.Evaluation of Prefix
                2.Evaluation of Postfix
                3.Exit
                ---------------------------------------------
                Enter your choice==>1


Enter Prefix Exp=+A*BC

Enter the value of C=2


Enter the value of B=3


Enter the value of A=1

Value of prefix exp=7

Do you want to continue(Y/N)?==>Y

                -------<< Evaluation menu >>-------
                1.Evaluation of Prefix
                2.Evaluation of Postfix
                3.Exit
                ---------------------------------------------
                Enter your choice==>2


Enter Postfix Exp=ABC+*DE/-

Enter the value of A=5


Enter the value of B=6


Enter the value of C=2


Enter the value of D=12


Enter the value of E=4

Value of postfix exp=37

Do you want to continue(Y/N)?==>N

Do want to go to main menu(Y/N)?==>Y

                -----<< MAIN MENU >>------
                1.Push an element
                2.Pop an element
                3.Conversion
                4.Evaluation
                5.Exit
                --------------------------
                Enter your choice==>5


























Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)