Parse Tree（分析树）
2021-03-07
0. 相关文章
- 聊聊数据类型（Data Type）
- 聊聊数据结构（Data Structure）
- 聊聊关联数组（Associative Array）
- 聊聊树结构（Tree）
- 聊聊自我平衡树（Self-balancing Tree）
- 树结构的两种实现方式
1. Parse Tree（分析树）
如何用树结构解决实际的问题呢？
一个很贴切的例子就是计算器，数学表达式有运算顺序（从左到右）和运算优先级，假如把优先级高的运算符放在 root 附近，然后从底层往上计算，是不是就能很好地体现出运算顺序了呢？
首先，我们来分解表达式，一个数学表达式包含以下四个类别的元素：
- 左括号；
- 右括号；
- 数字；
- 运算符；
当我们遇到一个左括号时，就代表我们需要创建一棵树，当我们遇到右括号时，就代表括号内的运算结束了；
另外，每个运算符都有左边和右边两个数字，很像一个二叉树的 parent node 对不对呀~
所以，我们制定以下规则：
- 如果当前字符是左括号，在 current node 上加一个 left child，指针指向这个 left child node；
- 如果当前字符是运算符，把 current node 的 root value 设置为这个运算符，然后给 current node 添加一个 right child，指针指向这个 right child node；
- 如果当前字符是一个数字，把 current node 的 root value 设置为这个数字，然后返回 parent node；
- 如果当前字符是右括号，返回 parent node；
如何记录返回 parent node 的路径呢？用 stack 最方便啦，当我们往下走的时候，先把 current node push 到 stack，当我们需要向上回去的时候，就从 stack 里面 pop 出一个 node。
2. Code
# 前提：需要 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