//title : PCNF AND PDNF OF A GIVEN WELL FORMED FROMULA
//AUTHOUR : CH GANESH (N190168)
//DEPARMENT OF COMPUTER SCIENCE (CSE)
// UNIVERSITY:RGUKT-IIIT NUZVID (ANDHRA PRADESH)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
void PDNF(int ,int ,int );
void PCNF(int ,int ,int);
static int op=0;
int c=0;
int stack[100],postfix[100];
int top=-1,top1=-1;
int sta[1000];
int top2=-1; int j=0;
int arr[1000][20];
int ar[1000][20];
int CNF=0,DNF=0;
char dup[100];char org[100];
//pushing to postfix
void push_postfix(char a)
{
postfix[++top]=a;
}
//pushing to stack
void push_stack(char a)
{
stack[++top1]=a;
}
//poping elements in stack
void pop_stack()
{
if(top1==-1)
top=-1;
else
top1--;
}
//checking precedence
int checking_pre(char a )
{
switch(a)
{
case '~':return 5;
case '&':return 4;
case '|':return 3;
case '_':return 2;
case '=':return 1;
case '(':return 0;
}
}
//checking special characters
void checking_spe(char a ){
switch(a)
{
case '(':push_stack(a);
break;
case ')':while(stack[top1]!='(')
{ push_postfix(stack[top1]);
pop_stack();
}
pop_stack();
break;
default:if(stack[top1]=='(')
{push_stack(a); op++;}
else{
while(checking_pre(a)<=checking_pre(stack[top1]))
{
push_postfix(stack[top1]);
pop_stack();
}
push_stack(a);
}
break;
}
}
//checking what type of char
void checking_char(char a)
{
if(a<='z'&& a>='a' || a>='A' && a<='Z')
{ push_postfix(a);
c++;}
else
checking_spe(a);
}
//evaluting expression
void evaluting_exp(char a[],int n)
{ int i=0;
while(i<n)
{
checking_char(a[i]);
i++;
}
}//checkin duplicates elements in expression
int checking_dup()
{int j=0,l=0;
for(int i=0;i<=top;i++)
{
if(isalpha(postfix[i]))
dup[j++]=postfix[i];
}
for(int i=0;i<j;i++)
{int c=0;
for(int k=0;k<l;k++)
{
if(org[k]==dup[i])
{c++;
break;}
}
if(c==0)
org[l++]=dup[i];
}
printf("%d\n\n",l);
return l;
}
//evaluting expression
void evaluting_expression(int b,int c)
{int ans=0;j=-1;int k=0;
for(int i=0;i<=top;i++)
{
if(((postfix[i])>='a'&&(postfix[i])<='z')||((postfix[i])>='A'&&(postfix[i])<='Z'))
{ ++j;}
else
{
switch(postfix[i])
{
case '&':ans=(arr[b][j]&&arr[b][j-1]);
arr[b][j-1]=ans;
break;
case '|':ans=(arr[b][j]||arr[b][j-1]);
arr[b][j-1]=ans;
break;
case '~':ans=(!arr[b][j]);
arr[b][j]=ans;
break;
case '_':ans=((!arr[b][j-1])||arr[b][j]);
arr[b][j-1]=ans;
break;
case '=':ans=((!arr[b][j]||arr[b][j-1])&&(!arr[b][j-1]||arr[b][j]));
arr[b][j-1]=ans;
break;
}
if(postfix[i]!='~'){
for(k=j;k<c;k++)
arr[b][k]=arr[b][k+1];
--j;
}
}
}sta[b]=ans;
}
//postfix
void post()
{
for(int t=0;t<=top;t++)
printf("%c",postfix[t]);
}
//main fun
int main()
{
printf("\n\t######## PCNF AND PDNF FOR GIVEN EXPRESSION ########\n\n");
printf("Please follow below instructions:\n");
printf("1.Please make sure your expressioin in parnthesis()\n2.For (Negation) use -->( ~ )\n2.For (and) use -->( & )\n3.For (Or) use -->( | ) \n4.For (Implepicatiton) use -->( _ ) **(MEANS UNDERSCORE)\n5.For (Bi-condition) use --> ( = ) \n");
printf("\n");
printf("\n-->NOTE:PLEASE MAKE SURE YOUR ENTER EXPRESION IS IN CAPTIAL OR SMALL AND FOLLOW ABOVE INSTRUCTIONS\n\n");
printf("\n\nENTER EXPRESSION:");
char exp[100];
scanf("%s",exp);
int len=strlen(exp);
char exp1[len];
strcpy(exp1,exp);
evaluting_exp(exp1,len);
//orginal length of exp
int org_l=checking_dup();
//making posibilites
int pow=2;
for(int i=1;i<org_l;i++)
pow=pow*2;
for(int i=0;i<pow;i++)
{int j=(c+org_l)-1; int t;int m=i;
while(m!=0)
{
t=m%2;
arr[i][j]=t;
ar[i][j]=t;
j--;
m=m/2;
}
}
//assing position
int mm=0;
for(int i=org_l-1;i>=0;i--)
{
dup[(c+org_l-1)-i]=org[mm++];
}
//making oginal posibilites
for(int i=c;i<org_l+c;i++)
{
for(int j=0;j<c;j++)
{
if(dup[i]==dup[j])
{
for(int k=0;k<pow;k++)
ar[k][j]=arr[k][j]=arr[k][i];
}
}
}
while(stack[top1]!='\0')
{
if(stack[top]=='(')
pop_stack();
else
{
push_postfix(stack[top1]);
pop_stack();
}
}
//evaluting expression
for(int i=0;i<pow;i++)
evaluting_expression(i,c);
if(op>=1)
{ for(int i=c;i<c+org_l;i++)
{
printf("%c\t",dup[i]);
}
printf("%s\n",exp);
for(int i=0;i<pow;i++)
{
for(int j=c;j<(c+org_l);j++)
printf("%d \t",ar[i][j]);
printf("%d",sta[i]);
puts("\n");
}
}
else if(c==1)
{int l[2]={0,1};
printf("%s \t%s\n",exp,exp);
for(int i=0;i<2;i++)
printf("%d \t %d\n",l[i],l[i]);
}
printf("PDNF FORM:-->(Minterms)\n");
for(int i=0;i<pow;i++)
{ if(sta[i]==1)
PDNF(i,c,org_l);
}
if(DNF==0)printf("\tTHERE IS NO MINTERMS FOR GIVEN EXPRESSION\n\n");
printf("\nPCNF:-->(Maxterms)\n");
for(int i=0;i<pow;i++)
{ if(sta[i]==0)
PCNF(i,c,org_l);
}
if(CNF==0)printf("\tTHERE IS NO MAXTERMS FOR GIVEN EXPRESSION\n\n");
}
//PDNF FORM
void PDNF(int i,int c,int org_l)
{int j;DNF++;
for( j=c;j<(c+org_l);j++)
{
if(j!=c)
{if(ar[i][j]==1)
printf(" & %c",dup[j]);
else
printf(" & ~%c",dup[j]);
}
else
{if(ar[i][j]==1)
printf("( %c",dup[j]);
else
printf("( ~%c",dup[j]);
}
}
if(j==(c+org_l)&&i!=(c+org_l)-1)
printf(" ) V ");
else
printf(" )");
}
void PCNF(int i,int c,int org_l )
{int j;CNF++;
for( j=c;j<(org_l+c);j++)
{
if(j!=c)
{
if(ar[i][j]==1)
printf(" V ~%c",dup[j]);
else
printf(" V %c",dup[j]);
}
else
{
if(ar[i][j]==1)
printf("( ~%c",dup[j]);
else
printf("( %c",dup[j]);
}
}
if(j==(org_l+c)&&i!=(org_l+c)-1)
printf(") &");
else
printf(" )");
}
