c++计算并输出复合命题真值表

目录

• 问题描述
• 解决思路
• • 优先级
  • • 后缀表达式
    • • 中缀表达式转后缀表达式
  • 复合命题运算
• 完整代码

• 问题描述

  输入一个复合命题，计算并输出该命题真值表

• 解决思路

  计算复合命题时最需要注意的就是复合命题的优先级和保证不重不漏的遍历每一个变元真和假的两种情况

• 优先级

  解决复合命题的优先级问题我们需要考虑括号以及运算符的优先级，直接遍历整个复合命题会让问题变的更加复杂
  这时我们可以考虑使用后缀表达式来解决

• 后缀表达式

  我们平时使用的常规的表达式是中缀表达式，每一个运算符都在两个变量或常数之间，而后缀表达式的运算符根据一些规律被移动到了运算符的后面

• 中缀表达式转后缀表达式

  中缀表达式中我们要处理的运算符除了逻辑运算符还有最头疼的括号，转换时使用这样的步骤

1. 使用一个序列来存储还没有找到位置的运算符

2. 遍历表达式，当序列为空的时候将当前正在遍历的运算符存入序列

3. 序列非空时，将当前正在被遍历的运算符与序列中最后一个进入的运算符比较优先级，若该运算符优先级大于序列中最后进入的运算符的优先级则将该运算符放入序列，否则将序列中的运算符提出放入表达式

4. 当碰到左括号时直接放入序列，碰到右括号时将序列中的运算符放入表达式直至碰到左括号

5. 遍历结束后，将序列内的运算符按照从最后一个进入的到最先进入的顺序放入表达式

   不难发现存储运算符的序列符合先进后出的性质，因此考虑用栈实现该过程

stack<char> Stack; 
char all[10005];bool judge(char p, char q){        //判断运算符优先级int x = 0;int y = 0;if(p == '!')x = 5;else if(p == '&')x = 4;else if(p == '|')x = 3;else if(p == '-')x = 2;else if(p == '=')x = 1;if(q == '!')y = 5;else if(q == '&')y = 4;else if(q == '|')y = 3;else if(q == '-')y = 2;else if(q == '=')y = 1;return x > y;
}void change(){char c;for(int i = 0; i < s.length(); i++){if(s[i] >= 'a' && s[i] <= 'z')all[++pos] = s[i];else{   if(s[i] == '(')            //如果是左括号直接压进去Stack.push(s[i]);else if(s[i] == ')')       //如果是有括号弹掉左括号之前的所以的运算符{while(!(Stack.top() == '(')){all[++pos] = Stack.top();Stack.pop();}Stack.pop();          //弹左括号}else{if(Stack.empty())     //栈空直接进栈Stack.push(s[i]);else                  //非空就比较优先级{while(!judge(s[i],Stack.top())) //如果当前复合优先级小于等于栈顶符号的就弹栈{all[++pos] = Stack.top();Stack.pop();if(Stack.empty()) //防止弹空栈break;}  Stack.push(s[i]);     //压入当前运算符}}}}while(!Stack.empty())  //全部处理完之后将栈内剩余的运算符放到表达式里{if(Stack.top() != '(' && Stack.top() != ')'){all[++pos] = Stack.top();}Stack.pop();}
}

• 复合命题运算

  计算复合命题时要考虑到每一个变元的每一种情况，很容易想到用循环来解决，但是嵌套的循环只能解决固定个数的变元，所以我们可以考虑使用递归，应用到的思想与dfs+回溯类似
  由于此时表达式已经被转化成后缀表达式，因此只需要使用后缀表达式的计算方法进行计算，即遍历表达式，将变元转化为真值放入序列，碰到运算符时将序列中最后一个进入的和倒数第二个进入的变元拿出进行运算，将结果放回序列

bool getans(){                              //计算复合命题while(!P.empty())P.pop();int tot = 0;for(int i = 0; i <= pos; i++){bool x, y;if(all[i] >= 'a' && all[i] <= 'z')P.push(t[++tot]);else if(all[i] == '!'){x = P.top();P.pop();P.push(deny(x));}else{x = P.top();P.pop();y = P.top();P.pop();if(all[i] == '&')P.push(And(x,y));else if(all[i] == '|')P.push(Or(x,y));else if(all[i] == '-')P.push(contain(x,y));else if(all[i] == '=')P.push(equal(x,y));}}return P.top();
}void dfs(int now)   //now表示当前正在遍历第几个变元
{if(now > cnt)  //now>cnt时每一个变元都被已经遍历到{for(int i = 1; i <= cnt; i++) //输出每一个变元的真值{cout << t[i] << " ";}cout << getans() << endl;    //计算整个命题的真值return;                      //回溯}//如果没有遍历完t[now] = 1; //假设第now个变元真值为1dfs(now+1);t[now] = 0; //假设第now个变元真值为2dfs(now+1);
}

• 完整代码

  重要的步骤都在上面讲过了，下面就是完整的代码了

#include
#include
#include
using namespace std;// ！为否定 |为析取 &为合取 -为蕴含 =为等价int pos = -1;                     //后缀表达式长度
int cnt = 0;                      //变元数量                   
char all[10005];                  //储存后缀表达式
string s;
int t[26];                        //搜索参数数组
stack<char> Stack;                //中缀转后缀栈
stack<bool> P;                    //运算栈void read(){                      //从文件读入复合命题并计算变元个数ifstream fin ("text.txt");fin >> s;cout << s << endl;for(int i = 0; i < s.length(); i++){if(s[i] >= 'a' && s[i] <= 'z')cnt++;}
}bool judge(char p, char q){        //判断运算符优先级int x = 0;int y = 0;if(p == '!')x = 5;else if(p == '&')x = 4;else if(p == '|')x = 3;else if(p == '-')x = 2;else if(p == '=')x = 1;if(q == '!')y = 5;else if(q == '&')y = 4;else if(q == '|')y = 3;else if(q == '-')y = 2;else if(q == '=')y = 1;return x > y;
}void change(){                          //中缀表达式转后缀表达式char c;for(int i = 0; i < s.length(); i++){if(s[i] >= 'a' && s[i] <= 'z')all[++pos] = s[i];else{   if(s[i] == '(')            //如果是左括号直接压进去Stack.push(s[i]);else if(s[i] == ')')       //如果是有括号弹掉左括号之前的所以的运算符{while(!(Stack.top() == '(')){all[++pos] = Stack.top();Stack.pop();}Stack.pop();          //弹左括号}else{if(Stack.empty())     //栈空直接进栈Stack.push(s[i]);else                  //非空就比较优先级{while(!judge(s[i],Stack.top())) //如果当前复合优先级小于等于栈顶符号的就弹栈{all[++pos] = Stack.top();Stack.pop();if(Stack.empty()) //防止弹空栈break;}  Stack.push(s[i]);     //压入当前运算符}}}}while(!Stack.empty())  //全部处理完之后将栈内剩余的运算符放到表达式里{if(Stack.top() != '(' && Stack.top() != ')'){all[++pos] = Stack.top();}Stack.pop();}
}bool deny(bool p) {return !p;}
bool And(bool p, bool q) {return p && q;}
bool Or(bool p, bool q) {return p || q;}
bool contain(bool p,bool q) {return !(p == true && q == false);}
bool equal(bool p,bool q) {return p == q;}bool getans(){                              //计算复合命题while(!P.empty())P.pop();int tot = 0;for(int i = 0; i <= pos; i++){bool x, y;if(all[i] >= 'a' && all[i] <= 'z')P.push(t[++tot]);else if(all[i] == '!'){x = P.top();P.pop();P.push(deny(x));}else{x = P.top();P.pop();y = P.top();P.pop();if(all[i] == '&')P.push(And(x,y));else if(all[i] == '|')P.push(Or(x,y));else if(all[i] == '-')P.push(contain(x,y));else if(all[i] == '=')P.push(equal(x,y));}}return P.top();
}void dfs(int now)                              //搜索
{if(now > cnt){for(int i = 1; i <= cnt; i++){cout << t[i] << " ";}cout << getans() << endl;return;}t[now] = 1;dfs(now+1);t[now] = 0;dfs(now+1);
}int main(){read();change();freopen("result.txt","w",stdout);          //输出到文件dfs(1);fclose(stdout);return 0;
}

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