#E. 真值表

    传统题 1000ms 512MiB

真值表

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一个含布尔变量的布尔表达式,请计算其真值表

布尔表达式由布尔变量、小括号与运算符组成。具体来说,表达式的结构定义如下:

  • 一个小写英文字符 a ~ z 是一个可以取 0 或 1 的布尔变量,是一个表达式
  • 如果 A 是一个表达式,则 (A) 也是表达式
  • 如果 A 是一个表达式,则 !A 也是表达式
  • 如果 AB 是表达式,则 A|BA&BA^BA=B 也是表达式

运算符 !|&^= 的真值表如下:

运算符的优先级从高到低!&|^=。例如:对于表达式 a&!b|c,计算顺序为 (a&(!b))|c。多个相同运算符则从左往右依次计算

现要求枚举表达式中出现过的每个变量的取值并计算表达式,由此得到真值表

输入格式

输入共 T+1T+1

第一行一个整数 TT,表示测试数据的组数

接下来 TT 行,每行一个字符串,表示该组数据提供的表达式

输出格式

输出共 TT

每行为一个长度为 2k2^k,仅由字符 01 组成的字符串。其中 kk 为该组数据所给表达式中不同的布尔变量数量。要求将变量按字典序从小到大排序后依次枚举取值为 01。可参考样例解释理解

样例数据

样例一

input

1
(p&q)|((q&p)=(q=!p))

output

1001

解释

  • p=0,q=0p=0, q=0 时表达式值为 11
  • p=0,q=1p=0, q=1 时表达式值为 00
  • p=1,q=0p=1, q=0 时表达式值为 00
  • p=1,q=1p=1, q=1 时表达式值为 11

依次输出得到字符串 1001

样例二

input

1
!(!!(!!a|b&c))

output

11100000

样例三

input

1
!(!!(!a|b&c))&(!(((b^c=d=e))))|(a=b)

output

11111111000000001001011011111111

样例四

input

3
(!!!!!!m^!y=!!y^r&m&r=e^!v|!(y)&(y))
!(!!!!(!((!t|!y^(y)&t&t&(y|(!w))))))
(!(!(z|r))=!r|!z)=k|k&(z)&!!r=!!!k|z

output

00110011110000111100110000111100
11111111
10011100

数据范围与约定

子任务编号 分值 特殊性质
11 2020 表达式中不含括号和 ! 运算符
22 每个表达式中只有一个变量,且只出现一次
33 表达式中不含 ! 运算符
44 4040

对于所有数据,有 1T51\le T\leq 511\le 表达式长度 1000\le 100011\le 每个表达式内本质不同的变量数量 5\le 5

本题子任务一不进行捆绑测试

[YDRB#002] 一步步脚踏实地 · 云斗九月 Bronze Round

未参加
状态
已结束
规则
IOI(严格)
题目
5
开始于
2024-9-8 9:00
结束于
2024-9-8 20:00
持续时间
4 小时
主持人
参赛人数
126