评估后缀表达式树 - 计算器
Evaluate Postfix Expression Tree - Calculator
我有代码从中缀生成后缀表达式并从后缀表示法生成表达式树。问题是,如果我给它一个像 45 / 15 * 3 这样的表达式,它会给我结果 1 而不是 9,因为它首先求解树的最深层。我可以做另一种遍历来正确评估表达式吗?
def evaluate(self):
if not self.is_empty():
if not infix_to_postfix.is_operator(self._root):
return float(self._root)
else:
A = self._left.evaluate()
B = self._right.evaluate()
if self._root == "+":
return A + B
elif self._root == "-":
return A - B
elif self._root == "*":
return A * B
elif self._root == "/":
return A / B
def InfixToPostfix(exp: str):
exp = exp.replace(" ", "")
S = Stack()
postfix = ""
j = 0
for i in range(len(exp)):
if is_operand(exp[i]):
if i + 1 <= len(exp) - 1 and is_operand(exp[i+1]):
continue
else:
j = i
while j - 1 >= 0 and is_operand(exp[j - 1]):
if is_operand(exp[j]):
j -= 1
else:
break
postfix += exp[j:i + 1] + " "
elif is_operator(exp[i]):
while not S.is_empty() and S.top() != "(" and \ HasHigherPrecedence(S.top(), exp[i]):
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
S.push(exp[i])
elif exp[i] == "(":
S.push(exp[i])
elif exp[i] == ")":
while not S.is_empty() and S.top() != "(":
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
else:
print("There's an invalid character")
return
while not S.is_empty():
if S.top() == '(':
S.pop()
continue
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
return postfix
def HasHigherPrecedence(op1: str, op2: str):
op1_weight = get_operator_weight(op1)
op2_weight = get_operator_weight(op2)
return op1_weight > op2_weight
您的示例 45 / 15 * 3 的后缀表达式为:
45 15 / 3 *
所以生成的树看起来像:
*
/ 3
45 15
所以你的遍历算法看起来是正确的,因为它会做 45 / 15 = 3,然后 3 * 3 = 9。
这个问题实际上在您的后缀生成器中很小。具体来说,在函数 HasHigherPrecedence 中,你应该 return op1_weight >= op2_weight
。它应该大于或等于,因为在这样的示例中,运算符具有相同的优先级,它们应该按照它们出现的顺序执行。所以先做除法
我有代码从中缀生成后缀表达式并从后缀表示法生成表达式树。问题是,如果我给它一个像 45 / 15 * 3 这样的表达式,它会给我结果 1 而不是 9,因为它首先求解树的最深层。我可以做另一种遍历来正确评估表达式吗?
def evaluate(self):
if not self.is_empty():
if not infix_to_postfix.is_operator(self._root):
return float(self._root)
else:
A = self._left.evaluate()
B = self._right.evaluate()
if self._root == "+":
return A + B
elif self._root == "-":
return A - B
elif self._root == "*":
return A * B
elif self._root == "/":
return A / B
def InfixToPostfix(exp: str):
exp = exp.replace(" ", "")
S = Stack()
postfix = ""
j = 0
for i in range(len(exp)):
if is_operand(exp[i]):
if i + 1 <= len(exp) - 1 and is_operand(exp[i+1]):
continue
else:
j = i
while j - 1 >= 0 and is_operand(exp[j - 1]):
if is_operand(exp[j]):
j -= 1
else:
break
postfix += exp[j:i + 1] + " "
elif is_operator(exp[i]):
while not S.is_empty() and S.top() != "(" and \ HasHigherPrecedence(S.top(), exp[i]):
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
S.push(exp[i])
elif exp[i] == "(":
S.push(exp[i])
elif exp[i] == ")":
while not S.is_empty() and S.top() != "(":
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
else:
print("There's an invalid character")
return
while not S.is_empty():
if S.top() == '(':
S.pop()
continue
if is_operator(S.top()):
postfix += S.top() + " "
else:
postfix += S.top()
S.pop()
return postfix
def HasHigherPrecedence(op1: str, op2: str):
op1_weight = get_operator_weight(op1)
op2_weight = get_operator_weight(op2)
return op1_weight > op2_weight
您的示例 45 / 15 * 3 的后缀表达式为:
45 15 / 3 *
所以生成的树看起来像:
*
/ 3
45 15
所以你的遍历算法看起来是正确的,因为它会做 45 / 15 = 3,然后 3 * 3 = 9。
这个问题实际上在您的后缀生成器中很小。具体来说,在函数 HasHigherPrecedence 中,你应该 return op1_weight >= op2_weight
。它应该大于或等于,因为在这样的示例中,运算符具有相同的优先级,它们应该按照它们出现的顺序执行。所以先做除法