代码之家 › 专栏 › 技术社区 › Edward Finkelstein

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

rpn tree python

0

Edward Finkelstein · 技术社区 · 1 年前

我知道有一种方法可以获得纯二进制RPN树的深度(例如。 here ),但我正在努力寻找如何获得具有二进制的树的深度和一元节点。

对于这个问题,我目前正在考虑以下令牌:一组二进制运算符 '+', '-', '*' ,一组一元运算符 'cos', 'exp' ,和叶节点 'x' 。我推断出我所寻找的那棵树最多可以有 depth - 1 二进制节点, depth 叶子和 0 一元节点,或者在另一个极端, 深度 一元节点, 0 二进制节点和 1 叶节点。此外,我发现在我的设置的有效RPN表达式中,叶子的数量似乎总是二进制节点的数量+1。然而,我不认为这是解决我的问题的有用标准,因为简单地改变代币的顺序可以完全改变深度。。。

然而,我需要知道具有一元和二元节点的RPN表达式的深度。另外,如果RPN表达式不完整(意味着它需要在末尾添加额外的节点才能完成),那么很高兴知道表达式可以完成的最小深度是多少。

0 回复 | 直到 1 年前

1

0

trincot Jakube 1 年前

首先谈谈你的发言:

我推断出我所寻找的那棵树最多可以有 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()