from typing import List
from typing import Tuple


def _create_instruction_bounds(instructions: str) -> List[Tuple[int, int]]:
    """converts an instruction string into a list of bounds containing the 
    index of the opening and closing parenthesis
    
    Parameters
    ----------
    instructions : str
        e.g.
            '(((main_opt, second_opt) & second_opt & third_opt) & second_opt)'
    
    Returns
    -------
    List[Tuple[int, int]]
        e.g.
            [(2, 23), (1, 49), (0, 63)]
    
    Raises
    ------
    ValueError
        a string that does not have a closing ) for a (
    """

    steps = []
    left_indexes = []
    right_indexes = []

    for i, char in enumerate(instructions):
        # open and close
        if char == "(":
            left_indexes.append(i)
        elif char == ")":
            right_indexes.append(i)

        # rest are assumed optimizer names or comments or instructions
        else:
            pass

    # build all steps of instructions
    for i, right_ind in enumerate(right_indexes):
        corresponding_l_paren_index = None

        # find corresponding index from left paren
        for j, left_ind in enumerate(left_indexes):
            if left_ind > right_ind:
                # we need the value before it becomes larger
                corresponding_l_paren_index = j - 1
        if not corresponding_l_paren_index:
            # will obtain furthest `(`
            corresponding_l_paren_index = len(left_indexes) - 1

        if corresponding_l_paren_index < 0:
            raise ValueError(
                f"no corresponding left index was found for the right ) at index {right_ind} - {instructions[:right_ind]}"
            )

        lv = left_indexes[corresponding_l_paren_index]
        left_indexes.remove(lv)
        steps.append((lv, right_ind))

    return steps