时间戳

首页 > 解决方案 > 反向波兰符号算法不能与相同的操作数正确工作

python - 反向波兰符号算法不能与相同的操作数正确工作

问题描述

我写了波兰符号算法。但是如果操作符之间有相同的操作数，它就不能正常工作。如果我们使用当前列表 ['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()

标签： pythonalgorithmpolish-notation

解决方案

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)

推荐阅读