信息学奥赛复赛复习10-CSP-J2020-03表达式求值-栈、后缀表达式、isdigit函数、c_str函数、atoi函数、链式前向星、数据结构、深度优先搜索

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

说明/提示

该后缀表达式的中缀表达式形式为 (x1and⁡x2)or⁡x3。

对于第一次询问，将 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=11&0=0 */if(num[n1]==1) dfs(n2);if(num[n2]==1) dfs(n1);}else if(c[x]=='|'){/*第1个结点操作数是0，第2个操作数影响结果例如: 0|1=10&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;
}