代码有比较详细的注释。

#include <iostream>
#include <cstdio>
#include <cstring> 

using namespace std;

struct node
{
	char opt;         // 操作符 
	bool useful,nt;   // useful 表示这个节点有没有用，nt 表示要不要取反 
	int num;
	node *lson,*rson; // 左右儿子 
}*root,*xs[100005],*st[1000005]; // xs 存变量的地址，st 是栈 

int n,nums[1000005]; // nums 是变量的初值 
string temp;

int count(node *now,bool useful)
{
	now->useful=useful;
	if(now->opt=='x')
	{
		// 如果遇到了变量，直接返回值 
		return now->nt?(!nums[now->num]):nums[now->num];
	}
	if(now->opt=='|')
	{
		// 如果是 | 
		int l,r;
		if(useful)
		{
			// 如果这棵树有用 
			l=count(now->lson,useful),r; // 先计算左子树的值 
			if(l==1)
			{
				// 左子树的值为 1，右子树是什么值都没影响 => 右子树没用 
				r=count(now->rson,false);
			}
			else
			{
				// 否则右子树有用 
				r=count(now->rson,useful);
			}
			if(r==1)
			{
				// 右子树的值为 1，左子树是什么值都没影响 => 左子树没用
				count(now->lson,false);
			}
		}
		else
		{
			// 这棵树没用，子树也没用了 
			l=count(now->lson,false),r=count(now->rson,false);
		}
		return now->nt?(!(l|r)):(l|r);
	}
	if(now->opt=='&')
	{
		// 如果是 & 
		int l,r;
		if(useful)
		{
			// 如果这棵树有用 
			l=count(now->lson,useful),r; // 先计算左子树的值 
			if(l==0)
			{
				// 左子树的值为 0，右子树是什么值都没影响 => 右子树没用 
				r=count(now->rson,false);
			}
			else
			{
				// 否则右子树有用 
				r=count(now->rson,useful);
			}
			if(r==0)
			{
				// 右子树的值为 0，左子树是什么值都没影响 => 左子树没用
				count(now->lson,false);
			}
		}
		else
		{
			// 这棵树没用，子树也没用了 
			l=count(now->lson,false),r=count(now->rson,false);
		}
		return now->nt?(!(l&r)):(l&r);
	}
}

int main()
{
	getline(cin,temp);   // 整行读入 
	int len=temp.size(); // 字符串长度 
	// 读入变量初值 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&nums[i]);
	}
	int t=0; // 栈顶 
	for(int i=0;i<len;i++)
	{
		node *p=new node;
		if(temp[i]=='x') // 是变量 
		{
			int num=0; // 变量编号 
			// 获取变量编号 
			i++;
			while(i<=len&&temp[i]>='0'&&temp[i]<='9')
			{
				num=num*10+temp[i]-'0';
				i++;
			}
			i--;
			// 赋值，入栈 
			p->opt='x';
			p->num=num;
			p->lson=NULL;
			p->rson=NULL;
			p->nt=false;
			xs[num]=p; 
			st[++t]=p;
		}
		else if(temp[i]=='|'||temp[i]=='&')
		{
			// 是 | 或者 & 操作符 
			// 取出栈顶的两个元素 
			node *f=st[t--];
			node *l=st[t--];
			// 赋值，入栈 
			p->opt=temp[i];
			p->lson=f;
			p->rson=l;
			p->nt=false;
			st[++t]=p;
		}
		else if(temp[i]=='!')
		{
			// 是 ！ 操作符 
			st[t]->nt=true; // 栈顶元素需要取反 
		}
	}
	root=st[1]; // 根 
	int ans=count(root,true); // 计算初值+标记有没有用 
	scanf("%d",&t);           // t 表示询问个数 
	while(t--)
	{
		int id;
		scanf("%d",&id); // 取反的变量编号 
		if(xs[id]->useful)
		{
			printf("%d\n",!ans); // 有用，答案取反 
		}
		else
		{
			printf("%d\n",ans); // 没用，答案不变 
		}
	}
	return 0;
}