poj2106——Boolean Expressions

题意：求表达式运算

思路：同数字表达式运算一样，先转后缀，再求值。

注意点：1，'('在进栈时，优先级最高，出栈时相反；

2，对于'!'，单目表达式的计算，在转后缀的时候，需将数值进栈，再将其压入后缀表达式中；

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int   len =120; 
char infix[len],suffix[len];
void infixtosuffix()
{
	int top=-1,i=0,j=0;
	char ch=infix[0],stk[len];
	while(ch!='\0')
	{
		if(ch==' ')
		{}
		else if(ch=='(')
		{
			top++;stk[top]=ch;
		}
		else if(ch==')')
		{
			while(stk[top]!='(')
			{
				suffix[j++]=stk[top];top--;
			}
			top--;
		}
		else if(ch=='!')
		{
			top++;stk[top]=ch;
		}
		else if(ch=='&')
		{
			while(stk[top]=='&'||stk[top]=='!')
			{
				suffix[j++]=stk[top];top--;
			}
			top++;stk[top]=ch;
		}
		else if(ch=='|')
		{
			while(top!=-1&&stk[top]!='(')
			{
				suffix[j++]=stk[top];top--;
			}
			top++;stk[top]=ch;
		}
		else
		{
			suffix[j++]=ch;
			while(top!=-1&&stk[top]=='!')
			{
				suffix[j++]=stk[top];top--;
			}
		}
		ch=infix[++i];
	}
	while(top!=-1)
	{
		suffix[j++]=stk[top];top--;
	}
	suffix[j++]='\0';
}
void pri_result()
{
	int i=0,top=-1;
	char ch=suffix[i];
	bool result[len];
	while(ch!='\0')
	{
		if(ch=='F')
		{
			top++;result[top]=false;
		}
		else if(ch=='V')
		{
			top++;result[top]=true;
		}
		else if(ch=='!')
			result[top]=!result[top];
		else if(ch=='|')
		{
			result[top-1]|=result[top];
			top--;
		}
		else if(ch=='&')
		{
			result[top-1]&=result[top];
			top--;
		}
		ch=suffix[++i];
	}
	if(result[top]==true)
		printf("V\n");
	else printf("F\n");
}
int main()
{
	int i=1;
	while(cin.getline(infix,len))
	{
		infixtosuffix();
		printf("Expression %d: ",i++);
		pri_result();
	}
	return 0;
}