利用表达式解析树求值

class BinaryTree:
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t
    def getRightChild(self):
        return self.rightChild
    def getLeftChild(self):
        return self.leftChild
    def setRootVal(self, obj):
        self.key = obj
    def getRootVal(self):
        return self.key
r = BinaryTree("A")
r.insertLeft("B")
print(r.getLeftChild())
from pythonds.basic.stack import Stack
'''
建立表达式解析树
如果当前的单词是 ( ,为当前节点创建一个新节点作为其左子节点。当前节点下降为这个新节点.
如果当前节点是 ),上升到父节点,
当前节点是 操作符号,将当前节点的值设置为 此符号，在当前节点添加一个新节点作为其右子节点，当前节点下降为这个新节点
当前节点是 操作数，当前节点的值设为此数，当前节点上升到父节点
'''
def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree
    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i == ")":
            currentTree = pStack.pop()
        elif i in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()#第一次搞反了。
        elif i not in ['+', '-', '*', '/', ')']:
            currentTree.setRootVal(int(i))
            parent = pStack.pop()
            currentTree = parent
        else:
            raise  ValueError
    return eTree

#利用表达式解析树求值
import operator
def evaluate(parseTree):
    opers = {'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}
    leftC = parseTree.getLeftChild()
    rightC = parseTree.getRightChild()
    if leftC and rightC:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootVal()
if __name__ == '__main__':
    fpexp = '( 3 * ( 4 + 5 ) )'
    parseTree = buildParseTree(fpexp)
    result = evaluate(parseTree)
    print(result)
    #print(fpexp.split())