PDF文档公众号回复关键字:20241003
1 P7073 [CSP-J2020] 表达式
[题目描述]
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 0 或 1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算
与运算：a & b。当且仅当 a和 b 的值都为 1 时，该表达式的值为 1。其余情况该表达式的值为 0
或运算：a | b。当且仅当 a 和 b的值都为 0 时，该表达式的值为 0。其余情况该表达式的值为 1
取反运算：!a。当且仅当 a 的值为 0 时，该表达式的值为 1。其余情况该表达式的值为 0
小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少
[输入格式]
第一行包含一个字符串 s，表示上文描述的表达式。
第二行包含一个正整数 n，表示表达式中变量的数量。表达式中变量的下标为 1,2,⋯ ,n
第三行包含 n 个整数，第 i个整数表示变量 xi 的初值。
第四行包含一个正整数 q，表示询问的个数。
接下来 q 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。变量的初值为 0 或 1
[输出格式]
输出一共有 q 行，每行一个 0 或 1，表示该询问下表达式的值
[输入输出样例]
输入 #1
x1 x2 & x3 |
3
1 0 1
3
1
2
3
输出 #1
1
1
0
输入 #2
x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5
输出 #2
0
1
1
说明/提示
该后缀表达式的中缀表达式形式为 (x1andx2)orx3。
对于第一次询问，将 x1 的值取反。此时，三个操作数对应的赋值依次为 0，0，1。原表达式的值为 (0&0)∣1=1
对于第二次询问，将 x2 的值取反。此时，三个操作数对应的赋值依次为 1，1，1。原表达式的值为 (1&1)∣1=1
对于第三次询问，将 x3 的值取反。此时，三个操作数对应的赋值依次为 1，0，0。原表达式的值为 (1&0)∣0=0
2 相关知识点
1) isdigit函数
在C语言中，isdigit()函数是用来检查一个字符是否为数字字符（0-9）的
#include <stdio.h>
#include <ctype.h>
int main() {
char ch;
printf("请输入一个字符：");
scanf("%c", &ch);
if (isdigit(ch)) {
printf("%c 是一个数字字符。\n", ch);
} else {
printf("%c 不是一个数字字符。\n", ch);
}
return 0;
}
/*
输入
请输入一个字符：4
输出
4 是一个数字字符。
输入
请输入一个字符：r
输出
r 不是一个数字字符。
*/
2) c_str函数
c_str() 是 C++ 中的一个成员函数，用于将 std::string 对象转换为 C 风格的字符串（即以 null 结尾的字符数组）
#include <iostream>
#include <string>
using namespace std;
int main() {
string str = "Hello, world!";
const char* c_str = str.c_str();
cout << "C-style string: " << c_str << endl;
return 0;
}
3) atoi函数
atoi() 是 C 语言中的一个标准库函数，用于将字符串转换为整数
#include <stdio.h>
#include <stdlib.h>
int main() {
char str[] = "12345";
int num = atoi(str);
printf("转换后的整数为：%d\n", num);
return 0;
}
3 思路分析
1 使用栈计算后缀表达式的值，遇到操作数存入栈中，遇到操作符从栈中取出计算
2 构建二叉树
遇到操作符时，从栈中取出对应操作数，建立操作符和操作数的边
3 通过dfs逐一判断每个操作数变化对结果是否有影响
如果是非操作符(!) ,影响前面1个操作符，且此操作符变化对结果一定有影响
如果是与操作符(&),如果1个操作数为1，另外1个操作符变化对结果有影响
如果是或操作符(|),如果1个操作费为0，另外1个操作符变化对结果有影响
示例
x1 x2 & x3 |
3
1 0 1
x1和x2的操作符为&
x1为1时，x2为0时，结果为0
x1为1时，x2为1时，结果为1
因此x2变化对结果有影响，x1变化对结果无影响
&这个分支计算结果和x3的操作符为|
x3为1时，&这个分支对结果无影响
示例程序
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;//表达式最大长度
int num[N];//存储每个节点的值
char c[N];//存储运算符
int m;//表示c数组的长度
bool f[N];//存储每个节点的值修改后对表达式的值是否有影响
struct node{
/*
to 边去向的结点
next 下一条边，连接以1条边为起点的所有的边
*/
int to,next;
}a[N];
/*
head 的下标为起点
head的值为以head下标为起点的最后一条边
k存储a数组的长度
*/
int head[N],k=0;
stack<int> st;//栈 存储后缀表达式的操作数
int n;//n个操作数
string s;//读入表达式
/*
链式前向星建边
u为起点 v为终点
*/
void add(int u,int v){
k++;//每条边存入a数组 k为下标
a[k].to=v;//终点
a[k].next=head[u];//下一个结点指向u为起点的上一条边
head[u]=k;//u为起点的边指向本次新增的边
}
/*
深搜计算哪些结点的值修改后会影响结果
从根遍历 x开始
深度优先搜索二叉树，每次只改变1位
把修改可能影响结果的位都做标识
!对应操作数一定会影响
& 如果1个操作数是1，另外1个对结果会产生影响
| 如果1个操作数是0，另外1个对结果会产生影响
*/
void dfs(int x){
f[x]=true;//只会深搜值取反后会影响结果的节点
if(x<=n) return;//遇到叶子搜索结束
/*
如果是！,head[x]找出x的下标
a[head[x]] 找出x对应边
a[head[x]].to,找出x对应边的终点
*/
if(c[x]=='!') dfs(a[head[x]].to);
else{//& | 拿到2个子结点的编号
// 找出x对应边的终点
int n1 = a[head[x]].to;//x连接第1个结点
/*
存图使用链式前向星，x连接的结点通过链表连在一起
a[head[x]]表示x指向的第1条边
a[head[x]].next表示x指向下1条边起点
a[a[head[x]].next]表示x指向下1条边
a[a[head[x]].next].to表示x指向下1条边终点
*/
int n2=a[a[head[x]].next].to;//x连接第2个结点
if(c[x]=='&'){//如果x对应操作符是&
/*
第1个结点操作数是1，第2个操作数影响结果
例如:
1&1=1
1&0=0
*/
if(num[n1]==1) dfs(n2);
if(num[n2]==1) dfs(n1);
}else if(c[x]=='|'){
/*
第1个结点操作数是0，第2个操作数影响结果
例如:
0|1=1
0&0=0
*/
if(num[n1]==0) dfs(n2);
if(num[n2]==0) dfs(n1);
}
}
}
int main()
{
getline(cin,s);//读入表达式
scanf("%d",&n);//输入n个运算数的值
for(int i=1;i<=n;i++){//逐一读入运算数
scanf("%d",&num[i]);
}
string w="";//存储连续的数字
int x,y;//x第1个操作数 y第2个操作数
m=n;//c数组从n+1开始存储运算符
for(int i=0;i<s.size();i++){
//采用连续性元素统计的思想，统计连续的数字字符为运算数的下标
if(isdigit(s[i])){
w = w +s[i];
//如果连续数字结束了
if(i==s.size()-1 || !isdigit(s[i+1])){
//运算数入栈
st.push(atoi(w.c_str()));
w= "";
}
}else if(s[i]=='!'){
m++;
c[m]=s[i];//将运算符存入c数组
//取1个栈顶元素计算，并将结果入栈
x = st.top();
st.pop();
num[m]=!num[x];
st.push(m);
//建树
add(m,x);
}else if(s[i]=='&' || s[i]=='|'){
//将运算符存入c数组
m++;
c[m]=s[i];
//取2个栈顶元素计算，并将结果入栈
x = st.top();
st.pop();
y = st.top();
st.pop();
if(s[i]=='&') num[m]=num[x] & num[y];
else if(s[i]=='|') num[m]=num[x] | num[y];
st.push(m);
//建树 建操作符到2个操作数的2条边
add(m,x);
add(m,y);
}
}
int r=st.top();//根结点存储了表达式计算结果下标
int ans = num[r];//num数组找到表达式下标的值
//深搜计算那些结点的值发生修改会影响结果，存储f数组
dfs(r);
int q;
cin>>q;//输入q次询问
while(q--){//循环每一次询问
scanf("%d",&x);//读入每次取反的下标
//如果本次改变对结果有影响取反
if(f[x]==true) printf("%d\n",!ans);
else printf("%d\n",ans);//否则结果不变
}
return 0;
}