CSP2020-j2 T3表达式（expr）

本题第一难点：字符串处理
方法一：纯模拟，时间复杂度O（q*|s|）~估计分数30左右
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[1000010];
 4 char c;
 5 int len;
 6 int n, a[100010];
 7 int q, qx;
 8 int stk[1000010], t;//手写栈，t来记录栈顶下标 
 9 void cal(int f) {
10     int p=0;//p记录第几个X（数），按要求更改取反 
11     t=0;
12     for(int i=0; i<len; i++) {
13         if(s[i]=='x') {
14             p++;
15             i++;//遇到x从之后开始将数字字符转换为数字 
16             int x=0;//计算x之后的数值，并从对应数组中取值，存于x中 
17             while(s[i]!=' ') {//此处是该题中的难点 
18                 x=x*10+s[i]-'0';
19                 i++;
20             }
21             i--;//i值恢复到之前 
22             if(p==f) {//要求取反的下标 
23                 ++t;
24                 stk[t]=!a[x];
25             } else {
26                 ++t;
27                 stk[t]=a[x];
28             }
29         }
30         if(s[i]=='!') {
31             stk[t] = !stk[t];
32         }
33         if(s[i]=='&') {
34             int temp1=stk[t];//写成这样方便调试 
35             t--;
36             int temp2=stk[t];
37             stk[t] = temp1 & temp2;
38         }
39         if(s[i]=='|') {
40             int temp1=stk[t];
41             t--;
42             int temp2=stk[t];
43             stk[t] = temp1 | temp2;
44         }
45     }
46     cout<<stk[t]<<endl;
47 }
48 int main() {
49 
50     while((c=getchar())!='
')
51         s[len++]=c;
52 //    for(int i=0; i<len; i++)cout<<s[i];//测试输入代码 
53 //    cout<<endl;//测试输入代码
54     cin>>n;
55     for(int i=1; i<=n; i++)
56         cin>>a[i];
57     cin>>q;
58     while(q--) {
59         cin>>qx;
60         cal(qx);//用于传递第几个数取反
61     }
62     return 0;
63 }