Luna Tech | Parse Tree(分析树)

March 7, 2021 字数 803 2 min


0. 相关文章

  1. Luna Tech | 聊聊数据类型(Data Type)
  2. Luna Tech | 聊聊数据结构(Data Structure)
  3. Luna Tech | 聊聊关联数组(Associative Array)
  4. Luna Tech | 聊聊树结构(Tree)
  5. Luna Tech | 聊聊自我平衡树(Self-balancing Tree)
  6. Luna Tech | 树结构的两种实现方式

1. Parse Tree(分析树)

Wikipedia: Parse Tree

如何用树结构解决实际的问题呢?

一个很贴切的例子就是计算器,数学表达式有运算顺序(从左到右)和运算优先级,假如把优先级高的运算符放在 root 附近,然后从底层往上计算,是不是就能很好地体现出运算顺序了呢?

首先,我们来分解表达式,一个数学表达式包含以下四个类别的元素:

  1. 左括号;
  2. 右括号;
  3. 数字;
  4. 运算符;

当我们遇到一个左括号时,就代表我们需要创建一棵树,当我们遇到右括号时,就代表括号内的运算结束了;

另外,每个运算符都有左边和右边两个数字,很像一个二叉树的 parent node 对不对呀~

所以,我们制定以下规则:

  1. 如果当前字符是左括号,在 current node 上加一个 left child,指针指向这个 left child node;
  2. 如果当前字符是运算符,把 current node 的 root value 设置为这个运算符,然后给 current node 添加一个 right child,指针指向这个 right child node;
  3. 如果当前字符是一个数字,把 current node 的 root value 设置为这个数字,然后返回 parent node;
  4. 如果当前字符是右括号,返回 parent node;

如何记录返回 parent node 的路径呢?用 stack 最方便啦,当我们往下走的时候,先把 current node push 到 stack,当我们需要向上回去的时候,就从 stack 里面 pop 出一个 node。


2. Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

# 前提:需要 implement stack 和 BinaryTree

def build_parse_tree(fp_expr):
    fp_list = fp_expr.split()
    p_stack = Stack()
    expr_tree = BinaryTree("")
    p_stack.push(expr_tree)
    current_tree = expr_tree

    for i in fp_list:
        if i == "(":
            current_tree.insert_left("")
            p_stack.push(current_tree)
            current_tree = current_tree.left_child

        elif i in ["+", "-", "*", "/"]:
            current_tree.root = i
            current_tree.insert_right("")
            p_stack.push(current_tree)
            current_tree = current_tree.right_child

        elif i == ")":
            current_tree = p_stack.pop()

        elif i not in ["+", "-", "*", "/", ")"]:
            try:
                current_tree.root = int(i)
                parent = p_stack.pop()
                current_tree = parent

            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))

    return expr_tree


pt = build_parse_tree("( ( 10 + 5 ) * 3 )")
pt.postorder()  # defined and explained in the next section

def evaluate(parse_tree):
    operators = {
        "+": operator.add,
        "-": operator.sub,
        "*": operator.mul,
        "/": operator.truediv,
    }

    left_child = parse_tree.left_child
    right_child = parse_tree.right_child

    if left_child and right_child:
        fn = operators[parse_tree.root]
        return fn(evaluate(left_child), evaluate(right_child))
    else:
        return parse_tree.root

Talk to Luna


Support Luna