本文章代码部分转载https://blog.csdn.net/DaDaMr_X/article/details/51265230
我增加了较多的注释，便于大家更好的理解
由于命题公式的很多符号我们无法从键盘录入，因此用以下做替换
! 非，替换 “ ¬ ”
& 与，替换 “ ∧ ”
| 或，替换 “ ∨ ”
- 蕴含，替换 “ → ”
+ 等价联结词，替换“ ↔ ”
#include#include #include #define N 1000 #define MAX 10000000 char s[N]; bool table[30]; int explain[30]; int value[MAX]; int sum = 0; int priority(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 postfix() //将输入的公式转换为逆波兰式 { char post[N] = { ' ' }; int pp = -1; char stack[N] = { '#' }; int ps = 0; int len = strlen(s); //len是输入公式的长度 for (int i = 0; i < len; i++) { if (s[i] >= 'a' && s[i] <= 'z') //如果是a到z的字母就直接把字母存入post { post[++pp] = s[i]; continue; } if (s[i] == '!' || s[i] == '&' || s[i] == '|' || s[i] == '-' || s[i] == '+') { while (priority(s[i]) <= priority(stack[ps])) post[++pp] = stack[ps--]; stack[++ps] = s[i]; continue; } if (s[i] == '(') { stack[++ps] = s[i]; continue; } if (s[i] == ')') { while (stack[ps] != '(') post[++pp] = stack[ps--]; ps--; continue; } } while (ps) post[++pp] = stack[ps--];//如果当前符号的优先级大于上一符号的优先级，借助此行代码实现逆波兰式的转换 strcpy(s, post); //把post的值赋给s(字符串复制) int l = strlen(s); } void settable() { memset(table, 0, sizeof(table));//将table初始化，每一项都是零 int len = strlen(s); for (int i = 0; i < len; i++) //遍历输入的公式 { if (s[i] >= 'a' && s[i] < 'z') table[s[i] - 'a'] = true; } //s[i]是a到z的字母，减去字母a的ASCⅡ码并赋值为1，例如若有a，b.则table数组下标为0和1的值就是1 for (int i = 0; i < 26; i++) if (table[i]) sum++; //sum记录变元个数 sum = pow(2, sum); //更新sum的值为变元个数的平方,例如有p，q，r三个变元则sum=8 } int btoi() //此函数用来得到极项的数字下标 { int sum = 0, weight = 1; //weight赋值为1，表示2的0次方 for (int i = 25; i >= 0; i--) //26个英文字母都遍历一边,倒序遍历因为极项的下标是从小加到大 if (table[i]) { if (explain[i]) sum += weight; weight *= 2; //1+2+4...... } return sum; } int calc(int a, int b, char c)//此函数用于两个命题变元的逻辑计算 { switch (c) //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; case '+': return !((a + b) & 1); } } int work() { int stack[N], ps = -1; int len = strlen(s); for (int i = 0; i < len; i++) { if (s[i] >= 'a' && s[i] <= 'z') { stack[++ps] = explain[s[i] - 'a'];//将每次的赋值的结果存入stack continue; } if (s[i] == '!')//因为calc没有写！的情况，此处单列 { stack[ps] = (stack[ps] + 1) & 1; continue; } int ans = calc(stack[ps - 1], stack[ps], s[i]);//两两结合依次运算 stack[--ps] = ans; } return stack[0];//返回某种情况整个逆波兰式的运算结果 } void assign()//计算真值表的每种情况的结果，存入value { int x = btoi(); int ans = work(); value[x] = ans; } void generate(char c) //此函数使用递归，相当于求真值表 { while (c <= 'z' && table[c - 'a'] == false) c++;//把所有的字母都遍历一边直到c>z if (c > 'z') { assign(); return; } explain[c - 'a'] = 0; generate(c + 1); explain[c - 'a'] = 1; generate(c + 1); //使用递归，先把所有字母都赋值为0，从后向前依次赋值1,举出所有情况 } void output1() { int i = 0; while (i < sum && !value[i]) i++;//主析取范式求成真赋值，若极小项的值是0，跳过，继续向后寻找为1的极小项 if (i >= sum) //矛盾式(永假式) { printf("矛盾式(永假式)无主析取范式; "); return; } printf("m%d", i); for (i++; i < sum; i++) if (value[i]) printf(" ∨ m%d", i); printf(" ; "); } void output2() { int i = 0; while (i < sum && value[i]) i++;//主合取范式求成假赋值，若极小项的值是1，跳过，继续向后寻找为0的极大项 if (i >= sum) //永真式(重言式) { printf("永真式(重言式)无主和取范式n"); return; } printf("M%d", i); for (i++; i < sum; i++) if (!value[i]) printf(" ∧ M%d", i); printf("n"); } int main() { scanf("%s", s); //输入公式 postfix(); //首先转换为逆波兰式 settable(); //得到sum(极项的所有情况的个数) memset(value, 0, sizeof(value)); memset(explain, 0, sizeof(explain));//对value和explain进行初始化 generate('a'); //直接传入字符串a保证无遗漏 output1(); //输出主析取范式 output2(); //输出主和取范式 return 0; }
运行结果如下
谢谢大家
