当前位置:首页 > 数据结构 > 二叉树 > 正文
洛谷P7073表达式(CSPJ2020)
100+

题目大意:一个二进制数的位运算后缀表达式,对于每个原来的数据,取反后对结果是否造成影响?

题目描述

小 C 热衷于学习数理逻辑。有一天,他发现了一种特别的逻辑表达式。在这种逻辑表达式中,所有操作数都是变量,且它们的取值只能为 ,运算从左往右进行。如果表达式中有括号,则先计算括号内的子表达式的值。特别的,这种表达式有且仅有以下几种运算:

  1. 与运算:a & b。当且仅当 的值都为 时,该表达式的值为 。其余情况该表达式的值为
  2. 或运算:a | b。当且仅当 的值都为 时,该表达式的值为 。其余情况该表达式的值为
  3. 取反运算:!a。当且仅当 的值为 时,该表达式的值为 。其余情况该表达式的值为

小 C 想知道,给定一个逻辑表达式和其中每一个操作数的初始取值后,再取反某一个操作数的值时,原表达式的值为多少。

为了化简对表达式的处理,我们有如下约定:

表达式将采用后缀表达式的方式输入。

后缀表达式的定义如下:

  1. 如果 是一个操作数,则 的后缀表达式是它本身。
  2. 如果 形式的表达式,其中 是任何二元操作符,且优先级不高于 中括号外的操作符,则 的后缀式为 ,其中 分别为 的后缀式。
  3. 如果 形式的表达式,则 的后缀式就是 的后缀式。

同时为了方便,输入中:

  1. 与运算符(&)、或运算符(|)、取反运算符(!)的左右均有一个空格,但表达式末尾没有空格
  2. 操作数由小写字母 与一个正整数拼接而成,正整数表示这个变量的下标。例如:x10,表示下标为 的变量 。数据保证每个变量在表达式中出现恰好一次

输入格式

第一行包含一个字符串 ,表示上文描述的表达式。
第二行包含一个正整数 ,表示表达式中变量的数量。表达式中变量的下标为
第三行包含 个整数,第 个整数表示变量 的初值。
第四行包含一个正整数 ,表示询问的个数。
接下来 行,每行一个正整数,表示需要取反的变量的下标。注意,每一个询问的修改都是临时的,即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。变量的初值为

输出格式

输出一共有 行,每行一个 ,表示该询问下表达式的值。

输入输出样例

输入 #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

说明/提示

样例 1 解释

该后缀表达式的中缀表达式形式为

  • 对于第一次询问,将 的值取反。此时,三个操作数对应的赋值依次为 。原表达式的值为
  • 对于第二次询问,将 的值取反。此时,三个操作数对应的赋值依次为 。原表达式的值为
  • 对于第三次询问,将 的值取反。此时,三个操作数对应的赋值依次为 。原表达式的值为

样例 2 解释

该表达式的中缀表达式形式为

数据规模与约定

  • 对于 的数据,表达式中有且仅有与运算(&)或者或运算(|)。
  • 对于另外 的数据,
  • 对于另外 的数据,变量的初值全为 或全为
  • 对于 的数据,

其中, 表示字符串 的长度。

解题思路

首先是读入:第一行,结束标志是换行符,每次读入一个字符串和一个字符,如果字符是换行,结束第一行输入。对于字符串,看首位是x还是运算符,运算符用负数标记;参数x则从字符串第一位继续读入数字。

其次是位运算特点:因为操作数只有0和1,所以结果只有0和1,运算法则可以枚举。如果或运算结果是1,那么两个操作数肯定有一个1;你要让他变成0,操作数只能是一个1和一个0,你只能将他们都变成0(两个1,其中一个变0,或的结果还是1)。与、非运算同理。

解决办法:

1、先依次计算每个运算符的结果,!运算符只有一个操作数,&和|有两个操作数。第一个操作数肯定在运算符的左边(可以是数字也可以是运算符),另一个操作数,在第一个操作数的左边,简单链表链起来即可。

2、强制最终结果发送改变,依次推出两个操作数必须做出的改变,如果最终数据被修改了,那么该数据的修改会造成最终结果的改变,否则不改变。

程序实现

更多
洛谷P7073表达式(CSPJ2020):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter