#include<stdio.h>
#include<alloc.h>
#define NULL 0
int *f,u;
int *d1,d2,d3;
struct new
{
int info;
struct new *next;
};
typedef struct new *ptr;
struct node
{
int info;
int t;
int one;
struct new *next;
};
typedef struct node *nptr;
nptr prime;
nptr org;
int c2;
int c3;
ptr getnode(void)
{
ptr w;
w=(ptr)malloc(sizeof(struct new));
return(w);
}
/*FUNCTION TO FIND THE NUMBER OF ONE'S AND TOTAL NUMBER OF DIGITS IN
IT'S BINARY FORM*/
int q=0,nc=0;
int binary(int n,int i)
{
int x;
if(n==0)
{
return;
}
if(n==1)
{
q++;
nc++;
return;
}
x=n%2;
binary(n/2,i);
if(x==1)
{
q++;
nc++;
}
else
nc++;
}
/*RECURSIVE FUNCTION TO FIND GREATEST NUMBER*/
int great(int a[],int x,int n)
{
int m;
if(n==x)
return(n);
m=great(a,x+1,n);
if(a[x]>a[m])
return(x);
else
return(m);
}
/*FUNCTION TO CONVERT NUMBERS INTO BINARY FORM USING LINKED LIST*/
ptr create(int nc,int n,int d)
{
int k,x,i;
ptr p,q,t,u;
p=NULL;
q=NULL;
k=nc-n;
if(k>=1)
{
for(i=0;i<k;i++)
{
if(i==0)
{
q=getnode();
t=q;
}
else
{
q->next=getnode();
q=q->next;
}
q->info=0;
}
q->next=NULL;
}
if(d==0)
return(t);
x=d%2;
p=getnode();
u=p;
p->info=x;
p->next=NULL;
d=d/2;
while(d>0)
{
p=getnode();
x=d%2;
d=d/2;
p->next=u;
p->info=x;
u=p;
}
if(k==0)
return(u);
q->next=p;
return(t);
}
/*QUICK SORT*/
int partition(int x[],int lb,int ub,int *pj)
{
int up,down,temp,a;
a=x[lb];
down=lb;
up=ub;
while(down<up)
{
while((down<ub)&&(a>=x[down]))
down++;
while(x[up]>a)
up--;
if(down<up)
{
temp=x[down];
x[down]=x[up];
x[up]=temp;
}
}
x[lb]=x[up];
x[up]=a;
*pj=up;
}
void quick(int x[],int lb,int ub)
{
int j;
if(lb>=ub)
return;
partition(x,lb,ub,&j);
quick(x,lb,j-1);
quick(x,j+1,ub);
}
void copy(int m[],int n)
{
int i,j,v,flag=1;
f=(int *)malloc(n*sizeof(int));
u=0;
for(i=0;i<n;i++)
{
v=m[i];
for(j=0;j<u;j++)
{
if(f[j]!=v)
{
flag=1;
}
else
{
flag=0;
break;
}
}
if(flag==0)
continue;
else
f[u++]=v;
}
quick(f,0,u-1);
}
/*FUNCTON TO FIND IF MINTERMS DIFFER ONLY BY ONE POSITION*/
int diff(ptr q,ptr r)
{
int k=0;
ptr u,v;
u=q;
v=r;
while(u!=NULL)
{
if(u->info!=v->info)
k++;
u=u->next;
v=v->next;
}
return(k);
}
int get(nptr s)
{
int d,i;
d=s->one;
for(i=0;i<u;i++)
{
if(f[i]==d)
return(i);
}
}
/*FUNCTION TO COUNT THE NUMBER OF MINTERMS WHICH CAN BE COMPARED DURING EACH LOOP*/
int count1(nptr p,int n)
{
int i,j,g,h,m=0,k;
nptr q,r;
for(i=0;i<n-1;i++)
{
q=p+i;
g=get(q);
for(j=i+1;j<n;j++)
{
r=p+j;
h=get(r);
k=diff(q->next,r->next);
if((g==h+1||h==g+1)&&k==1)
{
q->t=1;
r->t=1;
m++;
}
}
}
return(m);
}
/*FUNCTION TO RETURN THE POSITION BY WHICH TWO MINTERMS DIFFER*/
static int bn;
int set(int k,int i,int c)
{
if(k==1)
bn++;
if(bn==1)
return(i);
else
return(c);
}
int find(nptr d,nptr s1)
{
int i=0,m,n,k=0,c=0;
ptr g,h;
bn=0;
m=get(d);
n=get(s1);
if(m==n+1||n==m+1)
{
g=d->next;
h=s1->next;
while(g!=NULL)
{
i++;
if(g->info!=h->info)
k++;
if(k>1)
return 0;
if(k==1)
c=set(k,i,c);
g=g->next;
h=h->next;
}
return(c);
}
else
return 0;
}
/*FUNCTION TO COUNT THE NUMBER OF MINTERMS WHICH ARE NOT COMPARED DURING EACH LOOP*/
int count2(nptr p,int n)
{
int m=0,i;
nptr q;
for(i=0;i<n;i++)
{
q=p+i;
if(q->t==0)
m++;
}
return(m);
}
/*FUNCTION TO FIND PRIME IMPLECENTS*/
void implecents(nptr p,int n)
{
int ac=0,fg=0,my=0,cv,i,j,k,m1,a,count,w,x=0,o=1,t;
int *m;
nptr r,s,q,h1=NULL,h,c,pr;
ptr z1,z;
c2=0;
w=count1(p,n);
while(w!=0)
{
ac=count2(p,n);
if(ac!=0)
{
c2=c2+ac;
if(prime==NULL)
prime=(nptr)calloc(ac,sizeof(struct node));
else
prime=(nptr)realloc(prime,c2*sizeof(struct node));
for(i=0;i<n;i++)
{
q=p+i;
if(q->t==0)
{
(prime+fg)->next=q->next;
fg++;
}
}
}
my=0;
h1=(nptr)calloc(w,sizeof(struct node));
for(i=0;i<n-1;i++)
{
r=p+i;
for(j=i+1;j<n;j++)
{
s=p+j;
k=find(r,s);
if(k!=0)
{
h=h1+my;
my++;
z=r->next;
count=0;
if(r->one<s->one)
cv=r->one;
else
cv=s->one;
for(m1=0;m1<u;m1++)
{
if(f[m1]==cv)
h->one=m1+1;
}
a=1;
while(z!=NULL)
{
if(count==0)
{
h->next=getnode();
z1=h->next;
}
else
{
z1->next=getnode();
z1=z1->next;
}
if(a==k)
z1->info=-1;
else
z1->info=z->info;
a++;
z=z->next;
count++;
}
z1->next=NULL;
}
}
if(my<w)
continue;
else
break;
}
m=(int *)malloc(w*sizeof(int));
for(i=0;i<w;i++)
{
c=h1+i;
m[i]=c->one;
}
copy(m,w);
n=w;
w=count1(h1,w);
if(org==NULL)
org=p;
else
free(p);
p=h1;
h1=NULL;
}
ac=count2(p,n);
if(ac!=0)
{
c2=c2+ac;
if(prime==NULL)
prime=(nptr)calloc(ac,sizeof(struct node));
else
prime=(nptr)realloc(prime,c2*sizeof(struct node));
for(i=0;i<n;i++)
{
q=p+i;
if(q->t==0)
{
(prime+fg)->next=q->next;
fg++;
}
}
}
i=0;
q=prime+i;
while(i<c2)
{
if(x==0)
{
pr=(nptr)calloc(o,sizeof(struct node));
pr->next=q->next;
x++;
o++;
}
else
{
for(j=0;j<x;j++)
{
t=diff(q->next,(pr+j)->next);
if(t==0)
break;
}
if(t!=0)
{
pr=(nptr)realloc(pr,o*sizeof(struct node));
(pr+x)->next=q->next;
x++;
o++;
}
}
i++;
q=prime+i;
}
q=prime;
prime=pr;
c2=x;
free(q);
for(i=0;i<c2;i++)
(prime+i)->info=i;
}
int check(ptr r,ptr s)
{
int c=1,i,j;
ptr u,v;
u=r;
v=s;
while(u!=NULL)
{
if(u->info!=-1)
{
if(u->info!=v->info)
{
c=0;
return(c);
}
}
u=u->next;
v=v->next;
}
return(c);
}
int search(ptr v,int x,int a[],int m)
{
int i,j,c=0,h=-1,k=-2;
ptr u,w;
for(i=0;i<c2;i++)
{
u=v+i;
u=u->next;
while(u!=NULL)
{
for(j=0;j<m;j++)
{
if(a[j]==u->info)
h=(v+i)->info;
}
if(u->info==x)
{
c++;
k=(v+i)->info;
}
u=u->next;
if(h==k)
return 0;
}
}
if((c==1)&&(h!=k))
return 1;
else
return 0;
}
int ser(ptr p,int m,int x)
{
int i,j,c,k;
ptr q;
for(i=0;i<m;i++)
{
q=(p+i)->next;
while(q!=NULL)
{
if(x==q->info)
return 1;
q=q->next;
}
}
return 0;
}
int look(ptr u,int c)
{
u=u->next;
while(u!=NULL)
{
if(u->info==c)
return 1;
u=u->next;
}
return 0;
}
/*FUNCTION TO FIND ESSENTIAL PRIME IMPLECENTS*/
ptr essential(nptr p,int n)
{
int i,j,k,l,*ar1,*ar2,x=1,c,y=1,ay=0,ax=0,ij;
int op,z1=1,az1=0,at=1,d=0,big=0,v1,k1;
ptr v,u,w,z,b,t1;
nptr r,s,pt;
ar1=NULL;
w=NULL;
pt=NULL;
c3=0;
v=(ptr)calloc(c2,sizeof(struct new));
ar1=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
ar1[i]=(p+i)->info;
for(i=0;i<c2;i++)
(v+i)->info=i;
for(i=0;i<c2;i++)
{
u=v+i;
r=prime+i;
for(j=0;j<n;j++)
{
s=p+j;
l=check(r->next,s->next);
if(l==1)
{
u->next=getnode();
u=u->next;
u->info=s->info;
u->next=NULL;
}
}
}
ar2=(int *)malloc(x*sizeof(int));
for(i=0;i<n;i++)
{
c=search(v,ar1[i],ar2,ax);
for(j=0;j<d3;j++)
{
if(d1[j]==ar1[i])
{
c=0;
break;
}
}
if(c==1)
{
if(x>1)
{
ar2=(int *)realloc(ar2,x*sizeof(int));
}
ar2[ax]=ar1[i];
ax++;
x++;
}
}
for(i=0;i<ax;i++)
{
op=1;
c=ar2[i];
for(j=0;j<n&&op==1;j++)
{
z=v+j;
z=z->next;
while(z!=NULL&&op==1)
{
if(z->info==c)
{
if(w==NULL)
w=(ptr)calloc(y,sizeof(struct new));
else
w=(ptr)realloc(w,y*sizeof(struct new));
y++;
(w+ay)->info=(v+j)->info;
(w+ay)->next=(v+j)->next;
ay++;
op=0;
}
z=z->next;
}
}
}
free(ar2);
do
{
az1=0;
z1=1;
ar2=NULL;
for(i=0;i<n;i++)
{
c=ar1[i];
k=ser(w,ay,c);
for(j=0;j<d3;j++)
{
if(d1[j]==c)
{
k=1;
break;
}
}
if(k==0)
{
if(ar2==NULL)
ar2=(int *)malloc(z1*sizeof(int));
else
ar2=(int *)realloc(ar2,z1*sizeof(int));
z1++;
ar2[az1]=c;
az1++;
}
}
for(i=0;i<az1;i++)
{
op=1;
c=ar2[i];
for(j=0;j<c2&&op==1;j++)
{
u=v+j;
k1=look(u,c);
for(ij=0;(ij<d)&&(k1==1);ij++)
{
if((pt+ij)->info==u->info)
k1=0;
}
if(k1==1)
{
if(pt==NULL)
pt=(nptr)calloc(at,sizeof(struct node));
else
pt=(nptr)realloc(pt,at*sizeof(struct node));
at++;
(pt+d)->info=u->info;
(pt+d)->next=u->next;
d++;
}
}
}
for(i=0;i<d&&az1>0;i++)
(pt+i)->one=0;
for(i=0;i<az1;i++)
{
c=ar2[i];
for(j=0;j<d;j++)
{
t1=(pt+j)->next;
while(t1!=NULL)
{
if(t1->info==c)
((pt+j)->one)++;
t1=t1->next;
}
}
}
big=-1;
for(i=0;i<d&&az1!=0;i++)
{
if((pt+i)->one>big)
{
big=(pt+i)->one;
v1=(pt+i)->info;
}
}
if(az1!=0)
{
w=(ptr)realloc(w,y*sizeof(struct new));
y++;
(w+ay)->info=v1;
(w+ay)->next=(v+v1)->next;
ay++;
}
}while(az1!=0);
c3=ay;
return(w);
}
void main()
{
int n,g,i,j,k,*a,*l,*m,cd,nc1,d4=0,opt=0,inf,ing,ct,ch2,nc3;
nptr p,s1,p5,s3;
ptr r,v,b2,p9;
char *min;
clrscr();
d2=0;
d3=0;
p9=NULL;
s3=NULL;
prime=NULL;
printf("\n\nEnter the number of Minterms(EXCLUDING DON'T CARES).\n");
scanf("%d",&n);
/*if(n<=0)
{
printf("Error.\n\a");
getch();
exit();
}*/
printf("\n\nEnter the number of Don't Cares.\n");
scanf("%d",&d3);
n=n+d3;
p=(nptr)calloc(n,sizeof(struct node));
s3=p;
l=(int *)malloc(n*sizeof(int));
m=(int *)malloc(n*sizeof(int));
a=(int *)malloc(n*sizeof(int));
d1=(int *)malloc(d3*sizeof(int));
for(i=0;i<n;i++)
{
l[i]=0;
m[i]=0;
a[i]=0;
}
if(d3>0)
printf("\nEnter the Don't cares.\n");
else
{
printf("\nEnter the Minterms.\n");
d4=1;
}
for(i=0;i<n;i++)
{
scanf("%d",&(p->info));
if(p->info<0)
{
printf("Please don't enter negative term.\n");
printf("Minterms can't be negative.\n");
printf("Try again.\n\a");
getch();
exit();
}
if(i<d3)
{
d1[d2]=p->info;
d2++;
}
if(i==d3-1&&d4==0)
printf("Enter the other Minterms.\n");
a[i]=p->info;
if(i<n-1)
p=p+1;
}
clrscr();
for(i=0;i<n-1;i++)
p=p-1;
for(i=0;i<n-1;i++)
{
inf=(p+i)->info;
ct=0;
for(j=i+1;j<n;j++)
{
ing=(p+j)->info;
if(inf==ing)
{
ct++;
if(ct>0)
{
printf("Please don't enter the minterm more than once.\n");
printf("Try Again.\n\a");
getch();
exit();
}
}
}
}
g=great(a,0,n-1);
for(i=0;i<n;i++)
{
k=a[i];
binary(k,i);
l[i]=nc;
m[i]=q;
nc=0;
q=0;
if(i==g)
j=l[i];
}
nc1=j;
printf("\n\nThe simplified expression will be displayed using %d variables.\n",nc1);
for(i=0;i<n;i++)
{
r=create(j,l[i],a[i]);
p->t=0;
p->one=m[i];
p->next=r;
if(i<n-1)
p=p+1;
}
for(i=0;i<n-1;i++)
p=p-1;
/*CHARACTER ARRAY TO STORE THE VARIABLES*/
min=(char *)malloc(nc1*sizeof(char));
printf("\n\nEnter the variables of your choice(Eg:w,x..a,b..one per line).\n\n");
for(i=0;i<nc1;i++)
{
scanf("%s",&min[i]);
}
copy(m,n);
implecents(p,n);
/*THE MINTRMS CONSTITUTING PRIME IMPLECENTS ARE
DETERMINED AND ESSENTIAL PRIME IMPLECENTS ARE
FOUND USING THE FUNCTIONS BELOW*/
v=essential(s3,n);
clrscr();
/*DISPLAYING THE EXPRESSION*/
printf("\n\nThe simplified expression is.\n\n\n");
for(i=0;i<c3;i++)
{
cd=(v+i)->info;
for(j=0;j<c2;j++)
{
if((prime+j)->info==cd)
s1=prime+j;
}
if(s1->info==cd)
p9=s1->next;
k=0;
for(b2=p9;b2!=NULL;b2=b2->next)
{
if(b2->info==1)
{
opt=1;
printf("%c",min[k]);
k++;
}
else
if(b2->info==0)
{
opt=1;
printf("%c",min[k]);
printf("'");
k++;
}
else
{
if(b2->info==-1)
k++;
}
}
if(i<c3-1)
printf("+");
}
if(opt==0)
{
printf("1\n");
printf("In this case output is always equal to 1 regardless of input expression.\n");
}
getch();
}