lab3_1.cpp

逻辑表达式从终端输入

///////重言式判别问题////////            
#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)//把变量的个数n转化成二进制数
	{
		e=n%2;
		num++;
		temp[j++]=e;
		n=n/2;

	}
	j=j-1;
	num=N-num;
	while(j>=0)//把二进制数n存放到数组的最后几位
	{
		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--;
	}
}