短路前綴布爾表達式

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