博客

python 二叉树-解析四则运算公式

1、解析树

• 根据括号构建解析数
• 计算解析树中的表达式
• 将解析树还原为最初的数学表达式

构建表达式 **((7+3)*(8-6))**的解析树

先算加减，后算乘法

在计算顶层的乘法前， 需要先计算子树中的加法和减法， 计算完之后使用记过替代整颗子树

构建解析树规则

• 如果标记是 (， 为当前节点创建一个子节点， 并下沉至该节点
• 如果当前标记在列表[“+”, “-”, “/”, “*”], 将当前节点的值设置为当前标记对应的运算符；为当前节点穿件一个右节点并下沉至该节点
• 如果当前值是是数值， 就将当前节点的数值设置为该数值并返回至父节点
• 如果标记是), 则跳到当前节点的父节点

完全括号表达式

对每一对运算符都添加一对括号， 由括号决定运算顺序， 杜绝歧义， 并且不需要记忆运算规则

2、解析四则运算-Coding

BuildParseTree 类：解析并计算公式

# -*- coding: utf-8 -*-
import operator

class BuildParseTree:


    def __init__(self, fpexp):
        self.fplist = fpexp.split()

    def buildParseTree(self):
        """
        构建解析树
        使用栈来保存父节点
        """
        pStack = Stack()
        eTree = BinaryTree('')
        pStack.push(eTree)
        curentTree = eTree
        for i in self.fplist:
            # 如果标记是 (， 为当前节点创建一个子节点， 并下沉至该节点
            if i == "(":

                curentTree.insertLeft("")
                pStack.push(curentTree)
                curentTree = curentTree.getLeftChild()