首页 > 代码库 > poj 3295 Tautology
poj 3295 Tautology
题目链接：http://poj.org/problem?id=3295
思路：
判断逻辑表达式是否为永真式问题。根据该表达式的特点，逻辑词在逻辑变量前，类似于后缀表达式求值问题。
算法中使用两个栈，从表达式的后边开始处理表达式中每个字符；若为逻辑变量，使其入栈SR，否则从栈SR中弹出两个逻辑变量，进行运算后的结果再入栈SR；直到处理完表达式所有的字符。
注：使用栈可以很好的处理广义表类似的序列
代码：
#include <iostream>#include <stack>using namespace std;const int MAX_N = 1000 + 10;char A[MAX_N];int p, q, r, s, t, ans;int Match( char x ){ int value = http://www.mamicode.com/0; switch(x) { case ‘0‘:value = http://www.mamicode.com/0; break; case ‘1‘:value = http://www.mamicode.com/1; break; case ‘p‘:value = http://www.mamicode.com/p;break; case ‘q‘:value = http://www.mamicode.com/q;break; case ‘r‘:value = http://www.mamicode.com/r;break; case ‘s‘:value = http://www.mamicode.com/s;break; case ‘t‘:value = http://www.mamicode.com/t;break; default: value =http://www.mamicode.com/ p; } return value;}int Calc( char a, char b, char T ){ int x, y, ans; x = Match( a ); y = Match( b ); switch( T ) { case ‘K‘:ans = x && y;break; case ‘A‘:ans = x||y;break; case ‘N‘:ans = !x;break; case ‘C‘:ans = (!x)||y;break; case ‘E‘:ans = (x == y);break; } return ans;}int WWF( ){ int Rusult = 0; int Len = strlen( A ); stack<char>SL, SR; for ( p = 0; p <= 1; ++p ) for( q = 0; q <= 1; ++q ) for( r = 0; r <= 1; ++r ) for( s = 0; s <=1; ++s ) for( t = 0; t <= 1; ++t ){ for ( int i = 0; i < Len; ++i ) SL.push( A[i] ); while ( !SL.empty() ) { char x, y, T; int flag = 0; T = SL.top();SL.pop(); switch(T) { case ‘p‘: case ‘q‘: case ‘r‘: case ‘s‘: case ‘t‘: SR.push(T);flag = 1;break; } if ( flag == 1 ) continue; else if ( T == ‘N‘ ) { x = SR.top();SR.pop(); ans = Calc( x, x, T ); } else { x = SR.top();SR.pop(); y = SR.top();SR.pop(); ans = Calc( x, y, T ); } SR.push( ans + ‘0‘ ); } if ( ans == 0 ) return 0; } return 1;}int main(){ int flag = 0; while ( scanf( "%s", A ) != EOF ) { if ( A[0] == ‘0‘ ) break; flag = WWF(); if ( flag == 0 ) printf( "not\n" ); else printf( "tautology\n" ); } return 0;}
poj 3295 Tautology
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。