вторник, 21 марта 2017 г.

Задача о корректности расстановки скобок

Хочется рассказать о такой задаче, как определение корректности расстановки скобок. Она так же известна, как balanced parenthesis problem. Суть ее в следующем: дана строка, содержащая открывающиеся и закрывающиеся скобки, и какие то другие символы. Нужно узнать правильно ли расставлены скобки. Т.е. для каждой открывающейся скобки должна быть закрывающаяся. Например, строки вида (()) или (()()) содержат корректную расстановку, а (()() и )()( уже нет.

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

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

Код решения довольно прост:

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

И напоследок, предлагаю рассмотреть многопоточный вариант.

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

Здесь потребуется более подробное объяснение.

Возьмем S1,S2,S3...Sn - n строк из которых состоит исходная строка S. Т.е. конкатенация этих строк S1+S2+S3+...+Sn = S составляет первоначальную строку. У каждой строки S с номером i есть два числа - финальное значение finalValue и наименьшее значение minValue. Вычисляются они следующим образом:
Так же как и в решении со счетчиком, мы заводим переменную value = 0. Если встречаем ( то увеличиваем на 1, если ) то уменьшаем. В результате получаются значения finalValue = value, а minValue = минимальное value, которое было в процессе обработки.
Таким образом, должно выполняться неравенство sum (j = от 1 до i-1) finalValue(j) + min(i) >=0 и sum(j = от 1 до n) finalValue(j) = 0

Код решения на языке Scala: