Python 扩展buildParseTree方法,使其能处理字符间没有空格的数学表达式。
时间: 2024-02-03 12:12:50 浏览: 19
可以使用Python中的正则表达式和栈来实现处理字符间没有空格的数学表达式的解析树。
首先,需要导入re模块和Stack类:
```python
import re
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
```
然后,可以定义一个函数build_parse_tree,接受一个表示数学表达式的字符串作为参数,返回一个解析树的根节点。
```python
def build_parse_tree(expr):
tokens = re.findall('\d+|\+|\-|\*|\/|\(|\)', expr.replace(' ', ''))
# 用栈来追踪父节点和子节点
stack = Stack()
# 创建根节点,将其压入栈中
root = TreeNode('')
stack.push(root)
# 迭代所有的token
for token in tokens:
if token == '(':
# 如果是左括号,创建一个新的节点作为当前节点的左子节点,将当前节点压入栈中
current_node = TreeNode('')
stack.peek().left_child = current_node
stack.push(current_node)
elif token in ['+', '-', '*', '/']:
# 如果是运算符,创建一个新的节点作为当前节点的值,将其作为当前节点的右子节点,将当前节点压入栈中
current_node = TreeNode(token)
stack.peek().set_root_val(token)
stack.peek().right_child = current_node
stack.push(current_node)
elif token == ')':
# 如果是右括号,弹出栈中的当前节点
stack.pop()
else:
# 如果是数字,创建一个新的节点作为当前节点的值,弹出栈中的当前节点
current_node = TreeNode(int(token))
parent = stack.peek()
if parent.left_child is None:
parent.left_child = current_node
else:
parent.right_child = current_node
stack.pop()
return root
```
这里使用re.findall方法来将表达式字符串解析为一个token列表,然后使用栈来构建解析树。每次遇到左括号时,就创建一个新的节点作为当前节点的左子节点,并将当前节点压入栈中。每次遇到运算符时,就创建一个新的节点作为当前节点的值,并将其作为当前节点的右子节点,然后将当前节点压入栈中。每次遇到右括号时,就弹出栈中的当前节点。最后,返回根节点。
可以使用以下代码测试:
```python
pt = build_parse_tree("3+4*5/(6-2)")
pt.postorder() # 输出:3 4 5 * 6 2 - / +
```
输出的结果表明解析树的构建是正确的。
注:这里使用了自定义的TreeNode类来表示解析树的节点。TreeNode类的实现可以参考以下代码:
```python
class TreeNode:
def __init__(self, val):
self.left_child = None
self.right_child = None
self.val = val
def set_root_val(self, obj):
self.val = obj
def get_root_val(self):
return self.val
def get_left_child(self):
return self.left_child
def get_right_child(self):
return self.right_child
def insert_left(self, new_node):
if self.left_child is None:
self.left_child = TreeNode(new_node)
else:
t = TreeNode(new_node)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, new_node):
if self.right_child is None:
self.right_child = TreeNode(new_node)
else:
t = TreeNode(new_node)
t.right_child = self.right_child
self.right_child = t
def postorder(self):
if self.left_child:
self.left_child.postorder()
if self.right_child:
self.right_child.postorder()
print(self.val, end=" ")
```