algorithm - プレフィックスのブール式を短絡する

Question

プレフィックス表記（ポーランド記法とも呼ばれます）で記述されたブール式がたくさんあります。この形式のネストされた式は、非常に簡単に評価できます（Wikipediaの記事のアルゴリズムを参照してください）。

ただし、ウィキペディアのページに記載されているアルゴリズムは短絡を行いません（評価するときに、 ifがfalseand f() g()の評価をスキップしません）。短絡を含めるようにアルゴリズムを変更する方法はありますか？g()f()

Answer 1

私は最近これを行う必要があり、動作するように見えるアルゴリズムを思いつきました:

1. shunting yard を使用して式を解析し、後置用語シリーズを生成します。

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ノードを作成します。operand1operand2operator

ツリーを取得したら、それを評価できます (上から下へ)。子の 1 つを評価しないことで、評価を短絡できます (たとえば、左の子が に評価されFalse、演算子が である場合and)。

与えられたアルゴリズムは、下から上への評価と同等であることがわかります。これは単純ですが (そしてメモリを節約します)、現在のブランチを評価する必要があるかどうかさえわからないため、ショートサーキットを適用することはできません。