/*问题描述：
一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多情况下，既非重言式，也非矛盾式。
逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”，“&”，“～”，分别表示或、与和非，运算优先程度递增，但可以由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以包含多个空格符。
若是重言式或矛盾式，则显示“True forever”或“False forever”，否则显示“Statisfactible”以及变量名序列，供用户输入各变量名的值，程序然后显示表达式的值?*/
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#define stack_size_normal 100
#define bianliang_max 20
#define str_max 60
int zuhe[bianliang_max];/* 变量的取值组合数组定义; */
int N;/* 变量个数; */
/* 根据表达式建立的二叉树的结点定义; */
typedef struct btdnode{
char data;
struct btdnode *lchild;
struct btdnode *rchild;
}*bitree;
/* 识别表达式使用的堆栈定义,它存放的都是树的结构; */
typedef struct lnode_optr{
struct btdnode **base; /* 栈中的元素都是树的结点结构； */
struct btdnode **top;
int stacksize;
}sqstack;
/* 用于产生变量的各种取值组合; */
void creatzuhe(int n)
{
int i,num=0,j=0,e;
int temp[bianliang_max];
for(i=0;i<N;i++)
zuhe[i]=0;
while(n)
{
e=n%2;
num++;
temp[j++]=e;
n=n/2;
}
j=j-1;
num=N-num;
while(j>=0)
{
e=temp[j--];
zuhe[num++]=e;
}
}
/* 自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后-子根zigen就是一棵完整的二叉树 */
int k=0;/* 建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理 */
void create(bitree zigen,bitree l,bitree r)
{
zigen->lchild=l;
zigen->rchild=r;/* 分树的链接 */
if(l&&r)
{
if((int)(l->data)>=65&&(int)(l->data)<=90)
{
l->lchild=NULL;
l->rchild=NULL;
}
if((int)(r->data)>=65&&(int)(r->data)<=90)
{
r->lchild=NULL;
r->rchild=NULL;
}
}
}
/* 逻辑运算符的优先级判别； */
char youxianji(char lie,char hang)
{
int i,j;
char bijiao[7][7]={' ','|','&','~','(',')','#','|','>','<','<','<','>','>','&','>','>','<','<','>','>','~','>','>','>','<','>','>','(','<','<','<','<','=',' ',')','>','>','>',' ','>','>','#','<','<','<','<',' ','='};
for(i=0;i<7;i++)
if(bijiao[0][i]==lie)
break;
for(j=0;j<7;j++)
if(bijiao[j][0]==hang)
break;
return bijiao[j][i];
}
/* 对操作符栈和变量堆栈的操作； */
void creatstack(sqstack st)
{
st.base=(bitree*)malloc(stack_size_normal*sizeof(struct btdnode));
if(!st.base) exit(0);
st.top=st.base;
st.stacksize=stack_size_normal;
}
void push(sqstack st,bitree e)
{
if(st.top-st.base<st.stacksize)
*(st.top++)=e;
else exit(0);
}
void pop(sqstack st,bitree e)
{
if(st.top==st.base) ;
{ e=*(--st.top);
exit(0);}
}
void gettop(sqstack st,bitree e)
{
if(st.top==st.base);
{e=*(st.top-1);
exit(0) ; }
}
/* 重言式的识别函数； */
void creattree(char s[],bitree tree)
{
sqstack variable; /* 变量栈; */
sqstack logic; /* 逻辑运算符栈; */
bitree logic_di,variables,logics,e,a,b,theta,kuohao;/* 定义栈中的元素; */
creatstack(variable);
creatstack(logic);
logic_di=(bitree)malloc(sizeof(struct btdnode));
if(!logic_di) exit(0);
logic_di->data='#';
push(logic,logic_di);
while(*s!=NULL)
{
if((int)(*s)>=65&&(int)(*s)<=90)
{
variables=(bitree)malloc(sizeof(struct btdnode));
if(!variables) exit(0);
variables->data=*s;
push(variable,variables);
}
else if((int)(*s)>90||(int)(*s)<65)
{
gettop(logic,e);/* 取运算符栈的栈顶元素进行优先级比较 */
switch(youxianji(*s,e->data))
{
case '<': /* 栈顶的运算符优先级低,逻辑运算符进栈 */
logics=(bitree)malloc(sizeof(struct btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
break;
case '=':/* 脱括号并接受下一个字符; */
pop(logic,kuohao);break;
case '>':pop(logic,theta);/* 弹出逻辑运算符 */
pop(variable,a);/* 弹出变量 */
b=NULL;
if(theta->data!='~')
pop(variable,b);
/* 建树的函数调用 */
k=k+1;
create(theta,b,a);
push(variable,theta);/* 将临时的根作为新的变量压入变量栈中; */
if(*s!='#'&&*s!=')')
{
logics=(bitree)malloc(sizeof(struct btdnode));
if(!logics) exit(0);
logics->data=*s;
push(logic,logics);
}
else s=s-1;
break;
}
}
s++;
}
tree=theta;
}
/* 根据变量的取值组合并利用逻辑表达式的性质对树进行求值 */
int value_tree(bitree tree)
{
if(!tree) return 0; /* 遇到空的结点; */
else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~')/* 找到的是变量； */
return zuhe[(int)(tree->data-65)];
else if((int)(tree->data)<65||(int)(tree->data)>90) /* 找到的是运算符; */
switch(tree->data)
{
case '|': return(value_tree(tree->lchild)||value_tree(tree->rchild));
case '&': return(value_tree(tree->lchild)&&value_tree(tree->rchild));
case '~': return(!value_tree(tree->rchild));
}
}
/* 用户设定变量的一种取值； */
void user()
{
int i;
printf("请依次输入你的变元取值");
for(i = 65;i < 65 + N;i ++)
{
printf("%c=",i);
scanf("%c",&zuhe[i-65]);
}
}
main()
{
int SUM=0,l;/* 用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式类别判别的根据 */
int h,sum=(int)(pow(2,N)),N;
char str[str_max],string[str_max],*pstr;
int loop=20,choice,i=0,choose;
bitree Tree;
while(loop)
{
pstr=str;
i=0;
printf("请输入逻辑表达式的变量个数\n");
scanf("%d",&N);
/* 变量组合的总数; */
printf("请输入逻辑表达式的表达式 (或用'|',与用'&'和非用'~')\n");
scanf("%c",&str);
/* 重言式的正确读取; */
for(;*pstr!=NULL;pstr++)
if(*pstr!=' ')
string[i++]=*pstr;
string[i]='#';
string[i+1]='\0';
printf("************ 请选择你要的操作 **********\n") ;
printf("************ 1 逻辑表达式的判别(不显示各种取值组合的结果) **********\n") ;
printf("************ 2 逻辑表达式的判别(并显示各种取值组合的结果） **********\n") ;
printf("************ 3 逻辑表达式的求值(根据拥护的取值) **********\n") ;
printf("请选择你要的操作： \n");
scanf("%d",&choose);
switch(choose)
{
case 1:/* 对变量的不同组合依次调用重言式二叉树的求值函数;并判别重言式的类别; */
creattree(string,Tree);/* 建立重言式的二叉树; */
for(loop=0;loop<sum;loop++)
{
creatzuhe(loop);/* 产生变量取值组合; */
SUM+=value_tree(Tree);
}
string[i]='\0';
if(SUM==0)
printf("逻辑表达式:%s 是矛盾式\n",string);
if(SUM==sum)
printf("逻辑表达式:%s 是重言式\n",string);
if (SUM>0&&SUM<sum)
printf("逻辑表达式:%s 即不是重言式也,不是矛盾式\n",string);
break;
case 2:creattree(string,Tree);/* 建立重言式的二叉树; */
printf("逻辑表达式变量的预算结果\n");
printf("---------------------------------------------\n");
printf("| \n");
for(l=65;l<65+N;l++)
printf("%-4c",l);
printf("逻辑表达式的值");
printf(" |\n");
printf("---------------------------------------------\n");
for(loop=0;loop<sum;loop++)
{
creatzuhe(loop);/* 产生变量取值组合; */
SUM+=value_tree(Tree);
printf("| ");
for( h=0;h<N;h++)
printf("%-4d",zuhe[h]);
printf("%8d",value_tree(Tree));
printf(" |\n");
printf("-------------------------------------------\n");
}
string[i]='\0';
if(SUM == 0)
printf("逻辑表达式:%s 是矛盾式.\n",string);
else if(SUM == sum)
printf("逻辑表达式:%s 是重言式.\n",string);
else
printf("逻辑表达式: %s","不是重言式也不是矛盾式\n",string);
break;
case 3:
creattree(string,Tree);
user();
printf("逻辑表达式的值为%d",value_tree(Tree));
break;
}
printf("是否继续进行运算?是按1/否按0:");
scanf("%d",&choice);
if(choice==0)
exit(0);
loop--;
}
}
