布尔表达式解题报告

Description

输入一个布尔表达式，请你输出它的真假值。 
比如：( V | V ) & F & ( F | V ) 
V表示true，F表示false，&表示与，|表示或，!表示非。 
上式的结果是F

Input

输入包含多行，每行一个布尔表达式，表达式中可以有空格，总长度不超过1000

Output

对每行输入，如果表达式为真，输出"V",否则出来"F"

Sample Input

( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))

Sample Output

F
V
V

这个题虽然看上去很简单。。但实际上并没有想象中的那么简单。

考虑用栈维护布尔值和运算符，然后！是个蛋疼的地方，前缀一目运算符与中缀二目运算符需要不同的处理方式；中缀二目运算符就是像维护一个单调栈一样搞一下就行了。但是前缀一目运算符要先存起来，而且不能向前维护单调性，因为那样的话比如!!F，向前维护单调性的话就找不到可以运算的数了。（还好就它一个，要不然更蛋疼。）

Code：

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;
bool a[1005];
int opt[1005];
int atot;
void work(int x){
	switch(x){
		case 1:
			a[atot-2]|=a[atot-1];
			--atot;
			break;
		case 2:
			a[atot-2]&=a[atot-1];
			--atot;
			break;
		case 3:a[atot-1]=!a[atot-1];
	}
}
int main(){
	freopen("bool.in","r",stdin);
	char s[1005];
	int len,i,j,tmp;
	int otot=0;
	while(gets(s)){
		len=strlen(s);
		for(i=0;i<len;++i)
			if(s[i]!=' '){
				if(s[i]=='V'||s[i]=='F')a[atot++]=s[i]=='V';
				else
					if(s[i]=='(')opt[otot++]=0;
					else 
						if(s[i]==')')
							while(otot&&opt[--otot])
								work(opt[otot]);
						else
							if(s[i]=='!')opt[otot++]=3;
							else{
								tmp=s[i]=='|'?1:2;
								while(otot&&opt[otot-1]>=tmp)work(opt[--otot]);
								opt[otot++]=tmp;
							}
				/*printf("--------:%c\n",s[i]);
				for(j=0;j<atot;++j)printf("%d ",a[j]);
				puts("");
				for(j=0;j<otot;++j)printf("%d ",opt[j]);
				puts("");*/
			}
		if(atot==0)continue;
		while(otot)work(opt[--otot]);
		if(a[--atot])puts("V");
		else puts("F");
	}
}