0

昨日、この質問を投稿しましたが、私のアカウントが 9 か月後もまだアクティブであることに気付かず、二重投稿で申し訳ありませんでした。ジェリービーンによって指摘された私の例のエラーを修正しました。問題のコンテキストについてさらに詳しく説明します。 .

Pythonでネストされたリストと文字列として表される一次論理式を処理して、論理和正規形になるようにしようとしています。

すなわち

[
    '&', 
    ['|', 'a', 'b'], 
    ['|', 'c', 'd']
]

になる

[
    '|',
    [
        '|', 
        ['&', 'a', 'c'], 
        ['&', 'b', 'c']
    ], 
    [
        '|', 
        ['&', 'a', 'd'], 
        ['&', 'b', 'd']
    ]
]`

|はまたはであり、&です。

現在、「ands」のリスト引数内にネストされた「or」記号が見つからなくなるまで、式を何度かパスする再帰的な実装を使用しています。普遍的な計算ツリーロジック|の文字列とリストとして表されるネストされた式のセットを処理するために使用されているため、 s とsだけで&なく一時的な演算子も含まれます。

これは私の実装でperformDNF(form)あり、エントリ ポイントです。現時点では、dnfDistributivity()小さい入力に対して機能する数式に対して単一のパスを実行しますが、より大きな入力を使用すると、while ループ チェック関数 ( checkDistributivity()) は|s 内に&s を検出せず、終了します。誰か助けてください、これは私を怒らせています。

def dnfDistributivity(self, form):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                if form[1][0] == '|':
                    form = [
                               '|', 
                               ['&', form[2], form[1][1]], 
                               ['&', form[2], form[1][2]]
                           ]
                elif form[2][0] == '|':
                    form = [
                                '|', 
                                ['&', form[1], form[2][1]], 
                                ['&', form[1], form[2][2]]
                           ]
            form[1] = self.dnfDistributivity(form[1])
            form[2] = self.dnfDistributivity(form[2])
        elif len(form) == 2:
            form[1] = self.dnfDistributivity(form[1])
    return form

def checkDistributivity(self, form, result = 0):
    if isinstance(form, type([])):
        if len(form) == 3:
            if form[0] == '&':
                print "found &"
                if isinstance(form[1], type([])):
                    if form[1][0] == '|':
                        return 1
                elif isinstance(form[2], type([])):
                    if form[2][0] == '|':
                        return 1
                else:
                    result = self.checkDistributivity(form[1], result)
                    print result
                    if result != 1:
                        result = self.checkDistributivity(form[2], result)
                        print result
        elif len(form) == 2:
            result = self.checkDistributivity(form[1], result)
            print result
    return result

def performDNF(self, form):
    while self.checkDistributivity(form):
        form = self.dnfDistributivity(self.dnfDistributivity(form))
    return form
4

2 に答える 2

3

まず、コードに関する2つの一般的な注意事項：

  • return Trueの代わりに使用してくださいreturn 1。
  • isinstance(form, list)の代わりに使用してくださいisinstance(form, type([]))。

第二に、他のいくつかの観察：

  • また、二重否定を取り除きたいと思います。現在、あなたのコードはそれをしていません。
  • 同様に、否定を葉にプッシュするには、ド・モルガンの法則の1つを適用する必要があります。

それとは別に、このコードの可読性は大幅に向上すると思います。私が正しいと信じている代替の実装を提供します。以下のコードがあなたのために働くかどうか私に知らせてください。式の作成に夢中になっていなかったので、エッジケースを見逃した可能性があります。最後に、通常の命題論理語にのみ焦点を当てます。CTL固有の接続詞を含む変換を適用する方法を明確にする必要があります。

  1. Op演算子（接続）を表すクラスを作成します。

    class Op(list):
    def __init__(self, *args):
        super().__init__(args)

    の引数__init__はオペランドです。このコードはsuper、PEP 3135superで定義されているとおりに使用され、 Python3.xでのみ機能します。Python2.xでは、PEP367で定義されているとおりに使用する必要があります。

    class Op(list):
    def __init__(self, *args):
        super(Op, self).__init__(args)

  2. Op演算子ごとにの単純なサブクラスを作成します。デバッグの目的で、カスタム__str__メソッドを実装することをお勧めします。

    class Neg(Op):
    def __str__(self):
        return '!(%s)' % tuple(self)
class And(Op):
    def __str__(self):
        return '(%s) & (%s)' % tuple(self)
class Or(Op):
    def __str__(self):
        return '(%s) | (%s)' % tuple(self)
class AX(Op):
    def __str__(self):
        return 'AX (%s)' % tuple(self)
...

    これで、式！（a＆b）をとして作成できますNeg(And('a', 'b'))。

  3. 特定の変換を一度適用する非常に単純な関数を作成します。これにより、実装がクリーンに保たれます。これらの関数に注釈を付け、それらをどのように適用するかについての情報を示します。プレオーダー関数は上から下に適用する必要があります。最初に式ツリーのルートを変換してから、再帰します。事後関数は、部分式に再帰的に適用された後、式に適用する必要があります。接続詞のタイプを確認するために使用します。isinstance

    1. 簡単に始めましょう。この関数removeDoubleNegは二重否定を削除します。

      @expressionTransformation('postorder')
def removeDoubleNeg(expr):
    if isinstance(expr, Neg) and isinstance(expr[0], Neg):
        return expr[0][0]

    2. 次に、ド・モルガンの法則の1つを定義しましょう。

      @expressionTransformation('preorder')
def deMorgan(expr):
    if isinstance(expr, Neg) and isinstance(expr[0], And):
        return Or(Neg(expr[0][0]), Neg(expr[0][1]))

    3. そして今、この質問がすべてについてである関数：

      @expressionTransformation('preorder', 'postorder')
def distribute(expr):
    if isinstance(expr, And):
        if isinstance(expr[0], Or):
            return Or(And(expr[0][0], expr[1]), And(expr[0][1], expr[1]))
        if isinstance(expr[1], Or):
            return Or(And(expr[0], expr[1][0]), And(expr[0], expr[1][1]))

      わお！それははるかに少ないコードです！

  4. さて、これはどのように機能しますか？式変換fの単純な実装には、定型コードが含まれることに注意してください。

    1. 引数が（定数または変数ではなく）結合であるかどうかをテストします。
    2. 式ツリーのルートにfを適用してみます。
    3. 再帰します。
    4. 結果を返します。

    fによっては、ステップ1と2を逆にする必要がある場合があります（preorderではなくpostorder）。それでも、fのすべての実装は同じように見えます。特にさらに多くの変換を定義する予定がある場合は、定型コードを避けたいと思うでしょう。前のステップで定義された関数を非常に簡潔にした（したがってデバッグが容易にした）のは、この定型文の欠如です。関数によって返されるデコレータは、この問題を解決しました。その実装は次のとおりです。expressionTransformation

    from functools import wraps
def expressionTransformation(*args):
    def wrap(f):
        @wraps(f)
        def recursiveTransformation(expr):
            if not isinstance(expr, Op):
                return expr
            if 'postorder' in args:
                expr[:] = map(recursiveTransformation, expr)
            res = f(expr)
            expr = expr if res is None else res 
            if 'preorder' in args:
                expr[:] = map(recursiveTransformation, expr)
            return expr
        return recursiveTransformation
    return wrap

    ここで何が起こるかは次のとおりです。

    1. この関数は、引数として変換関数を受け取るexpressionTransformationデコレータ（という名前の）を返します。wrapf
    2. wrapこの引数が接続詞である場合にのみ、その引数recursiveTransformationに適用される再帰関数を返します。fexpr
    3. argsに指定された引数に応じてexpressionTransformation、部分式にffを適用する前または後（または前と後）に適用されます。
    4. 変換が行われないf場合に戻る可能性があるという仮定が行われます。None

    この関数は、名前などfunctools.wrapsのの特定のプロパティをにコピーするために使用されます。この機能は必須ではありません。frecursiveTransformation

    'postorder' in args（テストを'preorder' in args何度も使用するよりも、事前注文と事後注文の変換を作成する方が効率的な方法があることに注意してください。ただし、わかりやすくするためにこれを選択しました。）

  5. それで全部です。これで、これらの関数を簡単に組み合わせることができます（この関数は装飾されるべきではないことに注意してください）。

    def toDNF(expr):
    return distribute(removeDoubleNeg(deMorgan(expr)))

  6. 次のようなステートメントを使用してコードをテストできます。

    toDNF(AX(And(Or('a', 'b'), And(Or('c', 'd'), Or('e', 'f')))))
toDNF(Neg(And(Or(Neg(Neg('a')), 'b'), And(Or('c', 'd'), Or('e', 'f')))))
于 2009-11-25T10:20:25.153 に答える
0

あなたが持っている：

    elif len(form) == 2:
        result = self.checkDistributivity(form[1], result)
        print result

そうではありませんか：

    elif len(form) == 2:
        result_1 = self.checkDistributivity(form[1], result)
        result_2 = self.checkDistributivity(form[2], result) 
        if result_1 or result_2:
            return 1
于 2009-11-25T03:24:24.850 に答える