chongyanshi.cpp

离散数学重言式判别以及逻辑表达式求值原代码

#include<stdlib.h>
#include<iostream.h>
#include<string.h>
#include<math.h>
#include<iomanip.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)           //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;
	}
}

//自底向上地根据运算符地优先级来建立分子树函数;当逻辑表达式读完后boot_tree就是一棵完整的二叉树
int k=0;//建树的标志，k＝1表示第一次建立分子树，要对左右孩子的指针域处理
void create(bitree &tree,bitree l,bitree r)
{
	tree->lchild=l;
	tree->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 priority(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,boot_tree,kuohao;   //定义栈中的元素;
                  //boot_tree为最后的二叉树的根;
	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(priority(*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,boot_tree);//弹出逻辑运算符
				pop(variable,a);//弹出变量
				b=NULL;
				if(boot_tree->data!='~')
					pop(variable,b);
				//建树的函数调用
				k=k+1;
				create(boot_tree,b,a);
				push(variable,boot_tree);//将临时的根作为新的变量压入变量栈中;
				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=boot_tree;
}
//根据变量的取值组合并利用逻辑表达式的性质对树进行求值 
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<<"请输入表达式,用大写字母ABCD等依次表示变量,可以有括号(或用'|',与用'&'和非用'~')"<<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;
				for(l=65;l<65+N;l++)
					cout<<setw(4)<<char(l);
				cout<<"    表达式值  ";
				cout<<endl;
				cout<<"-----------------------------------------"<<endl;
				for(loop=0;loop<sum;loop++)
				{
					creatzuhe(loop);//产生变量取值组合;
					SUM+=value_tree(Tree);
					for(int h=0;h<N;h++)
						cout<<setw(4)<<zuhe[h];
					cout<<setw(8)<<value_tree(Tree);
					cout<<endl;
					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--;
	}
}