具有二元和一元节点的波兰表示法树（前缀）的高度

Question

我需要获取具有二元和一元节点的波兰表示法树（前缀）的深度。解决方案here可以通过简单地预先反转表达式字符串来解决；但是，如果前缀表达式不完整，则解决方案无法推断最小深度是多少。如何扩展解决方案？

编辑：下面我发布代码以更清楚地解释：

def getPNdepth(expression):
    stack = []
    expression = expression[::-1]
    for val in expression:
        if val in ['-', '+', '*', '/']:  # all binary operators
            stack.append(max(stack.pop(), stack.pop()) + 1)
        elif val in ['cos', 'exp']:  # all unary operators
            stack[-1] += 1
        else:  # an operand (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

Answer 1

通过预排序，您可以根据观察采取不同的方法，即当访问最深的节点时，所有祖先都将在堆栈上，因此最大堆栈大小直接指示树的深度。

对于不完整的树，我们还可以注意到，如果最长的路径以运算符结束，则通过将其下方的操作数添加为叶子，即可达到最小深度，只需在深度上添加 1。

涵盖这两个原则，每当我们向堆栈添加运算符时，我们都可以跟踪这个最小深度，始终为操作数（至少）计算一个额外的所需级别。我们不在堆栈上放置任何东西来表示操作数，只放置运算符。

def getPNdepth(expression):
    stack = []
    depth = 0
    for val in expression:
        if val in ['-', '+', '*', '/']:  # all binary operators
            stack.append(2)  # = number of operands
        elif val in ['cos', 'exp']:  # all unary operators
            stack.append(1)
        else:  # an operand (x)
            while stack:  # remove operators that got all their operands
                stack[-1] -= 1
                if stack[-1]:
                    break
                stack.pop()
        depth = max(depth, len(stack) + 1)
            
    return depth