Dijkstra 调车场算法的实施在某些情况下无法正常工作

Question

我正在尝试将 Dijkstra 的调车场算法 实施到 python，因为这将是一个很好的练习。但是，即使我的代码对于某些测试用例也能正常工作。其中一些无法正常工作。

在我的具体情况下，在我在图片中显示的位置之后无法正常工作：screenshot

这是我的代码：

operator_dict = {"^": 3,
                 "*": 2,
                 "/": 2,
                 "+": 1,
                 "-": 1,
                 #"(": 0,
                 #")": 8
                 }
parenthesis_dict = {
                "(":1,
                ")":0
}

operator_assoc = {"^": 1, # right
                  "*": 0, # left
                  "/": 0,
                  "+": 0,
                  "-": 0,
                  "(": 0,
                  ")": 0,
                  }

test1 = "A-B^C^D*(E-(F-G-H))/K"
test2 = "A*B+C-D"
test3 = "A-B*(C-D-E)/F-G"
from time import sleep
initial_expression = test1
stack = []
output_queu = []

# if it is an operand we push it to the output queu
def operand_check(element):
    if (element not in operator_dict.keys()) and (element not in parenthesis_dict.keys()):
        output_queu.append(element)


def parenthesis_check(element):
    # push down the left parenthesis
    if element == "(":
        stack.append(element)
    # if it's right parenthesis then pop everything out of stack until
    # you reach left parenthesis
    elif element == ")":
        while stack[-1] != "(":
            temp = stack.pop()
            output_queu.append(temp)
        # to remove left parenthesis
        stack.remove(stack[-1])

def operator_check(element):
    if element in operator_dict.keys():
        while (len(stack) != 0) and assoc_precedence_check(element) and does_top_of_stack_have_operator():
            temp = stack.pop()
            output_queu.append(temp)
        stack.append(element)

def assoc_precedence_check(element):
    if stack[-1] == "(" or ((operator_assoc[element] == 0) and (operator_dict[element] <= operator_dict[stack[-1]])): return True
    elif stack[-1] == "(" or ((operator_assoc[element]==1) and (operator_dict[element] < operator_dict[stack[-1]])): return True
    else: return False


def does_top_of_stack_have_operator():
    return True if stack[-1] in operator_dict.keys() else False

def empty_stack():
    while len(stack) != 0 :
        temp = stack.pop()
        output_queu.append(temp)




# main stream
for element in initial_expression:


    operand_check(element)

    parenthesis_check(element)

    operator_check(element)

    

    print("stack:",stack)
    print("output queu",output_queu)
    #sleep(0.5)

empty_stack()

print("stack:",stack)
print("output queu",output_queu)

尽管，它适用于 test2 "A*B+C-D":

stack: []
output queu ['A', 'B', '*', 'C', '+', 'D', '-']

对于 test3 "A-B*(C-D-E)/F-G":

stack: []
output queu ['A', 'B', 'C', 'D', '-', 'E', '-', '*', 'F', '/', '-', 'G', '-']

我真的很想完成这项工作，但我不知道如何进行，我有点卡住了。谁能帮我一把？

我还添加了我使用的伪代码：

Get next token t from the input queue
if t is an operand then
  Add t to the output queue
if t is an operator then
  while There is an operator τ at the top of the stack, and either t is leftassociative
  and its precedence is less than or equal to the precedence of τ ,
  or t is right-associative and its precedence is less than the precedence of τ do
    Pop τ from the stack, to the output queue.
  Push t on the stack.
if t is a left parenthesis then
  Push t on the stack.
if t is a right parenthesis then
  Pop the operators from the stack, to the output queue until the top of the stack
  is a left parenthesis.
  Pop the left parenthesis.
if No more tokens to get then
  Pop the operators on the stack, if any, to the output queue.

注意：我知道我的代码现在有点乱，但我会在解决问题后处理它。

Answer 1

栈上有两个括号。哪个正在被删除？哪些应该删除？

elif element == ")":
    while stack[-1] != "(":
        temp = stack.pop()
        output_queu.append(temp)
    # to remove left parenthesis
    stack.remove(stack[-1])  # <----

伪代码（强调）

如果t是右括号则

从栈中弹出运算符，到输出队列，直到栈顶是左括号。
弹出左括号.

Docs.python.org（强调）

array.remove(x)
Remove the first occurrence of x from the array.

Dijkstra 调车场算法的实施在某些情况下无法正常工作

Implementation of Dijkstra's Shunting Yard Algorithm not working properly for some cases

python

algorithm

dijkstra

pseudocode

shunting-yard