python - 用整个元组替换嵌套元组中的值

Question

好的，

我正在开发一个语言证明器，并且我有一系列表示语句或表达式的元组。 有时，我最终会得到一个嵌入的“和”语句，并且我试图将其“冒泡”到表面。 我想要一个如下所示的元组:

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

或者，举一个更简单的例子:

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

我想将 and 分成两个语句，这样第一个语句的结果是:

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

所以基本上，问题是试图用整个元组的值替换嵌套元组，但嵌套元组已修改。这是非常难看的。 :(

我不是 super 流利的Python流利者，所以它变得非常复杂，有很多我知道不应该存在的for循环。 :( 非常感谢任何帮助!

Answer 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 循环中，直到输出与输入相同，如下所示:

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”示例，因为它在“not”之前冒泡了“and”，而您说您希望将其单独保留:

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

所以我想你必须在 recursive_bubble_ands_up 中构建“not”的特殊情况，或者在运行我的函数之前应用你的非处理函数，并将其插入到 recursive_bubble_ands_up 之前 在 repeat_bubble_until_finished 中，以便它们交替应用。

好吧，我现在真的该 sleep 了。