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

Question

我写过波兰语算法。但是如果运算符之间有相同的操作数，它就不能正常工作。如果我们运行此代码与当前列表 ['a'、'+'、'a'、'*'、'b']，它将正常工作，但如果我们更改（ b) 在 (a) 上它不会。第一种情况的结果是 (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)

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

Reverse polish notation algorithm doesn`t work correctly with the same operands

python

algorithm

polish-notation