数据结构与算法

2024-07-14 03:07| 来源: 网络整理| 查看: 265

文章目录一、解析树二、解析树实例：表达式解析1. 建立表达式解析树（1）建立表达式解析树的规则（2）建立表达式解析树的思路（3）python代码实现 2. 表达式解析树的求值（1）增加程序可读性的技巧：函数引用（补充知识点）（2）python代码实现

一、解析树

树结构可以用来分析句子的各种语法成分，对句子的各种成分进行处理。比如：

语法分析树：主谓宾，定状补；程序设计语言的编译：词法、语法的检查，从语法树生成目标代码；自然语言处理：机器翻译、语义理解。

举例来说，对于表达式 ( ( 7 + 3 ) ∗ ( 5 − 2 ) ) ((7+3)*(5-2)) ((7+3)∗(5−2))的解析：我们还可以将表达式表示为树结构，叶节点保存操作数，内部节点保存操作符。

在这里插入图片描述

由于括号的存在，需要计算*的话，就必须先计算7+3和5-2。因此，表达式层次决定计算的优先级，越底层的表达式，优先级越高。

树中每个子树都表示一个子表达式，将子树替换为子表达式值的节点，即可实现求值。替换后的结果如下图：

在这里插入图片描述

二、解析树实例：表达式解析

下面，我们用树结构来做如下尝试：

从全括号表达式构建表达式解析树；

利用表达式解析树对表达式求值；

从表达式解析树恢复原表达式的字符串形式。

1. 建立表达式解析树

首先，全括号表达式要分解为单词Token列表，其单词分为括号“( )”、操作符“+ - * /”和操作数“0～9”这几类。左括号就是表达式的开始，而右括号是表达式的结束。

比如：3+(4*5)，分解后的单词Token列表为：['(', '3', '+', '(', '4', '*', '5', ')', ')']。

创建表达式解析树过程：

创建空树，当前节点为根节点；

在这里插入图片描述

读入’(’，创建了左子节点，当前节点下降；

在这里插入图片描述

读入’3’，当前节点设置为3，上升到父节点；

在这里插入图片描述

读入’+’，当前节点设置为+，创建右子节点，当前节点下降；

在这里插入图片描述

读入’(’，创建左子节点，当前节点下降；

在这里插入图片描述

读入’4’，当前节点设置为4，上升到父节点；

在这里插入图片描述

读入’’，当前节点设置为，创建右子节点，当前节点下降。

在这里插入图片描述

读入’5’，当前节点设置为5，上升到父节点；

在这里插入图片描述

读入’)’，上升到父节点；

读入’)’，再上升到父节点。

（1）建立表达式解析树的规则从左到右扫描全括号表达式的每个单词，依据规则建立解析树；如果当前单词是"("：为当前节点添加一个新节点作为其左子节点，当前节点下降为这个新节点；如果当前单词是操作符"+,-,/,*"：将当前节点的值设为此符号，为当前节点添加一个新节点作，为其右子节点，当前节点下降为这个新节点；如果当前单词是操作数：将当前节点的值设为此数，当前节点上升到父节点；如果当前单词是")"：则当前节点上升到父节点。（2）建立表达式解析树的思路

从图示过程中我们看到，创建树过程中关键的是对当前节点的跟踪。我们之前用代码实现过树结构，创建左右子树可调用insert_left/right，当前节点设置值，可以调用set_root_val，下降到左右子树可调用get_left/tight_child。但是，上升到父节点，没有方法支持！

所以，用我们一个栈来记录跟踪父节点：当前节点下降时，将下降前的节点push入栈。当前节点需要上升到父节点时，上升到pop出栈的节点即可！

（3）python代码实现 def build_parse_tree(fpexp): # 创建单词列表 fplist = fpexp.split() pStack = Stack() eTree = BinaryTree("") # 将父（根）节点入栈 pStack.push(eTree) # 当前节点下降，指向刚刚建立的节点 currentTree = eTree # 左到右扫描列表中的每个单词 for i in fplist: # 表达式开始 if i == "(": # 创建当前节点的左子节点 currentTree.insert_left("") # 当前节点入栈 pStack.push(currentTree) # 当前节点下降，指向左子节点 currentTree = currentTree.get_left_child() # 操作符 elif i in ["+", "-", "*", "/"]: # 将操作符放入当前节点的根（父）节点 currentTree.set_root_val(i) # 创建当前节点的右子节点 currentTree.insert_right("") # 当前节点入栈 pStack.push(currentTree) # 当前节点下降，指向右子节点 currentTree = currentTree.get_right_child() # 表达式结束 elif i == ")": # 当前节点上升降，指向父节点 currentTree = pStack.pop() # 剩余的为操作数或其他单词 elif i not in ["+", "-", "*", "/", ")"]: # 尝试将操作数放入当前节点的父节点，并将当前节点上升，指向父节点 try: currentTree.set_root_val(int(i)) parent = pStack.pop() currentTree = parent # 说明单词是非法的，抛出异常 except ValueError: raise ValueError("token '{}' is not a valid integer".format(i)) # 返回解析树 return eTree 2. 表达式解析树的求值

创建了表达式解析树，接下来就可以来进行求值了。由于二叉树BinaryTree是一个递归数据结构，多以可以用递归算法来处理。由前述对子表达式的描述可知，越底层的表达式会越先求值，所以，可从树的底层子树开始，逐步向上层求值，最终得到整个表达式的值。

求值函数evaluate的递归三要素：

基本结束条件：叶节点是最简单的子树，没有左右子节点，其根节点的数据项，即为子表达式树的值；缩小规模：将表达式树分为左子树、右子树，即为缩小规模；调用自身：分别调用evaluate计算左子树和右子树的值，然后将左右子树的值依根节点的操作符进行计算，从而得到表达式的值。（1）增加程序可读性的技巧：函数引用（补充知识点） import operator # 该模块提供了一套与Python的内置运算符对应的高效率函数 op = operator.add op(1, 2) # 等价于：operator.add(1, 2)和1+2 # 返回：3 （2）python代码实现 import operator def evaluate(parseTree): # 运算符与对应函数的映射字典 opers = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv, } # 获取左右子节点 leftC = parseTree.get_left_child() rightC = parseTree.get_right_child() # 如果左右子节点存在，说明没有到达解析树的最底层，还需继续递归分解 if leftC and rightC: # 获取运算符，得到对应运算函数 fn = opers[parseTree.get_root_val()] # 将递归调用的返回值，交给运算符对应的函数进行运算 return fn(evaluate(leftC), evaluate(rightC)) # 如果没有子节点，说明到达了解析树的最底层（递归出口） else: return parseTree.get_root_val()

【本文地址】

公司简介

联系我们