main.cpp

这是一个关于数据结构重言式的判别

#include"StackTree.h"
#define MAX 100
char aOPND[6]={'|','&','~','(',')','#'};//运算符
int flag[MAX];//组合数的值
char letter[MAX];//变量的字符
int In(char a){//查看运算符的位置
	int i;
	for(i=0;i<5;i++)
		if(a==aOPND[i]) break;
		else continue;
		if(i==5) return 0;
		else return i+1;
}
char Priority[6][6]={//运算符的优先级
	{'>','<','<','<','>','>'},
	{'>','>','<','<','>','>'},
	{'>','>','>','<','>','>'},
	{'<','<','<','<','=',' '},
	{'>','>','>',' ','>','>'},
	{'<','<','<','<',' ','='}
};
char Precede(char letter1,char letter2){//获取运算符的优先级
	return Priority[In(letter1)-1][In(letter2)-1];
}
void FindLetter(char *s,int &n){//该函数用于找出输入串中的字母数，并将它们存储在letter[]中
	int i;
	char *p;
	p=s;
	n=0;
	while(*p!='\0'){
		if(!In(*p))
		if(n==0) {
			letter[0]=*p;
			n++;
		}//if 填第一个字母
		else {
			for(i=0;i<n;i++)
				if(letter[i]==*p) break;//是否已经有了该字母
				if(i==n){ 
				letter[n]=*p;
				n++;
				}
		}//else 
		//if(!In(*p)
		p++;
	}//while
}
void CreateTree(char s[],BiTree &T){
	SqStack OPTR;//运算符栈
	SqStack OPND;//运算数栈
	BiTree variable,logic,theta,firstin,e,a,b,bracket;
	InitStack(OPTR);
	InitStack(OPND);
	firstin=(BiTree)malloc(sizeof(BtNode));
	if(!firstin){
		printf("Tree malloc error in func CreateTree\n");
		exit(1);
	}
	firstin->data='#';//推入标志符
	Push(OPTR,firstin);
	while(*s!=NULL){
		if(*s>='A'&&*s<='Z'){//若该符号为变量的情况
			variable=(BiTree)malloc(sizeof(BtNode));
			variable->data=*s;
			Push(OPND,variable);
		}
		else if(*s<'A'||*s>'Z'){//该符号为运算符
			GetTop(OPTR,e);
			switch(Precede(*s,e->data)){
			case '<'://运算符优先级低进栈
				logic=(BiTree)malloc(sizeof(BtNode));
				logic->data=*s;
				Push(OPTR,logic);
				break;
			case '='://为括号的情况
				Pop(OPTR,bracket);break;
			case '>':Pop(OPTR,theta);
				Pop(OPND,a);
				b=NULL;
				if(theta->data!='~')
					Pop(OPND,b);
				Create(theta,b,a);
				Push(OPND,theta);
			if(*s!='#'&&*s!=')'){
			logic=(BiTree)malloc(sizeof(BtNode));
			logic->data=*s;
			Push(OPTR,logic);
			}
			else s=s-1;
			break;
			}
		}
		s++;
	}
	T=theta;
}
int GetValue(char a){
	int i;
	for(i=0;i<MAX;i++)
		if(a==letter[i])
			return flag[i];//返回一个组合值
		else continue;
		printf("error in GetValue\n");
		exit(1);
}
int ValueTree(BiTree T){
	if(!T) return 0;
	else if(T->data!='&'&&T->data!='|'&&T->data!='~')//非运算符则返回变量在组合函数中的值
		return GetValue(T->data);
	else if(T->data<'A'||T->data>'Z'){
		switch(T->data){
		case '|':return ValueTree(T->lchild)||ValueTree(T->rchild);break;
		case '&':return ValueTree(T->lchild)&&ValueTree(T->rchild);break;
		case '~':return (!ValueTree(T->lchild));break;//标记一下，该处可能为T->rchild
		}
	}
}
void CreateCombine(int n){//软计数器实现，flag    1代表有该数，0代表无该数
    long i,j,tmp,m=1;        

    for(i=1;i<=n;i++) m=m*2;
    for(i=1;i<=m;i++){
        tmp=i;
        for(j=1;j<=n;j++){
            flag[j]=tmp%2;
            tmp=tmp/2;
        }
    }
}
void Info(){
	printf("输入一个表达式\n");
	printf("如果恒为真则输出True forever,恒为假输出False forever,否则输出Satisfactible\n");
}
int main(){
	int n,j,valueflag=-1;//n代表不同的变量数,valueflag用于判断重言式是哪一种类型
	BiTree T;
	char str[MAX];//str用于获取输入串
	Info();
	gets(str);
	FindLetter(str,n);//将str中的不同的变量数存于数组letter中，并且算出变量个数n
	CreateTree(str,T);
	for(j=0;j<n;j++){
		CreateCombine(j);//产生组合数
		if(ValueTree(T)==0&&(valueflag==-1||valueflag==0))			valueflag=0;//valueflag=0代表重言式值为假
		if(ValueTree(T)==1&&(valueflag==-1||valueflag==1))			valueflag=1;//valueflag=0代表重言式值为真
		else break;
	}
	if(j<n) printf("Satisfactible\n");
	else if(j==n&&valueflag==0) printf("False forever\n");
	else if(j==n&&valueflag==1) printf("True forever\n");
	else printf("Unkown value need to test\n");
	return 0;
}