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]))
您可能需要搜索"shunting yard algorithm"。这是一个非常基本的表达式求值算法,它使用两个堆栈(尽管其中一个称为“输出队列”)。在
基本上,你从运算符中过滤数字。数字进入输出堆栈,运算符进入“保持”堆栈。当一个运算符的优先级低于保留堆栈上的运算符时,可以将保留堆栈的内容移到输出堆栈中,直到保留堆栈为空,或者保留堆栈上的项的优先级低于输入运算符。在
优先权
请记住,}。在
a + b * c - d
被计算为(a + (b*c)) - d
。还要记住,求幂比乘法有更高的优先级,所以a * b ^ c
将是{编辑:
这里有些代码不起作用。我不知道你的接线员“>;”和“<;”是什么。显然(10<;2)应该是第三个表达式中的2?在
我只是把它们实现为C风格的布尔函数(1表示真,0表示假)。在
里面有一堆冗余代码,因为只有一个函数。请随意清理。对调车场算法进行了改进,使之能实时进行RPN计算。我留下了一堆print语句,这些语句说明了我作为堆栈使用的列表的内容。请随意对堆栈类进行适当的处理。在我的版本中,
pop()
是pop,append()
是push。在相关问题 更多 >
编程相关推荐