algorithm - 短路前缀布尔表达式

Question

我有一堆用前缀表示法（也称为波兰表示法）编写的布尔表达式。这种格式的嵌套表达式很容易计算（参见维基百科文章中的算法）。

但是，Wikipedia 页面上给出的算法不会进行短路（当它评估 时and f() g()，它不会跳过g()iff()为 false 的评估）。有没有办法修改算法以包括短路？

Answer 1

我最近需要这样做，并想出了一个似乎可行的算法：

1. 使用调车场解析表达式，生成后缀术语系列。

2. 找到每个术语的父运算符并存储偏移量。

   for term in terms:
       count = 0
       for next in remaining terms:
           if next type is function:
               count = count - (argument count - 1)
           else if next type is operator:
               count = count - 1
           else:
               count = count + 1
           if count is 0:
               next is term's parent
               offset = next - term
   

3. 评估通常的方法并在每次操作后检查是否短路。如果适用，在父学期之后跳到学期。

   for term in terms:
       if term is operator:
           pop 2 values
           evaluate (in reverse order)
           push result value
           if short-circuit (result is 0 and parent is AND, or result is non-zero and parent is OR):
               term = term + offset
       else if term is function:
           pop arguments
           evaluate (in reverse order)
           push result value
       else:
           push term value
   

Answer 2

您可以使用相同的算法来构建表达式树：而不是评估operand1 operator operand2，创建一个以operand1和operand2作为子节点和operator作为父节点的节点。

一旦你有了树，你就可以评估它（从上到下）。您可以通过不评估其中一个孩子来缩短评估（例如，如果左孩子评估为False并且运算符为and）。

您会注意到给定的算法等效于从下到上的评估。虽然这很简单（并且可以节省内存），但您不能应用短路，因为您永远不知道是否应该评估您所在的分支。