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

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

  •  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()