regexp валидности скобок

#php #регулярные_выражения

Как проверить на валидность скобки? Скобки могут быть и с пробелом и без, например
( () ) либо ) () (.
    

Ответы

Ответ 1

В PHP данную проблему легко решить с помощью рекурсивного регулярного выражения:

^[^()]*+(\((?>[^()]|(?1))*+\)[^()]*+)++$


См. демо (\n добавлен в демонстративных целях)

Описание рекурсивного механизма приведено на странице Рекурсивные шаблоны в Руководстве
по PHP.

Шаблон находит следующее:


^ - начало строки
[^()]*+ - 0 и более символов, отличных от круглых скобок
(\((?>[^()]|(?1))*+\)[^()]*+)++ - (подмаска №1) 1 или более повторений


\( - открывающая круглая скобка
(?>[^()]|(?1))*+ - 0 и более повторений подстроки, состоящей из символов, отличных
от круглых скобок или подмаски №1
\) - закрывающая круглая скобка
[^()]*+ - 0 и более символов, отличных от круглых скобок.

$ - конец строки.


Ответ 2

Алгоритм только для скобок одного вида.

Заводим счёчик. Перебираем символы по порядку. Если встретилась открывающая скобка,
увеличиваем счётчик. Если закрывающая -- уменьшаем. Если после уменьшения счётчик стал
отрицательным, возвращаем ошибку.
При окончании строки если счётчик не равен нулю, возвращаем ошибку.
Иначе строка валидна.


Ответ 3

Напишите детерминированный/недетерминированный конечный автомат для решения этой
задачи, затем сделайте из получившегося автомата - минимальный дка/нка, используя например
эту статью: http://habrahabr.ru/post/166777/, потом методом исключения состояний постройте
регулярное выражение, описание есть в книге Хопкрофта, или вот обсуждение http://dxdy.ru/topic77781.html.
И будет вам счастье)