Shunting Yard Algorithm in Python

shunting_yard.py

import re

from collections import deque
from typing import List, Union

def tokenize(expression: str) -> List[Union[int, str]]:
    tokens = [
        int(token) 
        if token.isnumeric() 
        else token 
        for token 
        in re.split(r'(\d+)|([+\-x\^/]+)|([\(\)])', expression) 
        if token and token != ' '
    ]
    return tokens

operators = {
    '^': {'precedence': 4, 'associativity': 'right'},
    'x': {'precedence': 3, 'associativity': 'left'},
    '/': {'precedence': 3, 'associativity': 'left'},
    '+': {'precedence': 2, 'associativity': 'left'},
    '-': {'precedence': 3, 'associativity': 'left'}
}

class MismatchedParenthesisError(Exception):
    pass

def parse_tokens(tokens: List[Union[int, str]]):
    output_queue = []
    operator_stack = []
    for token in tokens:
        print(f'{output_queue=}\n{operator_stack=}\n{token=}\n{tokens=}')
        if isinstance(token, int):
            print(f'Found int, {token=}, appending to output_queue')
            output_queue.append(token)
        elif token in operators:
            print(f'Found operator, {token=}, checking for higher precedence operators or equal precedence operators with left associativity')
            while (
                operator_stack
                and operator_stack[-1] != '('
                and (
                    operators[operator_stack[-1]]['precedence'] > operators[token]['precedence']
                    or (
                        operators[operator_stack[-1]]['precedence'] == operators[token]['precedence']
                        and operators[token]['associativity'] == 'left'
                    )
                ) 
            ):
                print(f'  - Appending {operator_stack[-1]=} to the output_queue')
                output_queue.append(operator_stack.pop())
            print(f'Done. Now appending {token=} to operator_stack')
            operator_stack.append(token)
        elif token == '(':
            print(f'Found left parens, {token=}, appending it to the operator stack')
            operator_stack.append(token)
        elif token == ')':
            print(f'Found right parens, {token=}, popping all non left paren operators off the operator stack')
            try: 
                while operator_stack[-1] != '(':
                    print(f'  - Found {operator_stack[-1]=}, popping it into the output_queue')
                    output_queue.append(operator_stack.pop())
            except IndexError:
                print(f'Whoopsie, mismatch parens detected!')
                raise MismatchedParenthesisError('ERROR: Parenthesis are mismatched!')
            print(f'Done. Appending right parens, {operator_stack[-1]}, and discarding')
            operator_stack.pop()
        print('-'*50, end='\n')

    print(f'No more tokens, now popping all operators from the operator stack onto the output queue')
    while operator_stack:
        operator = operator_stack.pop()
        print(f'Found {operator=}. ', end=' ')
        if operator in '()':
            print(f'Whoopsie! Mismatched parens.')
            raise MismatchedParenthesisError('ERROR: Parenthesis are mismatched!')
        print(f'appending it to the output_queue')
        output_queue.append(operator)
        
    return output_queue

parse_tokens(tokens)