1

わかった、

私は言語証明に取り組んでおり、ステートメントまたは式を表す一連のタプルを持っています。時々、「and」ステートメントが埋め込まれてしまい、それを表面に「バブル」させようとしています。次のようなタプルを取得したい:

('pred', ('and', 'a', 'b'), 'x')

または、より単純な例:

( ('and', 'a', 'b'), 'x')

and を 2 つのステートメントに分けて、一番上のステートメントが次のようになるようにします。

('and', ('pred', 'a', 'x',), ('pred', 'b', 'x') )

そして一番下のもの：

('and', ('a', 'x'), ('b', 'x') )

私は多くのことを試しましたが、常に非常に醜いコードであることが判明しました。また、次のようなネストされたタプルがさらにある場合、問題が発生します。

('not', ('p', ('and', 'a', 'b'), 'x') )

結果を出したい

('not', ('and', ('p', 'a', 'x',), ('p', 'b', 'x') ) )

基本的に、問題はネストされたタプルをタプル全体の値に置き換えようとしていますが、ネストされたタプルは変更されています。とても醜いです。:(

私は非常に流暢なPythonではないので、そこにあってはならないことがわかっている多くのforループで非常に複雑になります。:(どんな助けでも大歓迎です！

4

1 に答える 1

1

この再帰的なアプローチは機能しているようです。

def recursive_bubble_ands_up(expr):
    """ Bubble all 'and's in the expression up one level, no matter how nested.
    """
    # if the expression is just a single thing, like 'a', just return it. 
    if is_atomic(expr):
        return expr
    # if it has an 'and' in one of its subexpressions 
    #  (but the subexpression isn't just the 'and' operator itself)
    #  rewrite it to bubble the and up
    and_clauses = [('and' in subexpr and not is_atomic(subexpr)) 
                   for subexpr in expr]
    if any(and_clauses):
        first_and_clause = and_clauses.index(True)
        expr_before_and = expr[:first_and_clause]
        expr_after_and = expr[first_and_clause+1:]
        and_parts = expr[first_and_clause][1:]
        expr = ('and',) + tuple([expr_before_and + (and_part,) + expr_after_and 
                                 for and_part in and_parts])
    # apply recursive_bubble_ands_up to all the elements and return result
    return tuple([recursive_bubble_ands_up(subexpr) for subexpr in expr])

def is_atomic(expr):
    """ Return True if expr is an undividable component 
    (operator or value, like 'and' or 'a'). """
    # not sure how this should be implemented in the real case, 
    #  if you're not really just working on strings
    return isinstance(expr, str)

すべての例で動作します:

>>> tmp.recursive_bubble_ands_up(('pred', ('and', 'a', 'b'), 'x'))
('and', ('pred', 'a', 'x'), ('pred', 'b', 'x'))
>>> tmp.recursive_bubble_ands_up(( ('and', 'a', 'b'), 'x'))
('and', ('a', 'x'), ('b', 'x'))
>>> tmp.recursive_bubble_ands_up(('not', ('p', ('and', 'a', 'b'), 'x') ))
('not', ('and', ('p', 'a', 'x'), ('p', 'b', 'x')))

これは、他の「特別な」演算子を認識していないことに注意してくださいnot-コメントで述べたように、それをどうするべきかわかりません。しかし、それはあなたに何かを与えるはずです。

編集：ああ、おっと、これは単一の「バブルアップ」操作しか実行しないことに気付きました。たとえば、次のようになります。

>>> tmp.recursive_bubble_ands_up(((('and', 'a', 'b'), 'x'), 'y' ))
(('and', ('a', 'x'), ('b', 'x')), 'y')
>>> tmp.recursive_bubble_ands_up((('and', ('a', 'x'), ('b', 'x')), 'y'))
('and', (('a', 'x'), 'y'), (('b', 'x'), 'y'))

したがって、次のように、「and」を多くのレベルからバブルアップさせたい場合は、出力が入力と同一になるまで、while ループで適用することをお勧めします。 

def repeat_bubble_until_finished(expr):
    """ Repeat recursive_bubble_ands_up until there's no change 
    (i.e. until all possible bubbling has been done). 
    """
    while True:
        old_expr = expr
        expr = recursive_bubble_ands_up(old_expr)
        if expr == old_expr:
            break
    return expr

一方、それを行うと、実際に私のプログラムが「not」の例を壊していることがわかります。これは、「and」を「not」の前にバブルするためです。

>>> tmp.recursive_bubble_ands_up(('not', ('p', ('and', 'a', 'b'), 'x')))
('not', ('and', ('p', 'a', 'x'), ('p', 'b', 'x')))
>>> tmp.repeat_bubble_until_finished(('not', ('p', ('and', 'a', 'b'), 'x')))
('and', ('not', ('p', 'a', 'x')), ('not', ('p', 'b', 'x')))

したがって、「not」の特別なケースを に組み込むrecursive_bubble_ands_upか、私の実行前に処理しない関数を適用し、 in の前recursive_bubble_ands_upに挿入してrepeat_bubble_until_finished、それらが交互に適用されるようにする必要があると思います。

よし、もう本当に寝たほうがいい。

于 2012-04-22T08:15:01.520 に答える