首先谈谈你的发言:
我推断出我所寻找的那棵树最多可以有
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()