SP9446 SHORTCIR - Shortest Circuit Evaluation

布尔表达式的短路求值是一种优化技术：当某些布尔运算符的第一个参数已经足以确定整个表达式的值时，我们可以不计算第二个参数。许多编程语言都使用这种方法来加速布尔表达式的求值。 例如，对于表达式「A and B」，如果 A 为假，整个表达式必然为假，因此无需计算 B。而对于「A or B」，如果 A 为真，结果自然为真，不需再看 B 的情况。由于这些布尔运算是可交换的，我们可以先尝试判断 B 的值，如果 B 的结果能确定整个表达式的值，则不必再检查 A。进一步地，如果有多个或连接的表达式「A1 or A2 or ... or An」，我们能够按任意顺序评估这些变量，发现一个为真时即认定整个表达式为真。同理，对于多个与连接的表达式可以照此处理。 考虑一个复杂的布尔表达式，我们需固定一个变量的评估顺序，按此顺序计算。过程中，我们会跳过那些无法提供新信息的变量。例如，有表达式「A and B or C」，且评估顺序为 B, A, C。首先计算 B，如果 B 为假，则不用计算 A，直接去看 C。但若 B 为真，则需要计算 A。如果 A 也为真，表达式肯定为真，无须再看 C；否则，需要通过 C 的值来决定表达式结果。现在你的任务是：给定一个复杂的布尔表达式，包含 and、or、not 运算，以及每个变量为真的概率，找出一种评估顺序，使得在短路求值过程中期望的计算次数最少。

第一行输入整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例的第一行是一个由 and、or、not 运算符、括号和变量名组成的有效布尔表达式。每个表达式中的变量名都不相同。之后对于每个变量，将有一行形式为 $s\ p$，表示变量名 $s$ 及其为真的概率 $p$。所有变量名均为小写拉丁字母。

对于每个测试用例，输出在最优评估顺序下，短路求值过程中期望的计算次数，结果保留 6 位小数。 **本翻译由 AI 自动生成**