短路前缀布尔表达式

Question

我有一堆用前缀表示法写的布尔表达式（也称为Polish notation）。这种格式的嵌套表达式非常易于评估（请参阅维基百科文章中的算法）。

然而，在维基百科页面上给出的算法不会做短路（当它评估and f() g()时，如果f()为假，它不会跳过对g()的评估）。有什么办法可以修改算法以包含短路吗？

Answer 1

你可以使用相同的算法来构建表达式树：不是评估operand1 operator operand2，创建一个节点与operand1和operand2儿童，并operator父。

一旦你有了树，你可以评估它（从上到下）。您可以通过不评估其中一个孩子来短路评估（例如，如果左边的孩子评估为False，操作者为and）。

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

Answer 2

我最近需要做到这一点，有一种算法，似乎工作上来：

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