Python 程序构建给定表达式的表达式树
pythonserver side programmingprogramming更新于 2024/2/18 18:36:00
表达式树是叶节点具有要操作的值，内部节点包含将对其执行叶节点的运算符的树。
示例:4 + ((7 + 9) * 2) 将具有如下表达式树 -
解决此问题的方法
为了为给定表达式构建表达式树，我们通常使用堆栈数据结构。首先，我们迭代给定的后缀表达式，并按照以下步骤进行操作 -
- 如果我们在给定的表达式中获得一个操作数，则将其推送到堆栈中。它将成为表达式树的根。
- 如果运算符在表达式中获得两个值，则将其添加到表达式树中作为其子节点，并将它们推送到当前节点。
- 重复步骤 1 和步骤 2，直到我们无法完成给定的表达式。
示例
class stack: def __init__(self): self.arr = [] def push(self, data): self.arr.append(data) def pop(self): try: return self.arr.pop(-1) except: pass def top(self): try: return self.arr[-1] except: pass def size(self): return len(self.arr) # 表达式树的节点类 class node: def __init__(self, data): self.data = data self.left = None self.right = None # 表达式树类 class exp_tree: def __init__(self, postfix_exp): self.exp = postfix_exp self.root = None self.createTree(self.exp) def isOperator(self, char): optr = [" ", "-", "*", "/", "^"] if char in optr: # 如果给定的 char 是运算符 return True # 然后返回 true return False # 否则返回 false def createTree(self, exp): s = stack() # 存储所有子节点为 NULL 的运算符节点 self.root = node(exp[-1]) # 后缀表达式的最后一个字符始终是运算符 s.push(self.root) # 继续执行后缀表达式的其余部分 for i in "".join(reversed(exp[:-1])): curr_node = s.top() if not curr_node.right: # 如果当前节点的右节点为 NULL temp = node(i) curr_node.right = temp if self.isOperator(i): s.push(temp) else: # 如果当前节点的左节点为 NULL temp = node(i) curr_node.left = temp # 如果当前节点的所有子节点都不为 NULL s.pop() # 从堆栈中弹出当前节点 if self.isOperator(i): s.push(temp) def inorder(self, head): # 表达式树的中序遍历 # 中序遍历 = > left, root, right if head.left: self.inorder(head.left) print(head.data, end=" ") if head.right: self.inorder(head.right) def infixExp(self): # 表达式树的中序遍历给出中缀表达式 self.inorder(self.root) print() if __name__ == "__main__": postfixExp = "ab ef*g*-" et = exp_tree(postfixExp) et.infixExp()
运行上述代码将生成如下输出，
输出
(a + b - e * f * g)
解释:
根据给定的表达式构建树将生成输出，使得操作数将成为节点的根，其余数字将成为表达式树的子节点。
