布尔表达式解题报告

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");
}
}