2

以下のような表現があります。

{1000} AND ({1001} OR {1002} OR {1003})

許可される演算子は OR と AND で、括弧を使用して式をネストできます。PHP 5.3 で実装された Shunting Yard アルゴリズムを使用して、この文字列をトークン化し、抽象構文木 (AST) に変換することができました。上記の式の結果は次のようになります。

1000 1001 1002 | 1003 | &


    &
  /   \
1000   |
      / \
     |   1003
    / \
1001  1002

このツリーをトラバースするとき、ユーザーが選択できる数値の最終的な組み合わせを出力したいと考えています。与えられた表現では、これは不可能です。私が必要とするのは、実際には分配法則が適用された後のフォームです。

(1000 & 1001) | (1000 & 1002) | (1000 & 1003)

1000 1001 & 1000 1002 & | 1000 1003 & |

               _______________|_____________
              /                             \
      _______|____                           &
     /            \                         / \
    &              &                    1000   1003
  /   \           / \
1000   1001    1000  1002

&-operator ノードとして許可されているノードは、リーフを運ぶ最後のノードだけであると結論付けました。他のすべては |-operator ノードでなければなりません。

上記で説明した文法を使用して任意の AST を、すべての最終順列を表すものに変換する方法は? 中置表現のトークンに分配法則を適用する方がよいでしょうか? ツリーの代わりに RPN 表現を使用する方が簡単ですか?

また、次のようなより難しい例があることにも注意してください。

(1000 & 1008) & (1001 | 1002 | 1003)
1000 1008 & 1001 1002 | 1003 | &
       ______ & ___
      /            \
     &             |
    / \           / \
1000   1008      |   1003
                / \
            1001  1002

結果として欲しいのは：

(1000 & 1008 & 1001) | (1000 & 1008 & 1002) | (1000 & 1008 & 1003)
1000 1008 & 1001 & 1000 1008 & 1002 & | 1000 1008 & 1003 & |

                        __________________|_________
                       /                            \
         _____________|_________                     &
        /                       \                   / \
       &                        &                  &   1003
      /  \                     / \                / \
     &    1001                &   1002        1000   1008
    / \                      / \
1000   1008              1000   1008

別の (より複雑な) 例として、左側のサブツリーと右側のサブツリーを切り替えるか、別の &-node を 1003 => 1003 1009 & の代わりに追加します。

私がすでに試したこと: 何度もグーグル検索し、ツリーの前後の順序をトラバースし、成功しなかったアルゴリズムを見つけようとしました。

正しい方向へのヒントや指針に感謝します。

4

2 に答える 2

1

あなたがやりたいと思われるのは、生成が分離正規形であることです。処理する興味深いケースがたくさんあるため、これを行うのは見た目よりも困難です。

やりたいことは、次の書き換えルールをツリーのどこにでも徹底的に実装することです (実際には、葉を上に向けるだけで十分です)。

 rule distribute_and_over_or(a: term, b: term, c: term): term->term
    "  \a and (\b or \c) " ->  " \a and \b or \a and \c ";

複雑にすると、冗長なサブタームが得られるため、次のルールが必要になる可能性があります。

 rule subsumption_identical_or_terms:(a: term): term->term
    "  \a or \a " ->  \a";

 rule subsumption_identical_and_terms:(a: term): term->term
    "  \a and \a " ->  \a";

問題を表現した方法では、「not」を使用しませんでしたが、表示される可能性が高いため、次の追加ルールが必要です。

 rule cancel_nots:(term: x): term -> term
    " not (not \x)) " -->  "\x";

rule distribute_not_over_or(a: term, b: term): term->term
    " not( \a or \b ) " ->  " not \a  and not \b ";

 rule distribute_not_over_and(a: term, b: term): term->term
    " not( \a and \b ) " ->  " not \a  or not \b ";

また、自己キャンセル用語に遭遇する可能性があるため、それらを処理する必要があります。

 rule self_cancel_and(a: term): term->term
     "  \a and not \a " -> "false";

 rule self_cancel_or(a: term): term->term
     "  \a or not \a " -> "true";

true と false を取り除く方法:

 rule and_true(a: term): term->term
     " \a and true " -> " \a ";

 rule and_false(a: term): term->term
     " \a and false " -> " false ";

 rule or_true(a: term): term->term
     " \a or true " -> " true ";

 rule and_false(a: term): term->term
     " \a or false " -> " \a ";

 rule not_false(a: term): term->term
     " not false " -> " true ";

 rule not_true(a: term): term->term
     " not true " -> " false ";

(私は、「not」バインディングが「and」バインディングよりも「or」よりタイトであるという式の優先順位を想定しています)。

示されているルールは、さまざまなサブツリーがせいぜい「バイナリ」であると想定していますが、例に示すように、実際の子が多数ある場合があります。実際には、結合法則についても心配する必要があります。包摂法則と相殺法則を実際に機能させたい場合は、交換法則も考慮する必要があります。

サブ式に関係演算子が含まれている場合、暗黙の「not」伝播を発見する可能性があります。

    " not ( x > y ) " -->  " x <= y "

リレーショナル比較を正規化することもできます。

    "  x < y " -->  " not (x >= y )"

ツリーを PHP で実装したので、手続き的にツリーを上ったり下ったりして、これらと同等のものを手動でコーディングする必要があります。これは可能ですが、かなり不便です。(RPN としてのトークンと AST の両方でこれを行うことができますが、トークンの文字列をシャッフルする必要がないため、AST の方がはるかに簡単だと思います)。

シンボリック式を操作するときは、書き換えを直接受け入れて適用するエンジン (通常はプログラム変換システム) を適用する方が簡単です。ここで使用した表記は、DMS Software Reengineering Toolkit から取得したもので、これらのルールを直接受け取り、結合性と可換性を自動的に処理します。これはおそらく、PHP 内で実行可能な選択ではありません。

最後にもう 1 つ問題があります。項が複雑な場合、最終的な選言正規形は非常に大きく、非常に速くなる可能性があります。私たちにはまさにこれを望んでいたクライアントがいましたが、大きな開始条件で彼にそれを渡すまで、たまたま何百もの葉の結合を生み出しました。(これまでのところ、任意のブール項を表現する適切な方法は見つかりませんでした。)

于 2014-07-15T03:01:39.500 に答える
0

私を最も助けてくれたキーワードに言及してくれてありがとう:選言標準形。私は実際にこの変換を探していることに気づいていませんでした。

インターネット上で詳細なアルゴリズムの説明を見つけることができなかったので、自分でやってみました。これは、擬似コードで行った方法です。わかりにくかったら教えてください。

- Traverse the AST recursively post order wise
- If an &-node is found, check if one of the children nodes is a |-node
- Set orChild and andChild accordingly
- Traverse the orChild-tree iterative pre order wise and for each OR-leaf push a new &-node with andChild and the OR-leaf value to the stack
- If you meet another &-node push a new &-node with andChild and the whole &-node you found to the stack
- After traversing is done, combine the nodes on the stack using an |-node
- The new sub tree, which has an |-node as root, replaces the &-node you started to traverse from
- As the outer traversal is post order, the newly created nodes are not traversed and have no effect on further changes
- Repeat the whole process until the resulting tree does not change anymore
于 2014-07-15T14:03:50.377 に答える