限制布尔表达式的深度

Question

我得到了任意深度的布尔表达式，例如

(A or (B and (C or (~D and E) or F) or (G and H)))

。 每个级别可以有任意数量的术语。

我想将表达式的深度（嵌套括号的最大深度 + 1）限制为某个常数，例如 4。如果深度超过该界限，那么我想生成一个深度不超过界限的等效表达式。

我知道我可以转换为 CNF 或 DNF，这会将深度限制为 2，但表达式的大小可能会呈指数级增长。

如何利用更多可用级别来尽可能限制结果表达式的大小？

Answer 1

这是一种平衡深度减少与表达式大小的方法：

1. 首先，将表达式解析成树，并识别超出深度限制的子树。

2. 对于每个有问题的子树，应用“滚动”转换，尽可能保留结构：

   • 从最深层开始
   • 使用分配律对该级别的兄弟项进行分组
   • 将分组术语上拉一级
   • 重复直到深度在范围内

这是一个简单的例子。给定最大深度 3 和表达式：

A or (B and (C or (D and E) or F))  # depth 4

转变为：

A or (B and ((C or F) or (D and E)))  # depth 3

这避免了完全的 CNF/DNF 转换，同时仍然保证深度限制。大小增加通常比 CNF/DNF 小得多，因为我们只转换有问题的子树并保留表达式的较浅部分。

这是实现此功能的 Python 代码：

from dataclasses import dataclass
from typing import List, Union

@dataclass
class BoolNode:
    op: str  # 'and', 'or', 'not', or None for literals
    children: List['BoolNode']
    literal: str = None
    
def parse_expression(expr: str) -> BoolNode:
    """Parse string expression into tree. Implementation left as exercise."""
    pass

def get_depth(node: BoolNode) -> int:
    if not node.op:  # Literal
        return 1
    return 1 + max(get_depth(child) for child in node.children)

def bound_depth(node: BoolNode, max_depth: int) -> BoolNode:
    """Recursively transform tree to bound depth."""
    if get_depth(node) <= max_depth:
        return node
        
    # Find deepest subtrees exceeding limit
    for i, child in enumerate(node.children):
        if get_depth(child) > max_depth - 1:
            # Group terms at deepest level and pull up
            node.children[i] = transform_subtree(child, max_depth - 1)
    
    return node

def transform_subtree(node: BoolNode, target_depth: int) -> BoolNode:
    """Transform subtree to reduce depth while preserving semantics."""
    current_depth = get_depth(node)
    if current_depth <= target_depth:
        return node
        
    if node.op == 'not':
        return BoolNode('not', [transform_subtree(node.children[0], target_depth - 1)])
        
    # Group deepest terms
    new_children = []
    for child in node.children:
        if get_depth(child) == current_depth - 1:
            # Pull up children of deep nodes
            if child.op == node.op:
                new_children.extend(child.children)
            else:
                new_children.append(transform_subtree(child, target_depth - 1))
        else:
            new_children.append(child)
            
    return BoolNode(node.op, new_children)

# Example usage:
expr = "(A or (B and (C or (~D and E) or F) or (G and H)))"
tree = parse_expression(expr)
bounded_tree = bound_depth(tree, 3)  # Limit depth to 3

这往往会产生比完整 CNF/DNF 转换更紧凑的结果。 时间复杂度为 O(n)，其中 n 是树中的节点，因为我们在转换过程中最多处理每个节点一次。 如果有帮助请告诉我！