实现功能：输入命题公式的合式公式，求出公式的真值表，并输出该公式的主合取范式和主析取范式。
输入：命题公式的合式公式
输出：公式的主析取范式和主析取范式，输出形式为：“ mi ∨ mj ; Mi ∧ Mj” ，极小项和 ∨ 符号之间有一个空格，极大项和 ∧ 符号之间有一个空格；主析取范式和主合取范式之间用“ ; ”隔开，“ ; ”前后各有一个空格。 永真式的主合取范式为 1 ，永假式的主析取范式为 0 。
输入公式的符号说明：
! 非，相当于书面符号中的 “ ¬ ”
& 与，相当于书面符号中的 “ ∧ ”
| 或，相当于书面符号中的 “ ∨ ”
- 蕴含联结词，相当于书面符号中的 “ → ”
+ 等价联结词，相当于书面符号中的 “ ↔ ”
( 前括号
) 后括号
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示 a&b↵ 以文本方式显示 m3 ; M0 ∧ M1 ∧ M2↵ 无限制 64M 0 测试用例 2 以文本方式显示 a|b↵ 以文本方式显示 m1 ∨ m2 ∨ m3 ; M0↵ 无限制 64M 0 思路：栈模拟+暴力枚举 #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <functional> #include <cmath> #include <vector> #include <queue> #include <deque> #include <stack> #include <map> #include <set> #include <ctime> #define INF 0x3f3f3f3f #define maxn 100100 #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; int Value[N], ans[N]; char Exist[N]; int cnt; class Stack { private: int topdata; char *data = new char[N]; public: void init()//初始化构造函数 { topdata = 0; } int is_Empty()//判断栈空 { if (!topdata) { return 1; } return 0; } void push(int n)//压栈 { data[topdata++] = n; } char pop() { return data[--topdata]; } char front()//查看栈顶 { return data[topdata - 1]; } void bye() { delete[] data; } }; int get_Priority(char ch)//优先级处理 { switch (ch) { case '!': return 5; case '|': return 4; case '&': return 3; case '-': return 2; case '+': return 1; case ')': return 6; case '(': return 0; default: return -1; } } int get_Value(char ch)//获得变量ch数值 { if (ch <= 'z' && ch >= 'a') { return Value[ch]; } if (ch == '0' || ch == '1') { return ch - '0'; } return -1; } int get_Value(int n)//获得第n个变量数值(重载get_Value函数) { if (n < cnt) return Value[Exist[n]]; return -1; } bool is_Word(char ch)//判断是否是变量 { if (ch <= 'z' && ch >= 'a') { return 1; } return 0; } void set_Value(int ch_id, int i)//设置变量值 { if (ch_id < cnt) Value[Exist[ch_id]] = i; } int solve(char single, Stack &word)//计算不同运算符 { int b = word.pop(); int a = word.pop(); switch (single) { case '|': return a | b; case '&': return a & b; case '-': return (!a) | b; case '+': return a == b; case '!': word.push(a); return !b; default: return -3; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif char ch[maxn]; while (~scanf("%s", ch)) { bool flag = 0; memset(ans, 0, sizeof(ans)); int one = 0, zero = 0; cnt = 0; int len = strlen(ch); for (int i = 0; i < len; i++)//遍历变量数量 if (is_Word(ch[i])) { flag = 1; for (int j = 0; j < cnt; j++) if (Exist[j] == ch[i]) { flag = 0; break; } if (flag) { Exist[cnt] = ch[i]; cnt++; } } for (int i = 0; i < cnt; i++)//对变量排序 for (int j = i + 1; j < cnt; j++) if (Exist[i] > Exist[j]) swap(Exist[i], Exist[j]); Stack word, sign; for (int i = 0; i < (1 << cnt); i++)//对每一个真值表数值进行计算 { word.init(); sign.init(); for (int j = 0; j < len; j++) if (is_Word(ch[j]) || ch[j] == '0' || ch[j] == '1') word.push(get_Value(ch[j])); else { if (get_Priority(ch[j]) == 6)//右括号 { while (get_Priority(sign.front())) word.push(solve(sign.pop(), word)); sign.pop(); } else if (!get_Priority(ch[j]))//处理括号 sign.push(ch[j]); else { while ((!sign.is_Empty()) && get_Priority(sign.front()) > get_Priority(ch[j]))//如果后面优先度小于前面则进行计算 word.push(solve(sign.pop(), word)); sign.push(ch[j]); //将符号压栈 } } while (!sign.is_Empty())//读完后进行计算 word.push(solve(sign.pop(), word)); if (word.front() == 1) { one++; ans[i]++; } else if (word.front() == 0) { zero++; ans[i]--; } int j = cnt - 1; while (get_Value(j) > 0)//真值表加1 j--; set_Value(j, 1); j++; while (j <= cnt - 1) { set_Value(j, 0); j++; } } word.bye(); sign.bye(); int j = 0; for (int i = 0; i < one; i++) //输出计算结果 { while (ans[j] <= 0) j++; printf("m%d", j); if (i < one - 1) printf(" ∨ "); j++; } if (!one) putchar('0'); printf(" ; "); j = 0; for (int i = 0; i < zero; i++) //输出计算结果 { while (ans[j] >= 0) j++; printf("M%d", j); if (i < zero - 1) printf(" ∧ "); j++; } if (!zero || !cnt) putchar('1'); puts(""); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }