/***********************************************************************
Name : Sohith pamu
Dno : N190830
Branch : CSE
Program to evaluate given WFF(well formed formula)
1)Truth table
2)PDNF expression
3)PCNF expression
*************************************************************************/
#include<stdio.h>
#include<stdlib.h>
const int M_SIZE = 100;
char stack[100];
int stackTop = -1;
int postfix[100];
int postfixTop = -1;
char pfExpresion[100];
char PDNF[100];
char PCNF[100];
int pdnfInd=-1;
int pcnfInd=-1;
int noOfVar=0;
int tValues[] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
char variables[];
int isEmpty(int top)
{
return (top == -1)? 1:0;
}
int isFull(int top)
{
return (top == M_SIZE-1)? 1:0;
}
void push(char arr[],int *top,char ch)
{
if(isFull((*top)))
{
printf("Stack overflow...!\n");
return ;
}
(*top)++;
arr[(*top)] =ch;
}
//function to push an elemtnt into postfix-expression
void pushPF(int val)
{
if(isFull(postfixTop))
{
printf("Stack overflow...!\n");
return ;
}
postfixTop++;
postfix[postfixTop] = val;
}
//function to pop an element from the postfix expression
int popPF()
{
if(isEmpty((postfixTop)))
{
printf("Stack underflow....!\n");
exit(1);
}
return postfix[postfixTop--];
}
//function to pop an element form stack
char pop(char arr[],int *top)
{
if(isEmpty((*top)))
{
printf("Stack underflow....!\n");
exit(1);
}
(*top)--;
return arr[*top+1];
}
//function to return a element form stack
char peek(char arr[],int top)
{
if(isEmpty((top)))
{
printf("Stack underflow....!\n");
exit(1);
}
return arr[top];
}
void print(char arr[],int top)
{
printf("Stack : ");
while(top != -1)
printf("%c ",arr[top--]);
printf("\n");
}
//function to return array length
int getLen(char arr[])
{
int count =0;
while(arr[count] != '\0')
count++;
return count;
}
//fucntion to check the open bracket and closed bracked
int isMatch(char a, char b)
{
if(a=='}' && b =='{')
return 1;
else if(a ==')' && b == '(')
return 1;
else if(a ==']' && b == '[')
return 1;
else if(a == '>' && b == '<')
return 1;
return 0;
}
int isOpenBracket(char c)
{
return (c == '{') || (c == '[') || (c == '(') || (c == '<')?1:0;
}
int isCloseBracket(char c)
{
return (c == '}') || (c == ']') || (c == ')') || (c == '>')?1:0;
}
int isOpertaor(char c)
{
return ( (c == '~') || (c == '&') || (c == '|') || (c == '@') ||(c =='*') )?1:0;
}
//fuction to get priority of operator
int priorityOf(char c)
{
switch (c)
{
case '~':
return 5;
break;
case '&':
return 4;
break;
case '|':
return 3;
break;
case '@':
return 2;
break;
case '*':
return 1;
}
}
//fucntions to do logical operations
int negation(int n)
{
return !n;
}
int conjunction(int a, int b)
{
return (a && b);
}
int disjunction(int a, int b)
{
return ( a || b );
}
int implication(int a, int b)
{
return (!a || b);
}
int biconditional(int a, int b)
{
return ((!a || b) && (!b || a));
}
//functions to check whether the given expression is valid or not
int isValid(char eq[])
{
int pos = 0;
while(eq[pos])
{
if( isOpenBracket(eq[pos]))
push(stack,&stackTop,eq[pos]);
else if( isCloseBracket(eq[pos]) )
{
if(isEmpty(stackTop))
return 0;
if(!(isMatch(eq[pos], pop(stack,&stackTop))))
return 0;
}
pos++;
}
if(isEmpty(stackTop))
return 1;
return 0;
}
//funciton to find the index of variable in the variables array
int findInd(char c)
{
for(int i=0;i<noOfVar;i++)
if(variables[i] == c)
return i;
return -1;
}
//function to convert given expresstion in to postfix expression
void getPostfixExp(char str[])
{
int pos = -1,i;
push(stack,&stackTop,'(');
for(i = 0 ;i<getLen(str);i++)
{
if(isOpenBracket(str[i]))
push(stack,&stackTop,str[i]);
else if(isCloseBracket(str[i]))
{
while( !isOpenBracket(peek(stack,stackTop)) )
{
pfExpresion[++pos] = pop(stack,&stackTop);
}
pop(stack,&stackTop);
}
else if(isOpertaor(str[i]))
{
while (isOpertaor(peek(stack,stackTop)) && ( (priorityOf(peek(stack,stackTop))) >= (priorityOf(str[i])) ))
{
pfExpresion[++pos] = pop(stack,&stackTop);
}
push(stack,&stackTop,str[i]);
}
else if(str[i] == ' ')
{
}
else
{
pfExpresion[++pos] = str[i];
if(findInd(str[i]) == -1)
{
variables[noOfVar++] = str[i];
}
}
}
while (isOpertaor(peek(stack,stackTop)) && ( (priorityOf(peek(stack,stackTop))) >= (priorityOf(str[i])) ))
{
pfExpresion[++pos] = pop(stack,&stackTop);
}
push(stack,&stackTop,str[i]);
}
//fucntion to find the value of a variable
int val(char c)
{
return tValues[findInd(c)];
}
//fucntion to call logialoperation's functions based on the operator
void doOperation(char c)
{
int a, b;
switch (c)
{
case '~':
pushPF(negation(popPF()));
break;
case '&':
pushPF(conjunction(popPF(),popPF()));
break;
case '|':
pushPF(disjunction(popPF(),popPF()));
break;
case '@':
a = popPF();
b = popPF();
pushPF(implication(b,a));
break;
case '*':
pushPF(biconditional(popPF(),popPF()));
}
}
//power function
int pow(int base, int expo)
{
int result =1;
while(expo>0)
{
result *= base;
expo--;
}
return result;
}
//fucntion to convert a number in to it's binary form
void toBinary(int i)
{
int pos =noOfVar-1;
int place=0;
for(int i=0;i<noOfVar;i++)
tValues[i] = 0;
while(i)
{
tValues[pos--] = i%2;
i /= 2;
}
}
//function to evaluate the postfix expression
int evaluationPFExpression()
{
for(int i = 0; i< getLen(pfExpresion);i++)
{
if(isOpertaor(pfExpresion[i]))
{
doOperation(pfExpresion[i]);
}
else
{
pushPF( val(pfExpresion[i]));
}
}
return popPF();
}
//main funciton
int main()
{
char equation[50];
printf("Enter a WFF using the folloiwng convctivities : \n");
printf("\t ~ --> Negation\n\t & --> conjunction\n\t | --> disjunction\n\t @ --> Implication \n\t * --> Biconditional\n\n");
printf("Expression(without spaces) : ");
scanf("%s",&equation);
if(!isValid(equation))
{
printf("\n\tYou have entered an invalid expression ....!\n\n");
exit(1);
}
printf("\nTruth table : \n\t");
getPostfixExp(equation);
for(int i=0;i<noOfVar;i++)
printf("%c ",variables[i]);
printf(" %s \n",equation);
int iterations = pow(2,noOfVar);
for(int i=0;i<iterations;i++)
{
toBinary(i);
printf("\t");
for (int j = 0; j < noOfVar; j++)
{
printf("%d ",tValues[j]);
}
printf(" %d \n",evaluationPFExpression() );
if(evaluationPFExpression())
{
PDNF[++pdnfInd] = '(';
for (int j = 0; j < noOfVar; j++)
{
if(tValues[j])
{
PDNF[++pdnfInd] = variables[j];
}
else
{
PDNF[++pdnfInd] = '~';
PDNF[++pdnfInd] = variables[j];
}
if(j< noOfVar-1)
{
PDNF[++pdnfInd] = '^';
}
}
PDNF[++pdnfInd] = ')';
PDNF[++pdnfInd] = 'v';
}
else{
PCNF[++pcnfInd] = '(';
for (int j = 0; j < noOfVar; j++)
{
if(tValues[j])
{
PCNF[++pcnfInd] = '~';
PCNF[++pcnfInd] = variables[j];
}
else
{
PCNF[++pcnfInd] = variables[j];
}
if(j< noOfVar-1)
{
PCNF[++pcnfInd] = 'v';
}
}
PCNF[++pcnfInd] = ')';
PCNF[++pcnfInd] = '^';
}
}
PDNF[pdnfInd] = '\0';
PCNF[pcnfInd] = '\0';
printf("\n\n\tPDNF eq : %s\n",PDNF);
printf("\tPCNF eq : %s\n\n",PCNF);
return 0;
}
