算数表达式最外边带括号,例子如图
,如何转化为二叉树并计算?表达式怎么用递归定义?
算数表达式最外边带括号,例子如图
class Treenode:
def __init__(self,x):
self.val=x
self.left=self.right=None
def calculate(s):
"""
:type s: str
:rtype: int
"""
def buildTree(s):
n=len(s)
if n==1:return Treenode(s[0])
k,p=-1,0
for i in range(n):
c=s[i]
if c=='(':
p+=1
elif c==')':
p-=1
elif c in ('+','-','*','/'):
if p==0:k=i
if k<0:return buildTree(s[1:-1])
root=Treenode(s[k])
root.left=buildTree(s[:k])
root.right=buildTree(s[k+1:])
return root
def f(root):
if root.left==None:return int(root.val)
l=f(root.left)
r=f(root.right)
if root.val=='+':return l+r
return l-r
t,i=[],0
while i<len(s):
c=s[i]
if c in '()+-*//':
t.append(c)
i+=1
elif c==' ':
i+=1
else:
k=i
while i<len(s) and s[i] in '0123456789':i+=1
t.append(s[k:i])
print(t)
root=buildTree(t)
return f(root)
print(calculate('2+3*(4-1)-5/1'))