实现功能：消解算法
输入：合式公式 A 的合取范式
输出：当 A 是可满足时，回答“YES ”；否则回答“NO”。
输入公式的符号说明：
! 非，相当于书面符号中的 “ ¬ ”
& 与，相当于书面符号中的 “ ∧ ”
| 或，相当于书面符号中的 “ ∨ ”
- 蕴含联结词，相当于书面符号中的 “ → ”
+ 等价联结词，相当于书面符号中的 “ ↔ ”
( 前括号
) 后括号
测试输入 期待的输出 时间限制 内存限制 额外进程 测试用例 1 以文本方式显示 (!p|q)&(p|q)&(!q)↵ 以文本方式显示 NO↵ 无限制 64M 0 测试用例 2 以文本方式显示 p&(p|q)&(p|!q)&(q|!r)&(q|r)↵ 以文本方式显示 YES↵ 无限制 64M 0 思路：一种暴力直接的方法是在求范式的基础上直接判断one变量是不是0即可。当然也可以按照消解算法来走，我这里偷了下懒QAQ #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[N]; 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(); if (!one) puts("NO"); else puts("YES"); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }