Как найти наибольшую допустимую последовательность скобок и скобок в строке?

Question

Итак, у меня есть сценарий, который мне нужно написать, и одна из самых больших проблем сводится к поиску самой большой допустимой подпоследовательности внутри строки. Так что у меня есть что-то вроде

"()(({}[](][{[()]}]{})))(" 

в качестве входных данных, и я должен был бы вернуться

"[{[()]}]{}" 

как выход.

Я попытался использовать стек, подобный структуре, как если бы это было просто круглые скобки, но не смог найти что-то, что работает. Я бы предпочел решение на питоне, но любое руководство, которое может предложить, поможет независимо от языка. Эффективность в идеале должна быть лучше, чем n^2, так как я могу думать о решении O (n^2), используя этот How to find validity of a string of parentheses, curly brackets and square brackets?, и просто пробовать его на разных подстроках.

Answer 1

Это можно решить с помощью динамического программирования. Пройдите через массив, записывающий самый длинный действительный матч, заканчивающийся от каждого индекса. Если у вас есть самое длинное совпадение индекса i, то легко найти самое длинное совпадение индекса i + 1: пропустить назад самое длинное соответствие для индекса i, а затем посмотреть, соответствуют ли окружающие символы подходящим скобкам открытия/закрытия. Затем добавьте самое длинное совпадение слева от него, если оно есть.

Вот некоторые Python код, который вычисляет это:

def longest_valid(s): 
    match = [0] * (len(s) + 1) 
    for i in xrange(1, len(s)): 
     if s[i] in '({[': 
      continue 
     open = '({['[')}]'.index(s[i])] 
     start = i - 1 - match[i - 1] 
     if start < 0: continue 
     if s[start] != open: continue 
     match[i] = i - start + 1 + match[start - 1] 
    best = max(match) 
    end = match.index(best) 
    return s[end + 1 - best:end + 1] 

print longest_valid("()(({}[](][{[()]}]{})))(") 
print longest_valid("()(({}[]([{[()]}]{})))(") 
print longest_valid("{}[()()()()()()()]") 

Это O (п) во времени и пространстве.

Answer 2

Если вы говорите о произвольной глубине, применяются: Regular expression to detect semi-colon terminated C++ for & while loops

Если мы говорим конечную глубину, Regex может быть вашим другом (вы можете проверить производительность)

, кажется, что вы ищете:

• буквального Square- бюстгальтер cket
• куча символов, которые не заканчивается кронштейн
• закрывающей скобки
• открывающей фигурная скобка
• всех символы до последней закрывающей фигурной скобки
• закрывающей фигурной скобки

так, Язык- агностик что-то вроде:

\[[^]]*\{.*\} 

это может быть использовано с re.compi le с Python, но на самом деле это может быть любой язык. Так как. * (Любой char) и [^]] (неконцевая квадратная скобка), вы можете использовать w + или d + для слова/цифры или другого короткого слова Regex, чтобы уточнить решение и ускорить процесс.

Answer 3

Этот ответ использует следующую последовательность ввода в качестве примера. Ожидаемый вывод - это все строки, за исключением последних (.

Input: ()(({}[]([{[()]}]{})))(
Output:()(({}[]([{[()]}]{}))) 

Шаг 1 - найти семена в строке. Семя представляет собой согласованный набор символов: (), [], или {}. Я дал каждому семени численное значение, чтобы помочь читателю визуализировать семена.

()(({}[]([{[()]}]{})))(
11 2233 44 55 

Шаг 2 является расширить семена в последовательности. Последовательности представляют собой вложенный набор символов: например. [{[()]}]. Поэтому, начиная с семени, работайте наружу, проверяя соответствие соответствующих символов. Поиск заканчивается с несоответствием или в начале или в конце строки. В этом примере только семя 4 заключает в себя соответствующие символы, поэтому расширяется только семя 4.

()(({}[]([{[()]}]{})))(
11 2233 4444444455 

Шаг 3 состоит в объединить смежные последовательности. Обратите внимание, что может быть два или более смежных последовательностей, но в этом примере есть две смежные последовательности в двух местах

()(({}[]([{[()]}]{})))(
11 2222 4444444444 

Повторите шаг 2, рассматривая комбинированные последовательности как семена. В этом примере последовательность 4 заключена в соответствующие круглые скобки, поэтому последовательность 4 расширяется.

()(({}[]([{[()]}]{})))(
11 2222444444444444 

Повторите шаг 3, объединить последовательности

()(({}[]([{[()]}]{})))(
11 2222222222222222 

Повторите шаг 2, расширить

()(({}[]([{[()]}]{})))(
1122222222222222222222 

И объединить еще один раз

()(({}[]([{[()]}]{})))(
1111111111111111111111 

Алгоритм заканчивается, когда нет ничего оставлять для расширения, или c ombine. Ответ - самая длинная последовательность.

---

Примечание по реализации:

Я думаю, что вы можете достичь O(n) пути расширения/слияния одной последовательности в то время. Я бы сохранил список последовательностей в двусвязном списке (поэтому удаление - операция O(1)). Каждая последовательность будет представлена ​​индексом start и индексом end.

Расширение последовательности включает проверку символов на array[start-1] и array[end+1], а затем обновление индексов start/end в зависимости от обстоятельств.

Слияние предполагает проверку следующей и предыдущей последовательностей в связанном списке. Если последовательности можно объединить, то одна последовательность обновляется, чтобы охватить весь диапазон, а другая удалена.

Как только последовательность будет расширена или объединена как можно больше, перейдите к следующей последовательности в списке. Поскольку эта новая последовательность расширяется/объединяется, она может в конечном итоге вернуться к предыдущей последовательности. Следовательно, после первоначального создания двусвязного списка семян один проход через связанный список должен быть достаточным для расширения/слияния всех последовательностей. Затем нужно пройти второе, чтобы найти самую длинную последовательность, оставшуюся от связанного списка.