首页 > 代码库 > poj 3295 Tautology
poj 3295 Tautology
这题属于构造题，有两点需要想到：
1、所谓永真式就是说题设中所给的五个逻辑变量无论如何取值，最终的运算结果总是为真，这里就需要枚举五个逻辑变量的取值情形。很容易想到共有32种情况：
也就是说，对于每个字符串，如果这32种情况下的运算结果都是真的话， 那它就是永真式。1~32， 用按位与的办法，可以逐次枚举这32中情况。
2、运算顺序：可以这样理解题目中的字符串结构，它就像一颗树，所以叶子节点做逻辑运算之后逐次汇聚到根节点得到最后的结果。于是想到从尾部开始（也就是从叶节点向上）。
如果遇到逻辑变量，压栈；如果遇到二元逻辑运算，弹出两个元素，做二元运算，将结果压栈，如果遇到一元逻辑运算，弹出一个元素，做一元运算，将结果压栈。最后栈中必然只有一个元素。
它为真，说明表达式为真，否则表达式为假：
#include<iostream>#include<stack>#include<string>using namespace std;int main(){#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin);#endif char s[110]; while (scanf("%s", s) != EOF){ //while (getchar() != ‘\n‘); if (s[0] == ‘0‘) break; int len = strlen(s); bool isTaut = true; for (int i = 0; i < 32; i++){ stack<bool> st; for (int j = len - 1; j >= 0; j--){ if (s[j] == ‘K‘ || s[j] == ‘A‘ || s[j] == ‘N‘ || s[j] == ‘C‘ || s[j] == ‘E‘){ if (s[j] == ‘N‘){ bool w = st.top(); st.pop(); st.push(!w); } else { bool w = st.top(); st.pop(); bool x = st.top(); st.pop(); switch (s[j]){ case ‘K‘: st.push(w && x); break; case ‘A‘: st.push(w || x); break; case ‘C‘: st.push(!(w && !x)); break; case ‘E‘: st.push(w == x); break; } } } else { st.push(i & (1 << (s[j] - ‘p‘))); } } if (!st.top()){ printf("not\n"); isTaut = false; break; } st.pop(); } if (isTaut){ printf("tautology\n"); } } return 0;}
poj 3295 Tautology
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。