反向抛光表示法算法在相同的操作数下无法正常工作

Question

我写了波兰符号算法。但是，如果运算符之间存在相同的操作数，则它无法正常工作。如果我们使用当前列表 ['a'， '+'， 'a'， '*'， 'b'] 运行此代码，它将正常工作，但如果我们在 (a( 上更改 (b(，它将无法正常工作。 第一种情况的结果是 (a， a， b， *， +(，第二种情况的结果是 (a， a， +， a， *(。为什么会这样？

operators = ["+", "-"]
operators1 = ["*", "/"]
operators2 = ["^"]
operators3 = ["(", ")"]
all_operators = ["+", "-", "*", "/", "^"]

def get_priority(operator):
if operator in operators:
priority = 1
if operator in operators1:
priority = 2
if operator in operators2:
priority = 3
if operator in operators3:
priority = 4
return priority

def notation():
exit = []
stack = []
list = ['a', '+', 'a', '*', 'b']
for i in list:
if i not in all_operators:
exit.append(i)
else:
stack.append(i)
while len(stack) > 1 and get_priority(stack[-2]) >= get_priority(stack[-1]):
exit.append(stack.pop(-2))
if i is list[-1]:
while len(stack) > 0:
exit.append(stack.pop())
print(exit)


notation()

Answer 1

错误i is list[-1]，当列表的最后一个元素是列表中较早出现的值时，错误就会出现。在 ['a'， '+'， 'a'， '*'， 'a'] 的情况下，条件在循环的第一次迭代(以及第三次和最后一次(上为真。显然，这将产生错误的结果。

由于您只想在经历for循环的最后一次迭代时执行该while循环，因此不妨无条件地将while循环移动到整个for块之后。

我对你的代码应用了一些其他的更改，这些更改与您的问题无关，也不是算法本身的修复，而只是看起来更好的做法。我从运算符列表中删除了括号，因为您的代码尚不支持该功能(波兰语表示法不应包含括号(：

operator_priority = {
"+": 1,
"-": 1,
"*": 2,
"/": 2,
"^": 3,
}
all_operators = list(operator_priority.keys())
def notation(tokens):
result = []
stack = []
for token in tokens:
if token not in all_operators:
result.append(token)
else:
prio = operator_priority[token]
while len(stack) > 0 and operator_priority[stack[-1]] >= prio:
result.append(stack.pop())
stack.append(token)
while len(stack) > 0:
result.append(stack.pop())
return result

result = notation(['a', '+', 'a', '*', 'a'])
print(result)