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

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