我正在尝试使用 python 中的 Stacks 来计算中缀表达式。
我想知道下面是否有以下中缀表达式:
'2 ^ ( 1 + 3 ^ 2 )'
'( 3 * 5 ) - ( 1 > 2 > 3 < 4 )'
'4 ^ ( 10 < 2 ) / 5 + 100'
我将如何继续使用 2 个堆栈来评估它,而不是调用多个其他函数,以便输出为:
1024
12
103
我只是想知道执行此操作的算法是什么。我知道标准方法是将中缀更改为后缀然后解决,但是有没有一种更快的方法可以在一个函数中完成此操作。非常感谢。
最佳答案
您可能想要搜索 "shunting yard algorithm" 。这是一种非常基本的表达式求值算法,它使用两个堆栈(尽管其中一个称为“输出队列”)。
基本上,您可以过滤来自运算符的数字。数字进入输出堆栈,运算符进入“保持”堆栈。当出现的运算符的优先级低于保持堆栈中的优先级时,您可以将保持堆栈的内容移动到输出堆栈,直到保持堆栈为空,或者保持堆栈上的项目的优先级低于输入运算符.
优先级
请记住,a + b * c - d
的计算结果为 (a + (b*c)) - d
。还要记住,求幂比乘法具有更高的优先级,因此 a * b ^ c
将是 a * (b ^ c)
。
编辑:
这是一些不起作用的代码。我不知道你的运算符“>”和“<”是什么。显然,从第三个表达式来看 (10 < 2) 应该是 2?
我只是将它们实现为 C 风格的 bool 值(1 为 true,0 为 false)。
那里有一堆冗余代码,因为只有一个函数。请随意清理它。它修改了调车场算法以动态执行 RPN 计算。我留下了一堆打印语句来说明我用作堆栈的列表的内容。请随意对您的堆栈类进行适当的工作。在我的版本中,pop()
是弹出,append()
是推送。
tests = [
'2 ^ ( 1 + 3 ^ 2 )',
'( 3 * 5 ) - ( 1 > 2 > 3 < 4 )',
'4 ^ ( 10 < 2 ) / 5 + 100',
]
expected = [
1024,
12,
103,
]
def expr_eval(s):
print("EXPR:", s)
tokens = s.split()
output_stk = []
operator_stk = []
precedence = {
'(': 0,
'+':1, '-':1, '<':1, '>':1,
'*':2, '/':2,
'^':3,
}
for t in tokens:
print("OUT:", output_stk, "OP:", operator_stk)
print("Tok: ",t)
if t.isdigit():
output_stk.append(int(t))
continue
elif t == '(':
operator_stk.append(t)
continue
elif t == ')':
# End of subexpression. Do math until we find opening (
while operator_stk:
op = operator_stk.pop()
if op == '(':
break
b = output_stk.pop()
a = output_stk.pop()
if op == '-': output_stk.append(a - b)
elif op == '+': output_stk.append(a + b)
elif op == '<': output_stk.append(1 if a < b else 0)
elif op == '>': output_stk.append(1 if a > b else 0)
elif op == '*': output_stk.append(a * b)
elif op == '/': output_stk.append(a // b)
elif op == '^': output_stk.append(a ** b)
else:
raise Exception("Unknown operator: %s" % op)
print("OUT:", output_stk, "OP:", operator_stk)
continue
# Not a number - check operator precedence
prec_t = precedence[t]
while operator_stk and prec_t <= precedence[operator_stk[-1]]:
print("OUT:", output_stk, "OP:", operator_stk)
op = operator_stk.pop()
b = output_stk.pop()
a = output_stk.pop() # 'a' went on first!
if op == '-': output_stk.append(a - b)
elif op == '+': output_stk.append(a + b)
elif op == '<': output_stk.append(1 if a < b else 0)
elif op == '>': output_stk.append(1 if a > b else 0)
elif op == '*': output_stk.append(a * b)
elif op == '/': output_stk.append(a // b)
elif op == '^': output_stk.append(a ** b)
else:
raise Exception("Unknown operator: %s" % op)
operator_stk.append(t)
print("OUT:", output_stk, "OP:", operator_stk)
while operator_stk:
op = operator_stk.pop()
if op == '(':
raise Exception('Mismatched opening parenthesis!')
b = output_stk.pop()
a = output_stk.pop() # 'a' went on first!
if op == '-': output_stk.append(a - b)
elif op == '+': output_stk.append(a + b)
elif op == '<': output_stk.append(1 if a < b else 0)
elif op == '>': output_stk.append(1 if a > b else 0)
elif op == '*': output_stk.append(a * b)
elif op == '/': output_stk.append(a // b)
elif op == '^': output_stk.append(a ** b)
else:
raise Exception("Unknown operator: %s" % op)
print("OUT:", output_stk, "OP:", operator_stk)
return output_stk.pop()
for i in range(len(tests)):
r = expr_eval(tests[i])
if r == expected[i]:
print("PASS: %d = %s" % (r, tests[i]))
else:
print("FAIL: %d != %d = %s" % (r, expected[i], tests[i]))
关于python - 使用 python 计算数学表达式而不使用多个函数的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41993639/