#include<stdlib.h>
#include<stdio.h>
#include<iostream.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(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) exit(0);
e=*--st.top;
}
void gettop(sqstack &st,bitree &e)
{
if(st.top==st.base) exit(0);
e=*(st.top-1);
}
//重言式的识别函数；
void creattree(char s[],bitree &tree)
{
sqstack variable; //变量栈;
sqstack logic; //逻辑运算符栈;
creatstack(variable);
creatstack(logic);
bitree logic_di,variables,logics,e,a,b,theta,kuohao; //定义栈中的元素;
//theta为最后的二叉树的根;
logic_di=(bitree)malloc(sizeof(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(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(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(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;
cout<<"请依次输入你的变元取值"<<endl;
for(i=65;i<65+N;i++)
{
cout<<char(i)<<" = ";
cin>>zuhe[i-65];
}
}
void main()
{
char str[str_max],string[str_max],*pstr;
int loop=20,choice,i=0,choose,sum;
bitree Tree;
while(loop)
{
pstr=str;
i=0;
int SUM=0,l; //用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式类别判别的根据
cout<<"请输入逻辑表达式的变量的个数"<<endl;
cin>>N;
sum=int(pow(2,N)); //变量组合的总数;
cout<<"请输入逻辑表达式的表达式(或用'|',与用'&'和非用'~')"<<endl;
cin>>str;
//重言式的正确读取;
for(;*pstr!=NULL;pstr++)
if(*pstr!=' ') string[i++]=*pstr;
string[i]='#';
string[i+1]='\0';
cout<<"************ 请选择你要的操作 **********"<<endl;
cout<<"************ 1 逻辑表达式的判别(不显示各种取值组合的结果) **********"<<endl;
cout<<"************ 2 逻辑表达式的判别(并显示各种取值组合的结果) **********"<<endl;
cout<<"************ 3 逻辑表达式的求值(根据用户的取值) **********"<<endl;
cout<<"请选择你要的操作: ";
cin>>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) cout<<"逻辑表达式： "<<string<<" 是矛盾式"<<endl;
if(SUM==sum) cout<<"逻辑表达式： "<<string<<" 是重言式"<<endl;
if (SUM>0&&SUM<sum)cout<<"逻辑表达式： "<<string<<" 既不是重言式，也不是矛盾式"<<endl;
break;
case 2:creattree(string,Tree);//建立重言式的二叉树;
cout<<" 逻辑表达式变量组合的预算结果 "<<endl;
cout<<"---------------------------------------------"<<endl;
printf("| ");
for(l=65;l<65+N;l++)
printf("%-4c",l);
printf("逻辑表达式的值");
printf(" |\n");
cout<<"---------------------------------------------"<<endl;
for(loop=0;loop<sum;loop++)
{
creatzuhe(loop);//产生变量取值组合;
SUM+=value_tree(Tree);
printf("| ");
for(int h=0;h<N;h++)
printf("%-4d",zuhe[h]);
printf("%8d",value_tree(Tree));
printf(" |\n");
cout<<"-------------------------------------------"<<endl;
}
string[i]='\0';
if(SUM==0) cout<<"逻辑表达式： "<<string<<" 是矛盾式"<<endl;
else if(SUM==sum) cout<<"逻辑表达式： "<<string<<" 是重言式"<<endl;
else cout<<"逻辑表达式： "<<string<<" 既不是重言式，也不是矛盾式"<<endl;
break;
case 3: creattree(string,Tree);
user();
cout<<"逻辑表达式的值为："<<value_tree(Tree)<<endl;
break;
}
cout<<"是否继续进行运算？是按1/ 否按0:";
cin>>choice;
if(choice==0)
exit(0);
loop--;
}
}