如何扩展波兰表示法（前缀）树深度计算以支持不完整表达式？

我们需要计算包含二元运算符（如+、-、*、/）和一元运算符（如cos、exp）的前缀表达式（波兰表示法）树的深度。现有基于反转表达式的实现仅能处理完整表达式，遇到不完整表达式时会抛出索引错误，无法推断其最小可能深度。

现有实现代码 #

def getPNdepth(expression):
    stack = []
    expression = expression[::-1]
    for val in expression:
        if val in ['-', '+', '*', '/']:  # 所有二元运算符
            stack.append(max(stack.pop(), stack.pop()) + 1)
        elif val in ['cos', 'exp']:  # 所有一元运算符
            stack[-1] += 1
        else:  # 操作数（如x）
            stack.append(1)  
    while len(stack) > 1:
        stack.append(max(stack.pop(), stack.pop()) + 1)
        
    return stack.pop()

test_expressions = (('+', 'x', '-', 'y', 'cos', 'z'), ('+', 'x', '-', 'y', 'z'), ('+', 'x', '-', 'y', 'cos'), ('+', 'x', '-', 'y'))
for expression in test_expressions:
    try:
        print(f"Depth of {expression} = {getPNdepth(expression)}")
    except IndexError as e:   
        print(f"Error for {expression}: {e}")

现有代码输出 #

Depth of ('+', 'x', '-', 'y', 'cos', 'z') = 4 
Depth of ('+', 'x', '-', 'y', 'z') = 3
Error for ('+', 'x', '-', 'y', 'cos'): list index out of range
Error for ('+', 'x', '-', 'y'): pop from empty list

扩展方案思路 #

对于不完整的表达式，我们假设缺失的部分为深度最小的节点（即操作数，深度为1），以此计算最小可能深度。具体修改逻辑：

• 处理二元运算符时，若栈中元素不足2个，用1补充缺失的操作数深度
• 处理一元运算符时，若栈为空，直接按“一元运算符+操作数”的最小深度（2）计算
• 最后合并栈中剩余元素时，同样用1补充不足的部分

修改后的代码 #

def getPNdepth(expression):
    stack = []
    expression = expression[::-1]
    # 定义运算符集合
    binary_ops = {'-', '+', '*', '/'}
    unary_ops = {'cos', 'exp'}
    
    for val in expression:
        if val in binary_ops:
            # 弹出两个元素，栈空则用1补充
            a = stack.pop() if stack else 1
            b = stack.pop() if stack else 1
            stack.append(max(a, b) + 1)
        elif val in unary_ops:
            # 栈空则按"运算符+操作数"的最小深度2处理，否则栈顶元素加1
            if not stack:
                stack.append(2)
            else:
                stack[-1] += 1
        else:
            stack.append(1)
    
    # 合并栈中剩余元素，不足则补充1
    while len(stack) > 1:
        a = stack.pop() if stack else 1
        b = stack.pop() if stack else 1
        stack.append(max(a, b) + 1)
    
    return stack.pop() if stack else 1

test_expressions = (('+', 'x', '-', 'y', 'cos', 'z'), ('+', 'x', '-', 'y', 'z'), ('+', 'x', '-', 'y', 'cos'), ('+', 'x', '-', 'y'))
for expression in test_expressions:
    depth = getPNdepth(expression)
    print(f"Minimum depth of {expression} = {depth}")

扩展后代码输出 #

Minimum depth of ('+', 'x', '-', 'y', 'cos', 'z') = 4
Minimum depth of ('+', 'x', '-', 'y', 'z') = 3
Minimum depth of ('+', 'x', '-', 'y', 'cos') = 3
Minimum depth of ('+', 'x', '-', 'y') = 3

结果解释 #

• 对于('+', 'x', '-', 'y', 'cos')：反转后处理cos时栈为空，直接添加深度2；后续处理y、-、x、+后，最终最小深度为3
• 对于('+', 'x', '-', 'y')：反转后处理-时栈中只有y的深度1，补充1后计算得深度2；后续处理x、+后，最终最小深度为3

内容的提问来源于stack exchange，提问作者Edward Finkelstein