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

Question

[lucifer_jr]

Как исправить скобочную последовательность путём закрытия скобок или удаления? Не могу ни за что зацепиться.
Пример последовательностей:
1) [(]) (невалидная, как исправить?)
2) }])
и пр

Answer 1

[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) времени.

Comments

[Ivan Brezhnev]

Чертов, гений!

[Wataru]

Иван Брежнев, Да нет тут ничего гениального. Если нарешать достаточно задачек на ДП, то решение в этой задаче вообще очевидно.

Answer 2

[dollar]

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

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

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

P.S. Дарю вам бонусный пример строки для медитации:
/* [(]) */ y = (a[i] + 7); // }])

Comments

[Сергей Соколов]

наверное, можно определить "длину" пути до исправленной версии каждого из вариантов, и среди равных наименьших выбрать случайный вариант )

[dollar]

Сергей Соколов,
x = 2 * 2 + (2);