二叉树ParseTree

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
        
#在开始之前，先初始化一个空的根节点
#1.如果目前的符号是“（”，为当前的节点增加一个左孩子节点，并下降来到左孩子节点
#2.如果目前的符号是[+，-，*，/]，将当前节点的值设置为该符号，并且为当前节点增加一个右孩子节点，并下降来到右孩子节点
#3.如果目前的符号是一个数字，将当前节点的值设置为该数字，并返回它的父亲节点
#4.如果目前的符号是“）”，返回当前节点的父亲节点
from myStack import *
from tree import *
def buildParseTree(expression):
    expressionList = []
    for i in expression:#将原表达式转换为列表，便于处理每一个字符
        expressionList.append(i)
    indexStack = Stack()#用于存储父节点，必要的时候拿出来返回
    parseTree  = BinaryTree(‘‘)#先初始化一个空的根节点
    indexStack.push(parseTree)
    currentNode = parseTree

    for i in expressionList:
        if i == ‘(‘:
            currentNode.insertLeft(‘‘)
            indexStack.push(currentNode)
            currentNode = currentNode.getLeftChild()
        elif i in [‘+‘,‘-‘,‘*‘,‘/‘]:
            currentNode.setRootVal(i)
            currentNode.insertRight(‘‘)
            indexStack.push(currentNode)
            currentNode = currentNode.getRightChild()
        elif i not in [‘)‘,‘+‘,‘-‘,‘*‘,‘/‘]:
            currentNode.setRootVal(int(i))
            parent = indexStack.pop()

            currentNode = parent
        else:
            currentNode = indexStack.pop()

    return parseTree

def evaluate(parseTree):
    signals = [‘+‘,‘-‘,‘*‘,‘/‘]
    if parseTree.getLeftChild() and parseTree.getRightChild():
        leftNumber = evaluate(parseTree.getLeftChild())
        rightNumber = evaluate(parseTree.getRightChild())
        signal = parseTree.getRootVal()
        if signals.index(signal) == 0:
            return leftNumber + rightNumber
        elif signals.index(signal) == 1:
            return leftNumber - rightNumber
        elif signals.index(signal) == 2:
            return leftNumber * rightNumber
        else:
            return leftNumber/rightNumber
    else:
        return parseTree.getRootVal()

二叉树ParseTree

原文：http://my.oschina.net/stevenKelly/blog/391653