1

好的，

我正在研究语言证明器，并且我有一系列表示语句或表达式的元组。有时，我最终得到一个嵌入的“和”语句，我试图将它“冒泡”到表面。我想要一个看起来像这样的元组：

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

或者，举个更简单的例子：

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

我想将 ands 分成两个语句，以便最上面的语句产生：

('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'))

所以你真正想要的可能是在一个while循环中应用它，直到输出与输入相同，如果你想让你的'and'从多个级别冒泡，就像这样： 

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

另一方面，这样做表明实际上我的程序打破了你的“非”示例，因为它在“非”之前冒泡了“和”，你说你想让它一个人呆着：

>>> 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' into 构建一个特殊情况recursive_bubble_ands_up，或者在运行我的之前应用你的非处理函数，然后在recursive_bubble_ands_upin之前插入它，repeat_bubble_until_finished以便它们交替应用。

好吧，我现在真的该睡觉了。

于 2012-04-22T08:15:01.520 回答