如何将一个将输入的数学表达式自动转化为二叉树并计算结果？(语言-python)

Question

算数表达式最外边带括号，例子如图

，如何转化为二叉树并计算？表达式怎么用递归定义？

Answer 1

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