- import re
- import fractions
- import math
- import sys
- level = 0
- line = 1
- class node:
- def __init__(self, category=0):
- self.operator = ''
- ## category=1 : leaf node
- ## category=0 : intermediate node
- self.category = category
- self.leftChild = None
- self.rightChild = None
- self.parent = None
- self.bracelet = False
- self.value = ''
- self.result = ''
- def popStack(subOpStack, subNumStack):
- if len(subOpStack) == 0:
- temp = subNumStack.pop()
- return temp
- else:
- temp = node(0)
- temp.value = subOpStack.pop()
- tmp = subNumStack.pop()
- temp.rightChild = tmp
- temp.rightChild.parent = temp
- temp.leftChild = popStack(subOpStack, subNumStack)
- temp.leftChild.parent = temp
- return temp
- def depthTree(temp):
- if temp.leftChild == None or temp.rightChild == None:
- return 0
- leftLen = depthTree(temp.leftChild) + 1
- rightLen = depthTree(temp.rightChild) + 1
- return max(leftLen, rightLen)
- def parseTree(opStack, numStack, subOpStack, subNumStack):
- global level
- if len(opStack) == 0:
- if (len(numStack) > 0):
- nn = numStack.pop()
- subNumStack.insert(0, nn)
- localNode = popStack(subOpStack, subNumStack)
- return localNode
- op = opStack.pop()
- if (op in "+-"):
- localNode = node()
- localNode.value = op
- nn = numStack.pop()
- subNumStack.insert(0, nn)
- localNode.rightChild = popStack(subOpStack, subNumStack)
- localNode.leftChild = parseTree(opStack, numStack, subOpStack, subNumStack)
- localNode.rightChild.parent = localNode
- localNode.leftChild.parent = localNode
- return localNode
- elif (op in "*/"):
- nn = numStack.pop()
- subNumStack.insert(0, nn)
- subOpStack.insert(0, op)
- res = parseTree(opStack, numStack, subOpStack, subNumStack)
- return res
- elif (op == ")"):
- numStack1 = []
- opStack1 = []
- subOpStack1 = []
- subNumStack1 = []
- flag = True
- while flag:
- op = opStack.pop()
- if op == ")":
- level = level + 1
- opStack1.insert(0, op)
- elif op == "(":
- if level == 0:
- nn = numStack.pop()
- numStack1.insert(0, nn)
- flag = False
- break;
- else:
- level = level - 1
- opStack1.insert(0, op)
- else:
- opStack1.insert(0, op)
- nn = numStack.pop()
- numStack1.insert(0, nn)
- res = parseTree(opStack1, numStack1, subOpStack1, subNumStack1)
- res.bracelet = True
- numStack.append(res)
- res = parseTree(opStack, numStack, subOpStack, subNumStack)
- return res
- def calculateExpress(expr, subExpr):
- if subExpr==None:
- return
- calculateExpress(expr, subExpr.leftChild)
- calculateExpress(expr, subExpr.rightChild)
- if (not subExpr.leftChild==None and not subExpr.leftChild==None and subExpr.leftChild.category == 1 and subExpr.rightChild.category == 1):
- left = fractions.Fraction(subExpr.leftChild.value)
- right = fractions.Fraction(subExpr.rightChild.value)
- op = subExpr.value
- if op=="+":
- result = left + right
- elif op=="-":
- result = left - right
- elif op=="*":
- result = left * right
- elif op=="/":
- result = left / right
- subExpr.category = 1
- subExpr.value = str(result)
- subExpr.bracelet = False
- subExpr.leftChild = None
- subExpr.rightChild = None
- outputExpress(expr)
- return
- def outputExpress(expr):
- global line
- print str(line)+":\\t",
- printExpress(expr)
- line = line + 1
- return
- def printExpress(expr):
- if expr == None:
- return
- if expr.bracelet:
- print "(",
- printExpress(expr.leftChild)
- print expr.value,
- printExpress(expr.rightChild)
- if expr.bracelet:
- print ")",
- return
- if __name__ == '__main__':
- str1 = '(1/9+1/8*(1/7+1/6)+1/9)/(1/2+(1/4+1/3)*1/2/(1/4+1/5))+1/2'
- pattern = '[\\(\\)\\+\\-\\*\\/]|\\d+/\\d+'
- result = re.findall(pattern, str1)
- operators = '()+-*/'
- opStack = []
- numStack = []
- subNumStack = []
- subOpStack = []
- for item in result:
- if item in operators:
- opStack.append(item)
- else:
- tmp = node(1)
- tmp.value = item
- numStack.append(tmp)
- oo = parseTree(opStack, numStack, subOpStack, subNumStack)
- calculateExpress(oo,oo)
- #该片段来自于http://www.codesnippet.cn/detail/300820135500.html
来源: http://www.codesnippet.cn/detail/300820135500.html