Get RPN tree size

Question

I've implemented the following 'tree sizer' but it fails under certain conditions, the example below returns size 2 when it should return size 4, can anyone help me out. I've written this several times, to no avail, it keeps failing.

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

a couple of examples : ['1','1' ,'+','1','1' ,'+' ,'+'] ['1','1','1' ,'+' ,'+'] both give the result of 3, which is correct, but. ['1','1' ,'+','1','1' ,'+' ,'+'] returns 3 when it should be 4

All in all, I need to know the depth of the RPN from its string representation.

What is 'tree size' ? General, you should NOT init mintreesize and maxtreesize to the same value. — Thomas, Mar 24 '17 at 09:22
mittreesize and maxtreesize are initialized to the same value because the tree wasnt 'measured' yet — Jorge Canelhas, Mar 24 '17 at 17:11

Matt Timmermans · Accepted Answer · 2017-03-26T22:36:49.953

3

Calculating the tree depth is similar to evaluating the expression, but the operators calculate resulting depths instead of resulting values:

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

edited Mar 26 '17 at 22:36

answered Mar 26 '17 at 22:28

Matt Timmermans

53,709
3
46
87

score 0 · Answer 2 · answered Mar 26 '17 at 22:01

Well, just did a little of 'cheating' and used my rpn to infix converter to achieve the same goal, I post it here if anyone need it.

def getRPNdepth(expression):
    tmpexp = expression
    tmpfmla = [1 if n[0] == 'x' else n for n in tmpexp]
    stack = []
    for val in tmpfmla:
        if val!=' ':
            if val in ['-', '+', '*', '/']:
                op1 = stack.pop()
                op2 = stack.pop()
                stack.append('(' + str(op1) + str(val) + str(op2) + ')')
            else:
                stack.append(str(val))

    openparentesiscount=0
    maxopenparentesiscount = 0

    onlyparentesis=''
    for c in stack[0]:
        if c in ['(', ')']:
            onlyparentesis=onlyparentesis+c
            if c=='(':
                openparentesiscount=openparentesiscount+1
            else:
                openparentesiscount = openparentesiscount - 1
        if openparentesiscount>maxopenparentesiscount:
            maxopenparentesiscount=openparentesiscount

    return maxopenparentesiscount

Thanks all !

Get RPN tree size

2 Answers2