@lucifer_jr

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

Как исправить скобочную последовательность путём закрытия скобок или удаления? Не могу ни за что зацепиться.
Пример последовательностей:
1) [(]) (невалидная, как исправить?)
2) }])
и пр
  • Вопрос задан
  • 102 просмотра
Пригласить эксперта
Ответы на вопрос 2
dollar
@dollar
На чёткий вопрос - чёткий ответ.
Определить такую последовательность можно с помощью стека - это структура в памяти (обычный массив), куда вы должны будете складывать скобки по мере прохождения по текстовой строке со скобками. Если скобка открывающая, то скалываете её в стек. Если закрывающая, то вынимаете соответствующую открывающую скобку из стека. И если скобка не та (тип не совпал), или необходимо взять скобку из пустого стека, или в конце строки стек не опустел, то значит в строке присутствует ошибка.

А вот автоматически исправлять ошибку - дело неблагодарное. Потому что текстовая строка с дефектом не содержит информации о том, какой она должна быть. Например, если ошибка в том, что скобка пропущена, то как узнать, в какое место нужно вставить недостающую скобку? Никак! Разве что ваша строка имеет определённый формат и всякие намёки на то, где это скобка может быть. Но даже в этом случае, скорее всего, будет неоднозначность.

Например, строка из текста программы: x = 2 * 2 + 2);
С помощью алгоритма выше вы можете узнать, что в скобочной последовательности допущена ошибка. Но есть целых три места, куда можно вставить открывающую скобку, чтобы строка стала валидной синтаксически. Если это Си-подобный язык, то четыре. Но даже если рассматривать более или менее разумные места для вставки, то их два, и всё равно не понятно, что именно будет исправлением ошибки.

P.S. Дарю вам бонусный пример строки для медитации:
/* [(]) */ y = (a[i] + 7); // }])
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Если это задача такая, то я предполагаю, что там надо удалить минимальное количество скобок, чтобы последовательность стала правильной. Можно только удалять скобки, потому что вместо любого добавления скобки, можно просто вторую пару удалять. Количество действий не изменится. Правда, в ваших примерах оно удалит все скобки.

Тут можно решать динамическим программированием. Пусть F(l,r) - минимальное количество операций удаления, чтобы сделать из строки с l по r правильную скобочную последовательность.

База - если l..r - пустая строка - ответ 0.
Иначе надо рассматривать варианты, что будет с последним символом. Если в конце стоит открывающая скобка, то ее надо удалить - других вариантов нет: F(l,r) = 1+F(l,r-1).

Если же там закрывающая скобка, то есть 2 варинта: или этот символ удаляем, или берем в ответ. В первом варианте ответ такой-же, как выше. Во втором - надо перебрать, а какой же символ в строке будет открывающей скобкой для данной. Пусть это символ i (там должна стоять открывающая скобка того же типа). Тогда ответ F(l,i-1)+F(i+1,r-1) - ведь части перед парой скобок и внутри их должны тоже быть правильными последовательностями.
Из всех вариантов надо выбрать минимальный - это и будет ответ для текущего состояния.

Если хотите восстанвливать саму последовательность, то надо при сохранении минимума еще и сохранять в отдельном двумерном массиве - какой именно из вариантов был выбран (дропнуть последний символ, или какой символ взять ему в пару).

Ответ к задаче - F(1,n) - для всей строки.

Это решение потребляет O(n^2) памяти и занимает O(n^3) времени.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bnovo Санкт-Петербург
от 110 000 до 140 000 ₽
Spice IT Recruitment Москва
от 160 000 до 200 000 ₽
СофтТелематика Москва
от 120 000 до 180 000 ₽
07 мар. 2021, в 03:18
1500 руб./за проект
06 мар. 2021, в 22:58
70000 руб./за проект
06 мар. 2021, в 22:36
10000 руб./за проект