Expression Tree即表达式树，专门用于计算表达式。例如，3-(4+5)，转化成list形式，即['3','-','(','4','+','5',')']，其表达式树为：
-
/
3 +
/
4 5
这样安排的好处是，这棵树的后续遍历就是逆波兰表达式，即[3,4,5,+,-]。由逆波兰表达式即可进行计算。
表达式树的关键在于生成，生成是根据优先度来决定的。对于普通的加减乘除表达式，有以下规定：
- 数字的优先度是最大的；
- +-优先度为+1
- */优先度为+2
- 遇到'('，优先度+10；遇到')'，优先度减10
则例子中的优先度list是[max, 1, max, 11, max]。把括号从计算当中去除。
那么，相当于把表达式转换成为了一个最小树，优先度最小的在上面，优先度最大的数字在叶子节点上。
而对于生成最大/最小树，有一个很优雅的解法： - 新建一个stk，然后对优先度list遍历；
- 对于一个元素n，每当stk之前的元素比其大，就将其作为n的左子树，直至stk为空，或者遇到一个比n小的元素，此时就把n作为其右子树；
- 直至遍历结束，返回stk[0]即可。
要实现“一条龙服务”，需要以下功能： - 从字符串表达式到表达式的list形式；T:O(n) S:O(n)
- 从表达式list到表达式树；T:O(n) S:O(n)
- 对表达式树后序遍历获得逆波兰表达式；T:O(n) S:O(n)
- 对逆波兰表达式进行计算。T:O(n) S:O(n)
总体复杂度T:O(n) S:O(n)。虽然有点长，但是解决了不少表达式计算的问题。代码如下：
class MyTreeNode:
def __init__(self, val, s):
self.left = None
self.right = None
self.val = val
self.s = s
maxint = 0x7fffffff
class ExpressionTree:
# convert the str expression to the list form
def convert(self, s):
if not s:
return []
ret = []
i = 0
while i < len(s):
if s[i] in ['+','-','*','/','(',')']:
ret.append(s[i])
i += 1
else:
j = i
while j < len(s) and s[j] not in ['+','-','*','/','(',')']:
j += 1
ret.append(s[i:j])
i = j
return ret
# build theexpression tree using the expression list
def build(self, expression):
# writeyour code here
return self.create_tree(expression)
# calculate theexpression value using the expression tree
def calculate(self, node):
exp = []
self.postOrder(node, exp)
operands, operators= [], []
for i in range(len(exp)):
if exp[i] in ['+', '-', '*', '/']:
operators.append(exp[i])
self.compute(operands, operators)
else:
operands.append(float(exp[i]))
return operands[0] if len(operands) > 0 else 0
def compute(self, operands, operators):
right, left = operands.pop(), operands.pop()
op = operators.pop()
if op == '+':
operands.append(left + right)
elif op == '-':
operands.append(left - right)
elif op == '*':
operands.append(left * right)
elif op == '/':
operands.append(left / right)
def get_val(self, a, base):
if a == '+' or a == '-':
if base == maxint:
return base
return 1 + base
if a == '*' or a == '/':
if base == maxint:
return base
return 2 + base
return maxint
def create_tree(self, expression):
stack = []
base = 0
for i in range(len(expression)):
if expression[i] == '(':
if base != maxint:
base += 10
continue
elif expression[i]== ')':
if base != maxint:
base -= 10
continue
val = self.get_val(expression[i], base)
node = MyTreeNode(val, expression[i])
while stack and val <= stack[-1].val:
node.left = stack.pop()
if stack:
stack[-1].right = node
stack.append(node)
if not stack:
return None
return stack[0]
def postOrder(self, node, exp):
if not node:
return
self.postOrder(node.left, exp)
self.postOrder(node.right, exp)
exp.append(node.s)
def oneStepCalculate(self, s):
if not s:
return 0
exp = self.convert(s)
n = self.build(exp)
return self.calculate(n)
if __name__ == "__main__":
print(ExpressionTree().oneStepCalculate("3/5+1.4*6"))
print(ExpressionTree().oneStepCalculate("1+(2*(4-6))"))
print(ExpressionTree().oneStepCalculate("5/(2+(3*(4/3)))"))
print(ExpressionTree().oneStepCalculate("1/(2+3)+(5+(6-8))"))
print(ExpressionTree().oneStepCalculate("1"))
print(ExpressionTree().oneStepCalculate("1+1"))
