设计python程序将下列表达式转换为二叉树
要设计一个python程序，它可以在用户将数学表达式作为输入输入后自动将其转换为二叉树。表达式的格式要与上述图片相同，可以递归。定义如下：并且它必须由（x？y）组成，其中x和y要么是数字要么是其他有效的表达式，？代表运算符（*，/，+，-）
昨天刚做过，你是要什么样的输出？
class Treenode:
def __init__(self,x):
self.val=x
self.left=self.right=None
def calculate(s):
"""
:type s: str
:rtype: int
"""
def buildTree(s):
n=len(s)
if n==1:return Treenode(s[0])
k,p=-1,0
for i in range(n):
c=s[i]
if c=='(':
p+=1
elif c==')':
p-=1
elif c in ('+','-','*','/'):
if p==0:k=i
if k<0:return buildTree(s[1:-1])
root=Treenode(s[k])
root.left=buildTree(s[:k])
root.right=buildTree(s[k+1:])
return root
def f(root):
if root.left==None:return int(root.val)
l=f(root.left)
r=f(root.right)
if root.val=='+':return l+r
return l-r
t,i=[],0
while i<len(s):
c=s[i]
if c in '()+-*//':
t.append(c)
i+=1
elif c==' ':
i+=1
else:
k=i
while i<len(s) and s[i] in '0123456789':i+=1
t.append(s[k:i])
print(t)
root=buildTree(t)
return f(root)
print(calculate('2+3*(4-1)-5/1'))
我写个吧，可以构建树，也可以根据构建的树计算值。验证了表达式结果
# -*- coding: utf-8 -*-
import operator
class BinaryTree:
def __init__(self, rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self, newNode):
if self.leftChild is None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self, newNode):
if self.rightChild is 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 getRootVal(self):
return self.key
def setRootVal(self, obj):
self.key = obj
class Stack():
def __init__(self):
self.items = list()
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
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()
elif i not in "=-*/":
curentTree.setRootVal(eval(i))
parent = pStack.pop()
curentTree = parent
elif i in "=-*/":
curentTree.setRootVal(eval(i))
curentTree.insertRight("")
pStack.push(curentTree)
curentTree.getRightChild()
elif i == ")":
parent = pStack.pop()
curentTree = parent
else:
raise ValueError("Error: %s" % i)
return eTree
def evaluate(self, 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(self.evaluate(leftC), self.evaluate(rightC))
else:
return parseTree.getRootVal()
if __name__ == "__main__":
formulas = "(((5+2)*(2-1))/((2+9)+((7-2)-1))*8)"
fTree = BuildParseTree(formulas)
eTree = fTree.buildParseTree() ##构建树
value = fTree.evaluate(eTree) ##计算值
print("%s = " % formulas, value)
使用了第三方库binarytree作二叉树的【字符图】输出，没安装的安装一下： pip install binarytree
class bTree:
def __init__(self, data=None, lchild=None, rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
def __repr__(self):
if self.lchild is None and self.rchild is None:
return f'{self.data}'
return f'({self.lchild} {self.data} {self.rchild})'
def build(exp):
ss = bTree.postExp(exp)
t,r = [],[]
for i in ss:
if str(i) not in '+-/*':
t.append(i)
else:
if len(t)==0:
n1 = r.pop()
n2 = r.pop()
elif len(t)==1:
n1 = bTree(t.pop())
n2 = r.pop()
elif len(t)==2:
n1 = bTree(t.pop())
n2 = bTree(t.pop())
r.append(bTree(i,n2,n1))
return r[0]
def trueExp(exp):
try:
eval(exp)
return True
except:
#raise SyntaxError('表达式错误!')
return False
def postExp(exp):
res, ops = [], []
EXP = ['+', '-', '*', '/']
exp = exp.replace(' ','')
ss = list(exp)
for i in ss:
if i in EXP:
while len(ops) >= 0:
if len(ops) == 0:
ops.append(i)
break
op = ops.pop()
if op == '(' or EXP.index(i)//2 > EXP.index(op)//2:
ops.append(op) # 运算优先级
ops.append(i)
break
else:
res.append(op)
elif i == '(': # 左括号，直接入操作符栈
ops.append(i)
elif i == ')': # 右括号，循环出栈道
while len(ops) > 0:
op = ops.pop()
if op == '(':
break
else:
res.append(op)
else:
res.append(int(i)) # 数值，直接入表达式栈
while ops:
res.append(ops.pop())
return res
def calcExp(exp):
res = []
for ex in exp:
if ex in ['+', '-', '*', '/']:
n2 = res.pop()
n1 = res.pop()
res.append(eval(str(n1)+ex+str(n2)))
else:
res.append(ex)
return res[0]
@property
def size(self):
t = str(self)
for i in '( )':
t = t.replace(i,'')
return len(t)
@property
def value(self):
res = []
for ex in self.postOrder():
if ex in ['+', '-', '*', '/']:
n2 = res.pop()
n1 = res.pop()
res.append(eval(str(n1)+ex+str(n2)))
else:
res.append(ex)
return res[0]
@property
def preList(self):
return self.preOrder()
@property
def inList(self):
return self.inOrder()
@property
def postList(self):
return self.postOrder()
def preOrder(self, res=[]):
'''前序遍历'''
if not self: return []
return [self.data]+bTree.preOrder(self.lchild)+bTree.preOrder(self.rchild)
def inOrder(self, res=[]):
'''中序遍历'''
if not self: return []
return bTree.inOrder(self.lchild)+[self.data]+bTree.inOrder(self.rchild)
def postOrder(self, res=[]):
'''后序遍历'''
if not self: return []
return bTree.postOrder(self.lchild)+bTree.postOrder(self.rchild)+[self.data]
def levelOrder(self):
'''层序遍历'''
que = __import__('queue').Queue()
que.put(self)
res = []
while not que.empty() :
n = que.get()
res.append(n.data)
if n.lchild is not None :
que.put(n.lchild)
if n.rchild is not None :
que.put(n.rchild)
return res
def Height(self):
if not self: return 0
lH = bTree.Height(self.lchild)
rH = bTree.Height(self.rchild)
return max(lH,rH)+1
@property
def height(self):
return self.Height()
@property
def values(self):
res = [['self']]
for i in range(self.height-1):
t = []
for j in res[-1]:
t.append(j+'.lchild')
t.append(j+'.rchild')
res.append(t)
res = sum(res,[])
for i,n in enumerate(res):
try:
res[i] = eval(n+'.data')
except:
res[i] = None
for i in range(len(res)):
if res[i] in list('+-*/'):
res[i] = list('+-*/').index(res[i])+101
return res
@property
def Values(self):
que = __import__('queue').Queue()
que.put(self)
res = []
while not que.empty() :
n = que.get()
res.append(n.data)
t = False
if n.lchild is not None :
que.put(n.lchild)
else:
t = True
if n.rchild is not None :
que.put(n.rchild)
else:
t = True
if t: res.append(None)
'''
for i in range(len(res)):
if res[i] in list('+-*/'):
res[i] = list('+-*/').index(res[i])+101
'''
return res
def print(self):
import binarytree as tree
tree.build(self.values).pprint()
s = '((( 5 +2)* (2 - 1 ) /((2+9)+((7-2)-1))*8))'
# 校验表达式是否正确
if bTree.trueExp(s):
bt = bTree.build(s)
else:
raise SyntaxError('表达式错误!')
print('字符串：', s)
print('二叉树：', bt)
print('\n前序遍历：',bt.preOrder())
print('中序遍历：', bt.inOrder() )
print('后序遍历：', bt.postOrder())
print('层序遍历：', bt.levelOrder())
print('校验后序遍历是否正确：',bt.postOrder() == bTree.postExp(s))
print('\n表达式的值：', bt.value)
print('校验表达式计算是否正确：',bt.value == eval(s))
print('\n二叉树图形化输出(+-*/分别用101、102、103、104表示)：')
bt.print()
print('\n测试另一个：')
a = '(((5+2))/((2+9)+((7-2)-1)))*8)+(5*2+1)'
at = bTree.build(a)
print(a)
print(at)
at.print()
测试结果：
=========================== RESTART: D:\binTree.py ===========================
字符串： ((( 5 +2)* (2 - 1 ) /((2+9)+((7-2)-1))*8))
二叉树： ((((5 + 2) * (2 - 1)) / ((2 + 9) + ((7 - 2) - 1))) * 8)
前序遍历： ['*', '/', '*', '+', 5, 2, '-', 2, 1, '+', '+', 2, 9, '-', '-', 7, 2, 1, 8]
中序遍历： [5, '+', 2, '*', 2, '-', 1, '/', 2, '+', 9, '+', 7, '-', 2, '-', 1, '*', 8]
后序遍历： [5, 2, '+', 2, 1, '-', '*', 2, 9, '+', 7, 2, '-', 1, '-', '+', '/', 8, '*']
层序遍历： ['*', '/', 8, '*', '+', '+', '-', '+', '-', 5, 2, 2, 1, 2, 9, '-', 1, 7, 2]
校验后序遍历是否正确： True
表达式的值： 3.7333333333333334
校验表达式计算是否正确： True
二叉树图形化输出(+-*/分别用101、102、103、104表示)：
___________________________103
/ \
_________104_________ 8
/ \
___103___ ___101_________
/ \ / \
101 102 101 ___102
/ \ / \ / \ / \
5 2 2 1 2 9 102 1
/ \
7 2
测试另一个：
(((5+2))/((2+9)+((7-2)-1)))*8)+(5*2+1)
((((5 + 2) / ((2 + 9) + ((7 - 2) - 1))) * 8) + ((5 * 2) + 1))
___101_________
/ \
___________________________103 ___101
/ \ / \
___104_________ 8 103 1
/ \ / \
101 ___101_________ 5 2
/ \ / \
5 2 101 ___102
/ \ / \
2 9 102 1
/ \
7 2