CF913E Logical Expression
题目描述
给定一个由其真值表定义的三变量布尔函数。你需要找到一个等价于该函数的最短表达式。表达式可以包含以下内容：
- 与运算符号（'&'，ASCII 码 38）
- 或运算符号（'|'，ASCII 码 124）
- 非运算符号（'!'，ASCII 码 33）
- 变量 x、y 和 z（ASCII 码 120-122）
- 括号（'('，ASCII 码 40，和 ')'，ASCII 码 41）
如果存在长度最短的多个表达式，你应当输出字典序最小的那一个。
各运算符遵循标准优先级。NOT 优先级最高，其次是 AND，最后是 OR。表达式需符合如下文法：
E ::= E '|' T | T
T ::= T '&' F | F
F ::= '!' F | '(' E ')' | 'x' | 'y' | 'z'
输入格式
第一行包含一个整数 $n$，表示输入中给定的函数个数（$1 \leq n \leq 10000$）。
接下来 $n$ 行，每行描述一个函数，第 $i$ 行包含一个长度为 $8$ 的字符串，由数字 $0$ 和 $1$ 组成，表示第 $i$ 个函数的真值表。当 $0 \leq j < 8$ 时，第 $j$ 位表示 $f(x, y, z)$ 在输入 $x, y, z$ 分别取 $j$ 的二进制形式对应值下的函数值。
输出格式
输出 $n$ 行，第 $i$ 行输出一个长度最短且符合语法要求的等价布尔表达式。如果有多个，输出其中字典序最小的。表达式中不得含有空格。
说明/提示
第二个函数的真值表如下：
由 ChatGPT 5 翻译