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

Question

I am trying to implement Dijkstra's shunting yard algorithm to python because it would be a good exercise. However even though my code works properly for some test cases. It doesn't work properly for some of them.

In my specific case it doesn't work properly after the place I showed in the picture: screenshot

Here is my code:

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)

Though, it works properly for test2 "A*B+C-D":

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

And for test3 "A-B*(C-D-E)/F-G":

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

I really want to get this done but I don't know how to proceed after this, I'm kind of stuck. Can someone give me hand?

I am also adding the pseudocode that I used:

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.

Note: I know that my code is kind of a mess right now but I'll handle it after I solve the problem.

Answer 1

There are two parentheses on the stack. Which is being removed? Which should be removed?

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

Pseudocode (emphasis added)

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.

Docs.python.org (emphasis added)

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