poj3295

本题虽然简单，但是利用了编译原理里面的自顶向下方法来设计语法树，递归求解。

例如：对于逻辑表达式A&B|C，得到以下输出
 A B C    A&B|C
 0 0 0    0
 0 0 1    1
 0 1 0    0
 0 1 1    1
 1 0 0    0
 1 0 1    1
 1 1 0    1
 1 1 1    1

逻辑表达式支持：常量（只有0和1两种常量）、变量（用一个大写字母表示，因此最多26个变量）、“与”运算、“或”运算、“非”运算

用算符优先文法来做语法解析。优先级比较表如下：
  | & ! ( ) #
| > < < < > <
& > > < < > <
! > > > < > <
( < < < < = <
) > > > E > <
# > > > > > =

算符优先文法解析方式：
1、定义优先级比较表。除了真正需要使用的运算符。
2、使用了一个栈，只用于存放操作数（Operand）
3、若当前优先级小于栈顶优先级，则规约；若大于，则入栈。

则不难写出以下代码：

#include <iostream>   
#include <stack>   
#include <string>   
  
using namespace std;  
  
stack <int> stk;  
  
bool isvariable(char c, int pp, int qq, int rr, int ss, int tt)  
{  
    switch (c)  
    {  
    case 'p': stk.push(pp); return true;  
    case 'q': stk.push(qq); return true;  
    case 'r': stk.push(rr); return true;  
    case 's': stk.push(ss); return true;  
    case 't': stk.push(tt); return true;  
    }  
    return false;  
}  
  
void operand(char op)  
{  
    switch (op)  
    {  
    case 'K':  
        {  
            int x = stk.top();  
            stk.pop();  
            int y = stk.top();  
            stk.pop();  
            stk.push(x && y);  
            break;  
        }  
    case 'A':  
        {  
            int x = stk.top();  
            stk.pop();  
            int y = stk.top();  
            stk.pop();  
            stk.push(x || y);  
            break;  
        }  
    case 'C':  
        {  
            int x = stk.top();  
            stk.pop();  
            int y = stk.top();  
            stk.pop();  
            stk.push((!x) || y);  
            break;  
        }  
    case 'E':  
        {  
            int x = stk.top();  
            stk.pop();  
            int y = stk.top();  
            stk.pop();  
            stk.push(x == y);  
            break;  
        }  
    case 'N':  
        {  
            int x = stk.top();  
            stk.pop();  
            stk.push(!x);  
            break;  
        }  
    }  
    return;  
}  
  
int main()  
{  
    string s;  
    while (cin >> s && s != "0")  
    {  
        bool flag = true;  
        for (int pp = 0; pp <= 1; ++pp)  
        {  
            for (int qq = 0; qq <= 1; ++qq)  
            {  
                for (int rr = 0; rr <= 1; ++rr)  
                {  
                    for (int ss = 0; ss <= 1; ++ss)  
                    {  
                        for (int tt = 0; tt <= 1; ++tt)  
                        {  
                            for (int i = s.size() - 1; i >= 0; i--)  
                            {  
                                if (!isvariable(s[i], pp, qq, rr, ss, tt))  
                                    operand(s[i]);  
                            }  
                            int ans = stk.top();  
                            stk.pop();  
                            if (!ans)  
                            {  
                                flag = false;  
                                break;  
                            }  
                        }  
                        if (!flag)  
                            break;  
                    }  
                    if (!flag)  
                        break;  
                }  
                if (!flag)  
                    break;  
            }  
            if (!flag)  
                break;  
        }  
        if (flag)  
        {  
            cout << "tautology" << endl;  
        }  
        else cout << "not" << endl;  
          
        while (!stk.empty())  
        {  
            stk.pop();  
        }  
    }  
}  

#include <iostream>
#include <stack>
#include <string>

using namespace std;

stack <int> stk;

bool isvariable(char c, int pp, int qq, int rr, int ss, int tt)
{
	switch (c)
	{
	case 'p': stk.push(pp); return true;
	case 'q': stk.push(qq); return true;
	case 'r': stk.push(rr); return true;
	case 's': stk.push(ss); return true;
	case 't': stk.push(tt); return true;
	}
	return false;
}

void operand(char op)
{
	switch (op)
	{
	case 'K':
		{
			int x = stk.top();
			stk.pop();
			int y = stk.top();
			stk.pop();
			stk.push(x && y);
			break;
		}
	case 'A':
		{
			int x = stk.top();
			stk.pop();
			int y = stk.top();
			stk.pop();
			stk.push(x || y);
			break;
		}
	case 'C':
		{
			int x = stk.top();
			stk.pop();
			int y = stk.top();
			stk.pop();
			stk.push((!x) || y);
			break;
		}
	case 'E':
		{
			int x = stk.top();
			stk.pop();
			int y = stk.top();
			stk.pop();
			stk.push(x == y);
			break;
		}
	case 'N':
		{
			int x = stk.top();
			stk.pop();
			stk.push(!x);
			break;
		}
	}
	return;
}

int main()
{
	string s;
	while (cin >> s && s != "0")
	{
		bool flag = true;
		for (int pp = 0; pp <= 1; ++pp)
		{
			for (int qq = 0; qq <= 1; ++qq)
			{
				for (int rr = 0; rr <= 1; ++rr)
				{
					for (int ss = 0; ss <= 1; ++ss)
					{
						for (int tt = 0; tt <= 1; ++tt)
						{
							for (int i = s.size() - 1; i >= 0; i--)
							{
								if (!isvariable(s[i], pp, qq, rr, ss, tt))
									operand(s[i]);
							}
							int ans = stk.top();
							stk.pop();
							if (!ans)
							{
								flag = false;
								break;
							}
						}
						if (!flag)
							break;
					}
					if (!flag)
						break;
				}
				if (!flag)
					break;
			}
			if (!flag)
				break;
		}
		if (flag)
		{
			cout << "tautology" << endl;
		}
		else cout << "not" << endl;
		
		while (!stk.empty())
		{
			stk.pop();
		}
	}
}

补充：软件开发 , C++ ,

上一个：HDU 2544 最短路
下一个：二叉树的序遍历