离散数学——用c/c++求命题公式的主范式

接下来需要按运算符优先级对公式进行转换，然后用位运算的方式写出五种运算符的运算方法
假设有两个命题变元a,b(计算时a,b的值为0或1)，下面列出位运算方法（可以举例子试一下）：
非运算：非a:  return （a+1）&1；（例如，a为1，a+1=2, 2在二进制中的表示为10，而位运算是取二进制形式的最后一位数进行运算，则为0&1，
其结果显然为0，即返回值为0，达到了非a的运算效果，以下运算方式类似）
合取：a&b: return a*b；
析取：if(a+b) return 1;else return 0;
条件：if(a==1 && b==0) return 0;else return 1;
双条件：return !((a+b)&1);

然后需要写一个函数来对所有存在的命题变元进行赋值，每个命题变元都有0和1两种情况，这一步可以采用递归来写（具体见代码），每完成一组赋值后都要都要以该组赋值情况确定下标（例如，有a,b,c,三个命题变元，假设某组赋值为101，则其下标为1*（2^0）+1*（2^2）=5，则最后输出范式时下标就为m5或M5,至于是主析取范式还是主合取范式则需看该组赋值的运算结果）

具体内容见代码：

#include
using namespace std;



const int N=1e4;
char s[N];//存放初始字符串 
bool table[30];//标记命题变元是否存在 
int explain[30];//存放每个命题变元的赋值（0或1） 
int value[1000010];//存放每组赋值的最后运算结果 
int sum=0;//下标 
 
int youxian(char c){
	switch(c){//定义运算符的优先顺序 
		case '#':return -1;
		case '!':return 5;
		case '&':return 4;
		case '|':return 3;
		case '-':return 2;
		case '+':return 1;
		case '(':return 0;
		default:return 0;
	}
}

void get_chars(){//将输入的字符串转换为逆波兰式 
	char post[N]={''};int po=-1;//post存放转换后的命题形式，初始化为使strlen求长度时准确 
	char stack[N]={'#'};int st=0;//stack暂时存放运算符 
	int len=strlen(s);
	for(int i=0;i='a' && s[i]<='z'){
			post[++po]=s[i];
			continue;
		}
		if(s[i]=='!'||s[i]=='&'||s[i]=='|'||s[i]=='-'||s[i]=='+'){
			 
			while(youxian(s[i])<=youxian(stack[st])) post[++po]=stack[st--];
			stack[++st]=s[i];
			continue;
		}
		if(s[i]=='('){
			stack[++st]=s[i];
			continue;
		}
		if(s[i]==')'){
			while(stack[st]!='(') post[++po]=stack[st--];//把括号之间的运算符加到post里 
			st--;//完成了一个括号内所有字符转换后,将st重新返回0,为后面的转换做准备 
			continue;
		}
	}
	while(st) post[++po]=stack[st--]; 
	strcpy(s,post);//由于post不是全局变量，所以需要复制给s
	int l=strlen(s);
}
	
void settable(){//统计命题变元的个数 
	memset(table,0,sizeof(table));//将table数组初始化为0 
	int len=strlen(s);
	for(int i=0;i='a'&&s[i]<='z') table[s[i]-'a']=true;//若含有某个变元，则将对应的table值变为1 
	}
	for(int i=0;i<26;i++){
		if(table[i]) sum++;//求命题变元的个数 
	}
	sum=pow(2,sum);//一共2^ans个赋值情况 
}

int boti(){//计算下标，如010表示2 
	int sum=0,wei=1;
	for(int i=25;i>=0;i--){//从后往前依次成二倍相加，把二进制数转换为十进制数 
		if(table[i]){
			if(explain[i]){ 
			    sum+=wei; 
		    }   wei*=2;
		}
	}
	return sum;//sum为最大情况个数 
} 

int cal(int a,int b,char c){//采用位运算对四种运算符进行操作 
	switch(c){
		case'&':return a*b;//合取 
		case'|':if(a+b) return 1;else return 0;//析取 
		case'-':if(a==1 && b==0) return 0;else return 1;//条件，a为真，b为假时为0，其他都为1； 
		case'+':return !((a+b)&1);//按位运算，比如2的二进制为10，则选0&1为结果 
	}
} 

int work(){//按照逆波兰式两两结合计算出最后结果 
	int stack[N],st=-1;
	int len=strlen(s);
	for(int i=0;i='a' && s[i]<='z'){
			stack[++st]=explain[s[i]-'a'];//存入命题的一次赋值(为0或1) 
			continue;
		}
		if(s[i]=='!'){//是！时对上一个字符取非 
			stack[st]=(stack[st]+1)&1;//位运算：+1后再跟1进行与运算可实现非的效果 
			continue;
	    }
	    int ans=cal(stack[st-1],stack[st],s[i]);//两两结合运算 
	    stack[--st]=ans;//每次将st归零 ,下次将stack[0]与stack[1]运算 
	}
	return stack[0];//返回的是最终运算后的结果 
} 

void assign(){//计算一组赋值后的结果,如00010,10100对应的结果 
	int x=boti();
	int ans=work();
	value[x]=ans;
}
void generate(char c){//利用真值表列出所有的取值情况 
	while(c<='z'&&table[c-'a']==false) c++;//因为命题字母可以随意选择，所以要把26个遍历一遍 
	if(c>'z'){//超出z后再计算该组赋值的结果 
		assign();
		return ;
    }
    explain[c-'a']=0;//类似树状图，遍历所有命题变元的0，1取值 
    generate(c+1);
    explain[c-'a']=1;
    generate(c+1); 
}

void output1(){//输出析取范式 
	int i=0;
	while(i= sum){
		printf("无主析取范式n");
		return ;
	}
	printf("主析取范式为：m%d",i);
	for(i++;i= sum){
		printf("无主合取范式n");
		return ;
	}
	printf("主合取范式为：M%d",i);
	for(i++;i>s;
	get_chars();
	settable();
	memset(value,0,sizeof(value));
	memset(explain,0,sizeof(explain));
	generate('a');//从a开始遍历26个字母 
	output1();
	output2();
	return 0;
}

测试样例如下：