Expression Tree即表達(dá)式樹，專門用于計算表達(dá)式。例如，3-(4+5)，轉(zhuǎn)化成list形式，即['3','-','(','4','+','5',')']，其表達(dá)式樹為：
-
/
3 +
/
4 5
這樣安排的好處是，這棵樹的后續(xù)遍歷就是逆波蘭表達(dá)式，即[3,4,5,+,-]。由逆波蘭表達(dá)式即可進(jìn)行計算。
表達(dá)式樹的關(guān)鍵在于生成，生成是根據(jù)優(yōu)先度來決定的。對于普通的加減乘除表達(dá)式，有以下規(guī)定：
- 數(shù)字的優(yōu)先度是最大的；
- +-優(yōu)先度為+1
- */優(yōu)先度為+2
- 遇到'('，優(yōu)先度+10；遇到')'，優(yōu)先度減10
則例子中的優(yōu)先度list是[max, 1, max, 11, max]。把括號從計算當(dāng)中去除。
那么，相當(dāng)于把表達(dá)式轉(zhuǎn)換成為了一個最小樹，優(yōu)先度最小的在上面，優(yōu)先度最大的數(shù)字在葉子節(jié)點(diǎn)上。
而對于生成最大/最小樹，有一個很優(yōu)雅的解法： - 新建一個stk，然后對優(yōu)先度list遍歷；
- 對于一個元素n，每當(dāng)stk之前的元素比其大，就將其作為n的左子樹，直至stk為空，或者遇到一個比n小的元素，此時就把n作為其右子樹；
- 直至遍歷結(jié)束，返回stk[0]即可。
要實(shí)現(xiàn)“一條龍服務(wù)”，需要以下功能： - 從字符串表達(dá)式到表達(dá)式的list形式；T:O(n) S:O(n)
- 從表達(dá)式list到表達(dá)式樹；T:O(n) S:O(n)
- 對表達(dá)式樹后序遍歷獲得逆波蘭表達(dá)式；T:O(n) S:O(n)
- 對逆波蘭表達(dá)式進(jìn)行計算。T:O(n) S:O(n)
總體復(fù)雜度T:O(n) S:O(n)。雖然有點(diǎn)長，但是解決了不少表達(dá)式計算的問題。代碼如下：
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"))
