rt。我很弱,请大佬指教。
感觉应该很好查到错误,但是就是照不出来。
感觉问题出在 t 数组上,或者是在建表达式树那块。
找出来的人直接给我的关注和我小号的关注。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
//读入 √
//化简后缀 √
//后缀转表达式树 √
//表达式树求值 √
struct node { //表达式树的一个节点
node *le, *ri;
int val;
char op; //是数字,则是 '*',否则正常存入
node(char _op) {
if(_op >= '0' && _op <= '1') {
op = '*';
val = _op - '0';
}
else op = _op;
}
};
string ori;
int n, q, cnt = 0;
int a[100007];
int t[100007]; //t[i] 记录后缀里第 i 个数字的位置
vector<char> fin;
inline void simp_suffix() {
for(int i = 0; i < ori.size(); i++) {
char ch = ori[i];
if(ch == ' ') continue;
//下面 ch 只会是变量、|、&、!
//如果是变量,则一下搜到是空格为止,并记录数字
//如果是 |、! 或者 & 直接加入
if(ch == '|' || ch == '&' || ch == '!') {
fin.push_back(ch);
continue;
}
int num = 0;
while(i < ori.size() && ((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9'))) {
if(isdigit(ch)) num = num * 10 + (ch - '0');
ch = ori[++i];
}
//cout<<num<<" "<<a[num]<<endl;
fin.push_back(a[num] + '0');
t[num] = fin.size() - 1;
}
// for(auto ch: fin)
// cout << ch;
// cout << endl;
}
inline void init() {
getline(cin, ori); //读入原来的字符串
n = read();
for(int i = 1; i <= n; i++)
a[i] = read();
//cout << ori << endl;
simp_suffix();
q = read();
}
node *root;
inline void build_tree() { //通过后缀表达式,转成表达式树
stack<node*> ds;
for(auto ch: fin) {
//处理后缀表达式
if(ch >= '0' && ch <= '1') {
ds.push(new node(ch));
continue;
}
if(ch == '!') {
node *tmp = new node(ch);
node *le = ds.top(); ds.pop();
tmp -> le = le;
ds.push(tmp);
continue;
}
node *tmp = new node(ch);
node *ri = ds.top(); ds.pop();
node *le = ds.top(); ds.pop();
tmp -> le = le;
tmp -> ri = ri;
ds.push(tmp);
}
root = ds.top();
}
inline int etree_count(node *x) {
if(x -> op == '*') return x -> val;
int l = etree_count(x -> le);
if(x -> op == '|' && x -> val == 1) return 1;
if(x -> op == '&' && x -> val == 0) return 0;
if(x -> op == '!') return !l;
int r = etree_count(x -> ri);
if(x -> op == '|') return l || r;
else return l && r;
}
inline void work() {
while(q--) {
int x = read();
a[x] = !a[x];
if(fin[t[x]] == '0') fin[t[x]] = '1';
else fin[t[x]] = '0'; //临时调换
//此时后缀表达式已经更新完成
//开始建表达式树并求值
//主要分为两步:
// * 后缀转表达式树
// * 表达式树求值
build_tree();
cout << etree_count(root) << "\n";
a[x] = !a[x]; //还原
if(fin[t[x]] == '0') fin[t[x]] = '1';
else fin[t[x]] = '0';
}
}
int main() {
init();
work();
return 0;
}