Вопрос для гуру регулярных выражений

Есть ли способ с помощью регулярных выражений проверить баланс скобочек в строках типа ((()(()()))())? Лично мне такой способ неизвестен. Может, я не знаю чего-то?
  • Вопрос задан
  • 6233 просмотра
Решения вопроса 1
@Bonart
Классические регулярные выражения из математики такую задачу не решают. Но на практике последние версиии популярной библиотеки PCRE умеют:
my $bal = qr/
    (?<bal>            # Name the rule (optional)  
    \{                 # Open brace
    (?>                # Possessive subgroup
        (?> [^{}]+ )   #  Grab all the non braces
    |                  #    or
        (?&bal)        #  Recurse
    )*                 # Zero or more times
    \}                 # Close brace
    )                  # End named rule
/x;

if ('{x{x}y{x}x}' =~ /^$bal$/ ){
    print "It's balanced\n";
}

$_= 'XXXX function xxx() {x{x}y{x}x} XXXX';

while ( /\bfunction\s+(\w+)\(\)\s*($bal)/g ){
    print "function: $1\nbody: $2\n";
}


Да и дотнет не отстает:

string pattern = 
    @"^((?<openBracket>\{) | [^\{\}] |" + 
    @"(?<closeBracket-openBracket>\}))*" +
    @"(?(openBracket)(?!))$";
Regex r = new Regex(pattern, RegexOptions.IgnorePatternWhitespace);
Ответ написан
Пригласить эксперта
Ответы на вопрос 8
Mithgol
@Mithgol
Сперва убрать из строки все нескобки (то есть найти регулярным выражением «[^()]» и заменить на пустую строку), затем перейти от регулярных выражений к обыкновенному программированию — пройтись по итоговой строке скобок в посимвольном цикле, который к значению некоторой переменной (изначально имеющей нулевое значение) прибавляет единицу, если найден символ «(», и вычитает единицу, если найден символ «)», причём цикл сразу завершается, если значение меньше нуля (найден дисбаланс скобок), а в конце цикла (что соответствует концу строки скобок) это значение также должно быть равно нулю, иначе опять же найден дисбаланс скобок.
Ответ написан
@Ano
В некоторых языках работают рекурсивные выражения:

\( (?: [^()] *+ | (?0) )* \)

В некоторых языках можно читерить (PERL):

$regex = qr/
  \(
    (
      [^()]+
    |
      (??{$regex})
    )*
  \)
/x;


(Ruby)

re = %r{
  (?<re>
    \(
      (?:
        (?> [^()]+ )
        |
        \g<re>
      )*
    \)
  )
}x
Ответ написан
taliban
@taliban
php программист
Даже если и можно, то не стоит ими это проверять, с помошью стека это все пройдет быстрей, проще и понятней.
Ответ написан
alexmuz
@alexmuz
На PHP:
$balanced = !preg_match("/[()]/", preg_replace("/\((((?>[^()]+)|(?R))*)\)/", "", $string));
Это в том числе для строк вида: aaa(bb)cc

Но это извращение, лучше делать как написал Mithgol.
Ответ написан
@andrewsh
Лучше это не делать через регулярные выражения. См. также Chomsky hierarchy и здесь.
Ответ написан
Laplace
@Laplace
Эта задача неразрешима в регулярных выражениях и в конечных автоматах (эквивалентные средства), требует автомата с магазинной памятью, то бишь стека. Хотя если максимальная глубина скобок ограниченна, то какое-то некрасивое решение наверное можно придумать.
Ответ написан
@temaHT
Regexp-в не то средство которым нужно решать такого плана задачу. Они не предназначены для работы с вложенными/рекурсивными структурами.
Теоретически конечно можно изголится и выдать некое решение. Все зависит насколько «умный» должен быть алгоритм.
Правильное решение для простого случая (когда больше ничего кроме проверки скобочек не иребуется) — простая функция на вашем любимом языке которая считает скобочки. Для более продвинутых случаев — библиотека для лексического/синтаксического анализа.
Ответ написан
@ivsedm
Ну как вариант, можно с помощью такого выражения \((?=[^\(]*\)).*?\) последовательно заменить все скобки на пробелы (оно убирает самую вложенную скобку), а дальше поискать в строке "(" либо ")", если найдем, значит баланс кривой.
Но проще все таки для балансировки два счетчика и один проход по строке :)
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы