Python 扩展buildParseTree方法,使其能处理字符间没有空格的数学表达式。
时间: 2024-02-06 21:10:46 浏览: 38
要扩展Python的buildParseTree方法,使其能够处理没有空格的数学表达式,需要进行以下步骤:
1. 定义tokenize方法:该方法将输入的数学表达式分解为单个字符的令牌列表。在这里,需要考虑到没有空格的情况,因此需要注意如何划分数字和运算符。
2. 在buildParseTree方法中调用tokenize方法,将其返回的令牌列表作为参数传递给Expression类的实例化过程。
下面是一个示例代码,可以实现上述功能:
```python
from pythonds.basic import Stack
from pythonds.trees.binary import BinaryTree
import re
def tokenize(expr):
tokens = []
expr = re.findall('\d+|\+|\-|\*|\/|\(|\)', expr)
for token in expr:
if token.isdigit():
tokens.append(int(token))
else:
tokens.append(token)
return tokens
def buildParseTree(expr):
tokens = tokenize(expr)
stack = Stack()
tree = BinaryTree('')
stack.push(tree)
currentTree = tree
for token in tokens:
if token == '(':
currentTree.insertLeft('')
stack.push(currentTree)
currentTree = currentTree.getLeftChild()
elif token in ['+', '-', '*', '/']:
currentTree.setRootVal(token)
currentTree.insertRight('')
stack.push(currentTree)
currentTree = currentTree.getRightChild()
elif token == ')':
currentTree = stack.pop()
else:
try:
currentTree.setRootVal(int(token))
parent = stack.pop()
currentTree = parent
except ValueError:
raise ValueError("token '{}' is not a valid integer".format(token))
return tree
```
在上面的代码中,我们使用了正则表达式 `\d+|\+|\-|\*|\/|\(|\)` 来划分数字和运算符。其中 `\d+` 匹配一个或多个数字,`\+|\-|\*|\/|\(|\)` 匹配运算符和括号。在 `tokenize` 方法中,我们遍历表达式的每个字符,如果该字符是数字,则将其转换为整数并添加到令牌列表中;否则,直接将运算符或括号添加到令牌列表中。
在 `buildParseTree` 方法中,我们首先调用 `tokenize` 方法,将输入的数学表达式转换为令牌列表。然后,我们创建一个栈和一个空的二叉树。我们将该二叉树压入栈中,并将其设置为当前树。接下来,我们遍历令牌列表中的每个令牌。如果令牌是左括号,则在当前树的左侧插入一个空节点,并将当前树压入栈中。然后,将当前树设置为新插入的左子树。如果令牌是运算符,则将其设置为当前树的根节点,并在其右侧插入一个空节点。然后,将当前树压入栈中并将其设置为新插入的右子树。如果令牌是右括号,则从栈中弹出一个树,并将当前树设置为该树。如果令牌是数字,则将其设置为当前树的根节点,并从栈中弹出一个树作为父节点,然后将当前树设置为该父节点。如果令牌不是数字、左括号、右括号或运算符,则引发一个值错误。
最后,我们返回根节点所对应的树,即可得到构建好的解析树。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)