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