poj3295解题报告（构造、算术表达式运算）

 

POJ 3952，题目链接http://poj.org/problem?id=3295

题意：

输入由p、q、r、s、t、K、A、N、C、E共10个字母组成的逻辑表达式，

其中p、q、r、s、t的值为1（true）或0（false），即逻辑变量；

K、A、N、C、E为逻辑运算符，

K --> and:  x && y

A --> or:  x || y

N --> not :  !x

C --> implies :  (!x)||y

E --> equals :  x==y

输入格式保证是合法的，问这个逻辑表达式是否为永真式。

思路：

1. 从输入字符串末尾向前读取字符，构造一个栈，遇到pqrst则入栈，遇到N则取出栈顶一个值计算后入栈，遇到KACE则取栈顶两个值计算后入栈。最后栈内将只剩一个值，即该表达式的值。（与用栈计算算术表达式的方式一样）

2. 一个5个逻辑变量，每种情况都要考虑，那么一共2^5（0x1f）种情况。

代码：

//560K	0MS

#include <cstdio>
#include <cstring>
#include <stack>
using std::stack;

//K, A, N, C, E //逻辑符号
//p, q, r, s, t //bool值
char buf[101];
stack<bool> s_stack;
bool data[5]={false};
bool WFF(char* str, int val)
{
	//init p q r s t
	for (int i=0; i<5; ++i){
		data[i] = (1<<i) & val;
	}

	while (! s_stack.empty()) s_stack.pop();
	int strLen = strlen(str);
	bool a,b;
	while (--strLen >= 0)
	{
		switch (buf[strLen])
		{
		case 'p':
			s_stack.push(data[0]);
			break;
		case 'q':
			s_stack.push(data[1]);
			break;
		case 'r':
			s_stack.push(data[2]);
			break;
		case 's':
			s_stack.push(data[3]);
			break;
		case 't':
			s_stack.push(data[4]);
			break;
		case 'K':
			a=s_stack.top(); s_stack.pop();
			b=s_stack.top(); s_stack.pop();
			s_stack.push(a && b);
			break;
		case 'A':
			a=s_stack.top(); s_stack.pop();
			b=s_stack.top(); s_stack.pop();
			s_stack.push(a || b);
			break;
		case 'N':
			a=s_stack.top(); s_stack.pop();
			s_stack.push(!a);
			break;
		case 'C':
			a=s_stack.top(); s_stack.pop();
			b=s_stack.top(); s_stack.pop();
			s_stack.push(!a || b);
			break;
		case 'E':
			a=s_stack.top(); s_stack.pop();
			b=s_stack.top(); s_stack.pop();
			s_stack.push(a == b);
			break;
		default:
			break;
		}
	}
	return s_stack.top();
}

int main()
{
	while (true)
	{
		memset(buf, 0, sizeof(char)*101);
		scanf("%s", buf);
		if (strcmp(buf, "0") == 0) break;

		bool tautology = true;
		for (int val=0; val<=0x1f; ++val)
		{
			if (! WFF(buf, val)){
				tautology = false;
				break;
			}
		}

		if (tautology){
			printf("tautology
");
		}else {
			printf("not
");
		}
	}

	return 0;
}