求命题公式的主范式

实现功能：输入命题公式的合式公式，求出公式的真值表，并输出该公式的主合取范式和主析取范式。

输入：命题公式的合式公式

输出：公式的主析取范式和主析取范式，输出形式为：“ mi ∨ mj ; Mi ∧ Mj” ，极小项和 ∨ 符号之间有一个空格，极大项和 ∧ 符号之间有一个空格；主析取范式和主合取范式之间用“ ; ”隔开，“ ; ”前后各有一个空格。 永真式的主合取范式为 1 ，永假式的主析取范式为 0 。

输入公式的符号说明：

! 非，相当于书面符号中的 “ ¬ ”

& 与，相当于书面符号中的 “ ∧ ”

| 或，相当于书面符号中的 “ ∨ ”

• 蕴含联结词，相当于书面符号中的 “ → ”

• 等价联结词，相当于书面符号中的 “ ↔ ”

( 前括号

) 后括号
主要思路：
1.转化为后缀表达式（去括号）
2.数一下有多少个不同的元素（字母），枚举的时候会用到
3.转化为二进制，用每一位代表一个字母的赋值
4.根据每种可能赋值计算结果并记录
注意：
永真式的主合取范式为 1 ，永假式的主析取范式为 0 。

#include 
#include 
#include 
#include 
using namespace std;
char in[1000];
int order[30], value[30] = { 0 }, as[10000000] = { 0 }, cnt1 = 0, cnt2 = 0;
int priority(char op);
void RPN(int n);
int e_cnt();
int cal(int a, int b, char c);
int rpn_cal();
int main()
{int ecnt, sum;cin >> in;RPN(strlen(in));//转换成后缀表达式ecnt = e_cnt();//计算有几个元素sum = pow(2, ecnt);//计算赋值上界for (int i = 0; i < sum; i++)//枚举{int c = i;memset(value, 0, sizeof(value));for (int j = ecnt-1; j >=0; j--){value[j] = c % 2;c /= 2;}int res = rpn_cal();if (res == 1){as[i] = 1;cnt1++;}else{as[i] = 0;cnt2++;}}for (int i = 0; i < sum; i++){if (as[i] == 1 && cnt1 > 1){cout << 'm' << i << " " << "∨" << " ";cnt1--;}else if (as[i] == 1 && cnt1 == 1){cout << 'm' << i << " " << ";" << " ";}}if (cnt1 == 0)cout << 0 << " " << ";" << " ";for (int i = 0; i < sum; i++){if (as[i] == 0 && cnt2 > 1){cout << 'M' << i << " " << "∧" << " ";cnt2--;}else if (as[i] == 0 && cnt2 == 1){cout << 'M' << i << endl;}}if (cnt2 == 0)cout << 1 << endl;return 0;
}
int priority(char op)//计算权值
{switch (op){case')':return 7;case'!':return 6;case'|':return 5;case'&':return 4;case'-':return 3;case'+':return 2;case'(':return 1;case'#':return 0;default:return -1;}
}
void RPN(int n)//转换成后缀表达式
{int cnt = 0;char post[1000] = { 0 };stack <char> op;op.push('#');for (int i = 0; i < n; i++){if (priority(in[i]) == -1)post[cnt++] = in[i];else{if (in[i] == ')'){while (op.top() != '('){post[cnt++] = op.top();op.pop();}op.pop();}else if(in[i] == '(')op.push(in[i]);else{if (priority(in[i]) > priority(op.top()))op.push(in[i]);else if (priority(in[i]) == priority(op.top())){post[cnt++] = op.top();op.pop();op.push(in[i]);}else{while (priority(in[i]) <= priority(op.top())){post[cnt++] = op.top();op.pop();}op.push(in[i]);}}}}while (priority(op.top()) != 0){post[cnt++] = op.top();op.pop();}for (int i = 0; i < n; i++){in[i] = post[i];}
}
int e_cnt()//计算可能赋值的上界
{int a[30] = { 0 }, ecnt = 0;for (int i = 0; i < strlen(in); i++){if (priority(in[i]) == -1)a[in[i] - 'a']++;}for (int i = 0; i < 30; i++){if (a[i]){order[i] = ecnt;ecnt++;}}return ecnt;
}
int cal(int a, int b, char c)//计算二元运算符
{switch (c){case'&':return a * b;case'|':if(a + b) return 1; else return 0;case'+':return !((a + b) & 1);case'-':if (a == 1 && b == 0) return 0; else return 1;}
}
int rpn_cal()
{stack <int> num;for (int i = 0; i < strlen(in); i++){if (priority(in[i]) == -1){int n = order[in[i] - 'a'];num.push(value[n]);}else if (in[i] == '!'){int temp = num.top();temp = (temp + 1) & 1;num.pop();num.push(temp);}else{int b = num.top();num.pop();int a = num.top();num.pop();int temp = cal(a, b, in[i]);num.push(temp);}}int ans = num.top();num.pop();return ans;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！