python - 获取 RPN 树大小

Question

我已经实现了以下“tree sizer”，但在某些情况下它会失败，下面的示例在应该返回大小 4 时返回大小 2，任何人都可以帮助我。我已经写了好几次了，没有用，一直失败。

def getRPNdepth(expression):
    treesize=0
    maxtreesize=treesize
    mintreesize=treesize
    tmpexp=expression
    tmpfmla = [1 if n[0] == 'x' else n for n in tmpexp]
    print(tmpfmla)
    try:
        stack = []
        for val in tmpfmla:
            if val in ['-', '+', '*', '/']:

                op1 = stack.pop()
                op2 = stack.pop()
                if val == '-': result = op2 - op1
                if val == '+': result = op2 + op1
                if val == '*': result = op2 * op1
                if val == '/':
                    if op1 == 0:
                        result = 1
                    else:
                        result = op2 / op1
                stack.append(result)
                treesize=treesize+1
            else:

                stack.append(float(val))
                treesize = treesize - 1

            if treesize>maxtreesize:
                maxtreesize=treesize
            if treesize<mintreesize:
                mintreesize=treesize
        return abs(mintreesize)
    except:
        print('error validate rpn>' + str(expression))
        return 0



xxxx = ['x6', 'x7', '+', 'x7', '+', 'x7', '+', 'x7', '+']
print(getRPNdepth(xxxx))

几个例子:['1','1','+','1','1','+','+']['1','1','1','+','+']两者都给出了 3 的结果，这是正确的，但是。['1','1','+','1','1','+','+']当它应该是 4 时返回 3

总而言之，我需要从其字符串表示中了解 RPN 的深度。

Answer 1

计算树的深度类似于评估表达式，但运算符计算结果深度而不是结果值:

def getRPNdepth(expression):
    stack = []
    for val in expression:
        if val in ['-', '+', '*', '/']:
            stack.append(max(stack.pop(),stack.pop())+1)
        else:
            stack.append(1)
    return stack.pop()