计算主析取范式
【问题描述】
请根据给定的命题公式，计算其真值为T的小项，列出主析取范式，并输出结果。
【输入形式】
输入一个字符串（字符串长度<=50）形式的命题公式，以回车表示输入结束。其中的命题公式为仅包含原子命题、联结词和括号的合式公式。联结词仅包含下述5中联结词：
1、否定，表示为“!”
2、合取，表示为“*”
3、析取，表示为“|”
4、条件，表示为“-”
5、双条件，表示为“=”
例如：
(P-Q)-R
注意：输入符号均采用英文输入。
【输出形式】
输出一个以单个空格分隔的字符串，字符串中各项分别对应主析取范式中小项的序号。
如(P-Q)- R对应的小项为
则输出1 3 4 5 7
注意：其中的原子命题按字母表排序。
【样例输入】
(P-Q) - R
【样例输出】
1 3 4 5 7
解题思路
0.真值表法基础
定义：
在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为公式的主析取范式。
1.代码实现
给各个原子命题设定初值（T/F）,然后计算命题公式的真值，如果为真，就输出原子命题对应的数字。
先对字母赋初值，赋值的方式是把数字转化为二进制序列，然后按照字母顺序一个一个赋值。具体实现方式看下面代码。
代码
#include<bits/stdc++.h> #include<set> #define N 55using namespace std;bool Flag[N];set<char> Set; //用来存储用了哪些字符map<char,char> Map;// (!P*Q)|(P*!Q)char Calculate(char a,char op,char b){if( op == '*' ){if( a == b && b == '1' ) return '1';else return '0';}else if( op == '|' ){if( a == b && b == '0' ) return '0';else return '1';}else if( op == '-' ){if( a == '1' && b == '0' ) return '0';else return '1';}else if( op == '='){if( a == b ) return '1';else return '0';}}//检测不带括号的字符串 char Check(string tem){ //tem是01字符 int Negation,AndOr,Condition; int temlen = tem.size(); // ！运算for(int i = 0;i < temlen; i++){if(tem[i]!='!') continue; int ri = i;tem[i] = ' '; while(tem[i]!='0' && tem[i]!='1'){i++;}if(tem[i]=='0') tem[i] = '1';else tem[i] = '0'; } temlen = tem.size();// *和|运算for(int i = 1;i < temlen;i++){if(tem[i]!='*' && tem[i]!='|') continue; int li = i,ri = i;while(tem[li]!='0' && tem[li]!='1') li--;while(tem[ri]!='0' && tem[ri]!='1') ri++;tem[i] = Calculate(tem[li],tem[i],tem[ri]);tem[li] = ' ',tem[ri] = ' ';} //-和=运算for(int i = 1;i < temlen;i++){if(tem[i]!='-' && tem[i]!='=') continue;int li = i,ri = i;while(tem[li]!='0' && tem[li]!='1') li--;while(tem[ri]!='0' && tem[ri]!='1') ri++;tem[i] = Calculate(tem[li],tem[i],tem[ri]);tem[li] = ' ',tem[ri] = ' ';} //返回结果 for(int i = 0;i<temlen;i++) if(tem[i]=='1') return '1';return '0';}//检查带括号的逻辑表达式 bool CheckWithParentheses(string tem){stack<char> Sta;int temlen = tem.size();for(int i = 0;i<temlen;i++){//处理每个字符if(tem[i] == ')'){//字符串匹配string str = "";int Size = Sta.size(); while(Size--){char C = Sta.top();Sta.pop();if(C == '(') {Sta.push(Check(str));break;}str = C + str; } } else{Sta.push(tem[i]); } }//所有的括号都去掉了，检查最后的表达式string str = "";while(Sta.size()) str = Sta.top()+str,Sta.pop();if(Check(str)=='0') return 0;return 1; }//更新Flag数组 void Initial(int K){int len; memset(Flag,0,sizeof(Flag));for(int i = 0 ; i <= 55; i++){Flag[i] = K%2;len = i;K/=2;if( K==0 ) break;} return ;}//把字母换成01值 string Transform(string s){//遍历字符串，将字母加入set中int lens = s.size(); //给对应的字母赋值0或1int pos = 0;auto it = Set.end();while(1){it--; Map[*it] = int(Flag[pos++])+'0'; if(it == Set.begin()) break; } //改变字符串for(int i = 0;i < lens;i++){if(isalpha(s[i])){s[i] = Map[ s[i] ] ;}} return s;} //求a的n次方 int qpow(int a, int n) { if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a; else { int temp = qpow(a, n / 2); return temp * temp; }}int main(){ string s,Storage;cin>>s; Storage = s;//字母加进集合中 int lens = s.size();for(int i = 0; i < lens ; i++){if(isalpha(s[i])) Set.insert(s[i]);} //初始化测试int Max = qpow(2,Set.size()); for(int i = 0;i < Max ;i++){ s = Storage;Initial(i); //把字母变成01符号 s = Transform(s); if( CheckWithParentheses(s) ) cout<<i<<' '; }cout<<endl; return 0;}/*1、否定，表示为"!" 直接取反 2、合取，表示为"*" 同真为真 3、析取，表示为"|" 同假为假 4、条件，表示为"-" 前真后假为假 5、双条件，表示为"=" 相同为真 */