Напишите рекурсивную функцию match_bracket (string, idx), чтобы найти индекс закрывающей скобки, совпадающей с открытой скобкой в ​​строке [idx]

Question

Несмотря на то, что есть много вопросов по stackoverflow, чтобы проверить, сбалансирована ли строка, мне нужно найти индекс закрывающей скобки string[idx]. Например:

>>> matching_bracket('([])', 0)
3

>>> matching_bracket('([])', 1)
2

Существует 3 условия, которые будут возвращать -1:

1. закрывающая скобка не того же типа

2. вложенные скобки не совпадают [ВАЖНО]

3. больше нет доступных скобок

Вот что у меня есть до сих пор:

def matching_bracket(string, idx):
  open_tup = ("(", "{", "<", "[")
  close_tup = (")", "}", ">", "]")
  chosen = string[idx]
  b_index = open_tup.index(chosen)
  n = len(string) - 1
  if string[idx + 1] in open_tup: # Case 1: Check if nested brackets match
    return matching_bracket(string, idx + 1)
  elif string[n] != close_tup[b_index]: # Case 2: Closing bracket not the same
    return matching_bracket(string[0 : n], idx)
  elif len(string) == 1: # Case 3: No more available brackets
    return -1
  else:
    return n

Пока я выполняю рекурсивную функцию, чтобы проверить, закрыты ли вложенные скобки, у меня возникают трудности с получением правильного вывода, поскольку я в конечном итоге возвращаю индекс закрывающей скобки, которая вместо этого вложен См. Ниже:

>>> matching_bracket('([])', 0)
2

Как мне изменить мой код?

Answer 1

В приведенном выше коде, во-первых, если условие вы проверяете, является ли следующая скобка открытого типа. если это так, вы вызываете match_bracket со следующим индексом скобки. и потерю фактического индекса открытой скобки, для которого вы хотите закрыть индекс скобки. Оформить заказ следующего решения, используя:

def matching_bracket(string, idx):
    open_tup = ("(", "{", "<", "[")
    close_tup = (")", "}", ">", "]")

    dict_brackets = {"{": "}", "(": ")", "<": ">", "[": "]"}
    stack = []
    if string[idx] in close_tup or idx >= len(string):
        return -1
    stack.append(string[idx])
    for t in range(idx + 1, len(string)):
        if string[t] in open_tup:
            stack.append(string[t])
        else:
            if string[t] != dict_brackets.get(stack.pop()):
                return -1
            elif len(stack) == 0:
                return t
    return -1

Answer 2

Это немного запутанно, но должно сделать:

def matching_bracket(string, idx):
    bracket_dict = {'[':']', '(':')', '{':'}', '<':'>'}
    # Actual recursive function
    def inner_func(ix_open, ix_close):
        if string[ix_close] == bracket_dict[string[ix_open]]:
            return ix_open, ix_close
        else:
            if ix_close + 1 == len(string) - 1:
                return ix_open, -1
            else:
                return inner_func(ix_open+1, ix_close+1)
    if idx == len(string) - 1:
        return -1
    elif string[idx + 1] == bracket_dict[string[idx]]:
        return idx + 1
    elif idx == len(string) - 2:
        return -1
    else:
        ix_open, ix_close = idx+2, idx+1
        while ix_open != idx and ix_close != -1:
            ix_open, ix_close = ix_open - 1, ix_close + 1
            ix_open, ix_close = inner_func(ix_open, ix_close)
        return ix_close

PS: записал решение обратно, забыл написать: p

Answer 3

Если ваша цель - сопоставить открытые разделители и закрыть их соответствующими разделителями, взгляните на эту библиотеку , которую я сделал, возможно, алгоритм может вам помочь, хотя он находится в java.

Вот как это работает -

• Сначала класс должен знать, какой открывающий разделитель соответствует какому закрывающему разделителю - вы можете использовать словарь для этого в python

delim_dict = {}
delim_dict['('] = ')'
.....

• Теперь, если вы только заинтересованы в проверке, не совпадают ли закрывающие и открывающие разделители - возьмите посмотрите на эту функцию . Проще говоря, вы должны посчитать количество каждого закрывающего разделителя и открытого разделителя , итерация строки производится в обратном порядке. Всякий раз, когда вы видите, если количество не совпадает, вы знаете, что разделители также не совпадают

• Теперь, если вы хотите найти index желаемого разделитель - взгляните на эту функцию Она предназначена для поиска математической функции в выражении, учитывая его закрывающий разделитель, но вы можете изменить его в соответствии с вашим вариантом использования. Поскольку вы хотите найти закрывающий разделитель , учитывая открывающий разделитель , вы должны выполнять итерацию выражения в обычном порядке вместо обратного

# opening_delim is given as parameter
closing_delim = get_corresponding_delimiter(opening_delim)
closing_delim_count, opening_delim_count = 0, 0
i = 0
for item in expression:
    if expression[i] == opening_delim:
        opening_delim_count += 1
    elif expression[i] == closing_delim:
        closing_delim_count+= 1
    if opening_delim_count == closing_delim_count:
        return i
    i += 1

Конечно, этот код предназначен только для разделителя первого индекса и также предполагает, что разделители совпадают правильно