发布于 

解析树| 笔记整理!

解析树| 笔记整理!

笔记心得

参考Python数据结构(外)

结构体部分 | 插入部分是必要的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, val='', left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    
    def insert_left(self,val=''):
        t=TreeNode(val)
        if not self.left:
            self.left=t
        else:
            t.left=self.left
            self.left=t
    def insert_right(self,val=''):
        t=TreeNode(val)
        if not self.right:
            self.right=t
        else:
            t.right=self.right
            self.right=t

进行建树 | 合理利用栈即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def build_parse_tree(s):
    ls=list(s)
    root=TreeNode()
    stk=[root]
    cur=root
    for i in ls:
        if i=='(':
            cur.insert_left() #进行占位
            stk.append(cur)
            cur=cur.left
        elif i not in '+-*/)':
            cur.val=int(i)
            cur=stk.pop()
        elif i in '+-*/':
            cur.val=i
            cur.insert_right()
            stk.append(cur)
            cur=cur.right
        elif i==')':
            cur=stk.pop()
        else:
            raise ValueError("当前输入不合法!")
    return root

计算解析树 | 递归处理

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_ans(root):
    map={
        '+':lambda x,y:x+y,
        '-':lambda x,y:x-y,
        '*':lambda x,y:x*y,
        '/':lambda x,y:x/y,
    }
    l=root.left
    r=root.right
    if l and r:
        return map[root.val](get_ans(l),get_ans(r))
    else:
        return root.val

遍历输出 | 利用中序遍历

这部分不自信 错了滴滴我

原书思路

1
2
3
4
5
def print_exp1(root):
    ans=''
    if root:
     ans='('+print_exp(root.left)+str(root.val)+print_exp(root.right)+')'
    return ans

优化

1
2
3
4
5
6
7
8
def print_exp2(root):
    ans=''
    if root:
        if root.left and root.right:
            ans='('+print_exp(root.left)+str(root.val)+print_exp(root.right)+')'
        else:
            ans=print_exp(root.left)+str(root.val)+print_exp(root.right)
    return ans

感觉还可以优化一下 | 根据优先级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def helper(root,flag):
    map={
        '+':1,'-':1,
        '*':2,'/':2
    }
    ans=''

    if root:
        ans=helper(root.left,flag)+str(root.val)+helper(root.right,flag)
        if root.left and root.right:
            if root.val in map and map[root.val]>=flag:
                flag=map[root.val]
                ans=helper(root.left,flag)+str(root.val)+helper(root.right,flag)
            else:
                ans='('+ans+')'
    return ans

感觉不是很难 | 2023.1.12

算法之路 不断精进!

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧