CSP 2020 第三题：表达式
牛客网题目
题目内容：
示例1
输入
x1 x2 & x3 |
3
1 0 1
3
1
2
3
输出
1
1
0
题意：
给出后续表达式，需要计算这个表达式的值，并让某几个变量值取反，再输出新的表达式的值（变量改变均为临时的）
知识点考察：
后缀表达式-栈、树（结构体）、递归
思路：
- 首先要计算表达式，后缀表达式：左右根，数据放在栈里面，当遇到运算符（根）就弹出并计算值，然后接着入栈、出栈计算即可。如果表达式和数值不变，压栈和出栈的过程就能计算出结果。
- 但是本题需要更改变量值，所以后缀表达式的数据关系还需要放在树里面，方便后面的查询或者操作。因此建立一个结构体数组，每个结构体储存左孩子和右孩子，储存变量序号，再设置一维数组，序号做下标，储存变量的值和符号的值（直接设为2或者3就行）。当遇到运算符时，保存压在栈中数据分别储存为右节点和左节点，根节点就储存运算符，运算符为了方便储存为数字，可以直接约定一个数字储存，为了避免和前面的孩子节点序号的冲突，直接将约定数据设置得比变量序号最大值大就行，即结构体的根节点序号是从MAX_N+1开始。
- 按照理由，当变量值变化时，直接再次计算：利用递归，从根节点开始搜索，找到左右孩子然后返回计算的即通过（注意每次改变都是临时改变，）。but ，保守来看：数据长度 105 * 改变次数 106=1011，会超时。由于数据都是0 1，结合”& | “的性质可以想到，”& “的一个孩子结点为0，则当前计算为0（另一个节点为无效节点）；同理” | “中一个节点为1，则结果为1（另一个节点为无效节点）。因此只要是如果改变的是有效节点，结果直接取反就行（结果都是0 1）。所以可以设置一个数组mark[]，记录该节点是否是无效节点，如果是，直接输出之前的结果，否则直接取反。这个想清楚了可以拿到至少30%的分。
- 接下来时处理取反操作，取反可以想到两个，一个是变量取反，一个是表达式结果取反——（！a&b ） = ！a | ！b。表达式取反如果挨个用if去处理，也可以直接用异或运算，即直接将根节点和1异或处理、同时左右节点分别和1异或处理。
异或逻辑的关系是：当AB不同时，输出1；当AB相同时，输出0。"⊕"是异或运算符号,计算机中“^”是异或数学运算符号，满足交换律和结合律
2^1 = 3 , 3^1=2 ,1 ^1=0 ,0^1
数据约束：
- s长度最大为 1106 所以长度最大为100000 ，但是实际储存数据时，运算符是以变量序号后面的数来存，必须大一点，>=10000002
- 结构体数组的长度也是，结构体下标是以运算符的数字来储存，也必须保证开到100000*2，否则会有溢出，出现问题
参考代码：
#include<bits/stdc++.h>
#include<stack>
#define MAX_N 1000005
using namespace std;
stack <int> st;//定义数据类型char的栈处理后缀表达式
struct Node{int left;int right;
}tr[MAX_N*2];//节点树
int a[MAX_N*2],m[MAX_N*2],f[MAX_N*2]; //存变量值和标记是否有影响的点以及是否是需要取反的点 //通过从根节点开始 递归计算出左右子树的值 int val(int k); //如果已经被标记 直接标记其孩子 void mark(int k);
int main(){int yc=MAX_N+1; //给运算符的地址编号 int n=0, q,ans=0; //存变量个数、需要改变的数据个数 、存储结果 string s0;//由于变量是x+数字 所以需要根据空格来分隔 判断出每个数据 cin>>s0;//如果一次获取一排就要单独处理 while(s0[0]>='9'||s0[0]<='0'){ //只要不是数组开头说明还是在输入表达式 int k=0; //获取变量的数字 int len = s0.size() ;if(s0[0]=='x'){ //变量需要转化成数字处理一下（数位合并） for(int i=1;i<len;i++){k=k*10+s0[i]-'0';} st.push(k); //把当前变量的名放到栈里面 }else if(s0[0]=='&'){//取出操作数 放到数里面找到左右孩子int rt = st.top() ; st.pop();int lt = st.top();st.pop();st.push(yc) ;//将运算符地址压入栈 tr[yc].left = lt; //出栈处理后放到数据树里面，记录当前运算符的左孩子和右孩子 tr[yc].right = rt;a[yc] = 2 ;//记录当前运算符的值，随便赋即可，a前面都是变量的数据 yc++;//后面的运算符将往后算 }else if(s0[0]=='|'){int rt = st.top() ; st.pop();int lt = st.top(); st.pop();st.push(yc) ;tr[yc].left = lt; tr[yc].right = rt;a[yc] = 3 ;yc++;}else if(s0[0]=='!'){//对前面的得到的这个数取反f[st.top()]=!f[st.top()];} cin>>s0; //继续输入表达式 }//以上的得到一个string需要转化成数字for(int i=0;i<s0.size();i++){n=n*10+s0[i]-'0';} for(int i=1;i<=n;i++){ //从1开始 因为 变量是从1开始的 cin>>a[i] ;} yc--;ans = val(yc);// 计算结果mark(yc);cin>>q;int l;
// cout<<"--------更换后-------"; for (int i=1;i<=q;i++){cin>>l;if(m[l]) cout<<ans<<endl; //结果不受影响(无效点） else {cout<<!ans<<endl; }} return 0;}
int val(int k){ //如果是0 1取反结果就是异或结果，如果 2 3取反 则刚好为3 2和运算取反的结果刚好也一致，同时左右孩子也取反就行 //但是！一次递归只需要处理一个值，所以左右孩子异或取反数组就行，不能直接把左右孩子都处理了 a[k] ^= f[k];f[tr[k].left] ^= f[k]; f[tr[k].right] ^= f[k];int p=0;if(k<=MAX_N) {p=a[k];return p;} //普通节点 int lt = val(tr[k].left);int rt = val(tr[k].right);if(a[k]==2){ //&运算一边为0都为0 if(lt == 0 ) m[tr[k].right]=1;if(rt == 0) m[tr[k].left]=1;p=lt&rt;}else if(a[k]==3){ //|运算一边1都为1 if(lt == 1 ) m[tr[k].right]=1;if(rt == 1) m[tr[k].left]=1;p=lt|rt;
// cout<<"a[k] 3: "<< "左："<<a[lt]endl;}return p;}
void mark(int k){if(k>MAX_N) {if(m[k]){m[tr[k].left] = 1;m[tr[k].right] = 1;}if((k-1)>MAX_N) mark(--k);//直接访问下一个符号节点 }}