[ZOJ4021]Boolean Expression

        题目大意：给出一个布尔表达式S（只含'!','&','|','T','F','(',')'），要求加上最少的字符使表达式的值为真。（\(|S| \leq 10^5\))

        题解：原表达式为真时答案就是0了，原表达式为假时由于可以在表达式最后加上'|T'使表达式值为真，所以答案一定小于等于2,如果只加一个字符的话显然只能加'!'，所以当原表达式为假时，这道题目可以转化为是否能在某一括号或'T'、'F'前面加上一个'!'使得原表达式值为真。这样一来我们可以这么考虑：原来每一子表达式的值只有0和1（表示假和真），我们将它改成值为0,1,2,3，其中0表示假，1表示真，2表示原式为假，但可以通过加上一个'!'后变成真，3表示原式为真，但可以通过加上一个'!'后变成假。然后我们可以通过重新定义运算来计算表达式的值。这里由于表达式的值并非只和运算符左右的值有关，而是和连着的整段相同运算符所组成的表达式有关，所以当前运算符和栈顶运算符相同时不能直接弹出，要等到下一个优先级更小的运算符出现时才能开始处理。

        另外，由于'!'加在括号里面的作用不如加在括号前面，所以可以先把括号里的值先算出来，然后把整个表达式改成只有'&'和'|'的表达式，会更容易处理。（我代码里没有写）

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;

char s[maxn];
char qc[maxn];
int pri[256];
int qx[maxn];
int qcn,qxn;
int n;

int And(int x,int y) {return x&y&1;}
int Or(int x,int y) {return (x|y)&1;}

void Calc()
{
	int cnt[4];
	memset(cnt,0,sizeof(cnt));
	char ch=qc[qcn];
	cnt[qx[qxn]]=1;
	while (qcn && qc[qcn]==ch)
	{
		int x=qx[qxn],y=qx[qxn-1];
		cnt[qx[qxn-1]]++;
		qxn-=2;
		if (ch=='&') qx[++qxn]=And(x,y);
		if (ch=='|') qx[++qxn]=Or(x,y);
		qcn--;
	}
	if (ch=='&' && cnt[0]==0 && cnt[2]==1) qx[qxn]|=2;
	else if (ch=='&' && qx[qxn]==1 && cnt[3]) qx[qxn]|=2;
	else if (ch=='|' && cnt[1]==0 && cnt[2]==1) qx[qxn]|=2;
	else if (ch=='|' && qx[qxn]==0 && cnt[2]) qx[qxn]|=2;
}

int main()
{
	pri['!']=1;
	pri['&']=2;
	pri['|']=3;
	pri[')']=pri['(']=4;
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%s",s);
		n=strlen(s);
		qcn=qxn=0;
		for (int i=0;i<n;i++)
		{
			if (s[i]=='F' || s[i]=='T')
			{
				qx[++qxn]=(s[i]=='T')+2;
				while (qcn && qc[qcn]=='!') qx[qxn]^=1,qcn--;
			}
			else if (s[i]!='(')
			{
				while (qcn && pri[s[i]]>pri[qc[qcn]])
					Calc();
				qc[++qcn]=s[i];
				if (s[i]==')')
				{
					qcn-=2;
					qx[qxn]|=2;
					while (qcn && qc[qcn]=='!') qx[qxn]^=1,qcn--;
				}
			}
			else qc[++qcn]=s[i];
		}
		while (qcn) Calc();
		if (qx[1]==1 || qx[1]==3) printf("0\n");
		else if (qx[1]==2) printf("1\n");
		else printf("2\n"); 
	}
	return 0;
}