反向波兰符号算法不能正确处理相同的操作数

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 = 4return prioritydef 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'] 的情况下，条件将在循环的第一次迭代（以及第三次和最后一次）上为真。显然这会产生错误的结果。

由于您只想在while循环的最后一次迭代时执行该for循环，因此您最好将该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)