具有二元和一元节点的RPN树的高度

首先谈谈你的发言:

我推断出我所寻找的那棵树最多可以有 depth - 1 二进制节点, depth 叶子

这是一个错误。这些最大值应该是2 ^深度 1个内部二进制节点,2个 ^深度 树叶。

你的代码 referenced 可以很容易地扩展以支持一元运算。原理是一样的:二进制运算符添加一个根节点,其高度由 最高 它下面的子树。由于一元运算下面只有一个子树,所以它是最高的,所以没有 max 是需要的,我们可以写 stack.append(stack.pop() + 1) 这真的简化为 stack[-1] += 1

def getRPNdepth(expression):
    stack = []
    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)  
    return stack.pop()

请注意,如果堆栈在执行之前有多个元素 return stack.pop() ,则输入表达式不完整。如果你想知道如果表达式完成,最小高度是多少,那么根据需要多次重复二进制运算符的操作,以在堆栈上得到一个项:

    while len(stack) > 1:
        stack.append(max(stack.pop(), stack.pop()) + 1)
        
    return stack.pop()