/******************************************************************************
program for PCNF AND PDNF with representation also
*******************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
char arr[100][100];
char stack[100];
int top=-1,t;
char ch,a[100],b[100];
int j,u,count=0;
char exp[100];
int vi[50];
void bin(unsigned n)
{
int k=0;
static int j=0;
unsigned i;
for(i=1<<(t-1);i>0;i=i/2)
{
if(n & i)
arr[j][k]='1';
else
arr[j][k]='0';
k++;
}
j++;
}
void push(char x)
{
if(top==49)
{
printf("stack is full");
}
else
{
top++;
stack[top]=x;
}
}
char pop()
{
if(top==-1)
{
printf("stack is empty");
}
else
{
ch=stack[top];
top--;
}
return ch;
}
int priority(char x)
{
if(x=='(')
return 0;
if(x=='!')
return 4;
if(x=='|')
return 3;
if(x=='&')
return 2;
if(x=='>'|| x=='<')
return 1;
}
void postfix()
{
char *e,x;
printf("Enter the expression (without spaces & maintain paranthesis properly):");
scanf("%s",exp);
e=exp;
int i=0,j=0;
while(*e!=NULL)
{
if(isalpha(*e))
{
a[j]=exp[i];
j++;
}
else if(*e=='(')
{
push(*e);
}
else if(*e==')')
{
while((x=pop())!='(')
{
a[j]=x;
j++;
}
}
else
{
while(priority(stack[top]) >= priority(*e))
{
pop();
a[j]=stack[top+1];
j++;
}
push(*e);
}
e++;
i++;
}
while(top!=-1)
{
pop();
a[j]=stack[top+1];
j++;
}
printf("\n postfix expression :");
for(i=0;i<j;i++)
{
b[i]=a[i];
printf("%c",a[i]);
}
}
int main()
{
int i,k;
printf("------------READ INSTRUCTIONS---------\n Enter the no of variables in the expression:");
scanf("%d",&t);
if(t>5)
{
printf("\n-----THIS PROGRAM IS UPTO 5 VARIABLES ONLY------\n\n");
exit(0);
}
printf("use only p,q,r,s,t variables \n for and ----> & \n for or ----> | \n for not ----> ! \n for implies ----> > \n for biimplies ----> < \n");
u=pow(2,t);
for(i=0;i<u;i++)
{
bin(i);
}
postfix();
printf("\n");
printf("\n-------TRUTH TABLE--------\n");
int asc=112;
for(i=0;i<t;i++)
{
printf("%c ",asc);
asc++;
}
printf("\t");
for(i=0;i<strlen(exp);i++)
{
printf("%c",exp[i]);
}
printf("\n");
for(i=0;i<u;i++)
{
for(k=0;k<t;k++)
printf("%c ",arr[i][k]);
printf("\t");
assign();
eval();
printf("\n");
}
printf("\n\n");
printf(" PDNF:");
pdnf();
printf("\n Representation: %c ",228);
for(i=0;i<u;i++)
{
if(vi[i]==1)
printf("%d ",i);
}
printf("\n\n");
printf("\n PCNF:");
pcnf();
printf("\n Representation: %c ",227);
for(i=0;i<u;i++)
{
if(vi[i]==0)
printf("%d ",i);
}
}
void assign()
{
int m,i;
static int j=0;
for(m=0;m<(strlen(a));m++)
{
if(b[m]=='p')
a[m]=arr[j][0];
else if(b[m]=='q')
a[m]=arr[j][1];
else if(b[m]=='r')
a[m]=arr[j][2];
else if(b[m]=='s')
a[m]=arr[j][3];
else if(b[m]=='t')
a[m]=arr[j][4];
else
a[m]=a[m];
}
j++;
}
void eval()
{
int i=0,num1=0,num2=0,ans=0,j,aci=112;
char n;
static int k=0;
while(i<(strlen(a)))
{
n=a[i];
if(isdigit(n))
{
push(n-'0');
}
else
{
switch(n)
{
case '&':
num1=pop();
num2=pop();
ans=num1&&num2;
break;
case '|':
num1=pop();
num2=pop();
ans=num1||num2;
break;
case '!':
num1=pop();
ans=!num1;
break;
case '>':
num1=pop();
num2=pop();
ans=!num2||num1;
break;
case '<':
num1=pop();
num2=pop();
ans=(!num2||num1)&&(!num1||num2);
break;
}
push(ans);
}
i++;
}
printf("%d",ans);
vi[k]=ans;
k++;
}
void pdnf()
{
int i,j;
for(i=0;i<u;i++)
{
if(vi[i]==1)
count=i;
}
for(i=0;i<u;i++)
{
int aci=112;
static int v=0;
if(vi[i]==1)
{
printf("(");
for(j=0;j<t;j++)
{
if(arr[v][j]=='0')
printf("~%c",aci);
else
printf("%c",aci);
aci++;
if(j<t-1)
{
printf("^");
}
}
printf(")");
if(i<count)
printf("v");
}v++;
}
}
void pcnf()
{
int i,j;
for(i=0;i<u;i++)
{
if(vi[i]==0)
count=i;
}
for(i=0;i<u;i++)
{
int aci=112;
static int v=0;
if(vi[i]==0)
{
printf("(");
for(j=0;j<t;j++)
{
if(arr[v][j]=='1')
printf("~%c",aci);
else
printf("%c",aci);
aci++;
if(j<t-1)
{
printf("v");
}
}
printf(")");
if(i<count)
printf("^");
}v++;
}
}
