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

Есть ли способ с помощью регулярных выражений проверить баланс скобочек в строках типа ((()(()()))())? Лично мне такой способ неизвестен. Может, я не знаю чего-то?
  • Вопрос задан
  • 6248 просмотров
Решения вопроса 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
Ну как вариант, можно с помощью такого выражения \((?=[^\(]*\)).*?\) последовательно заменить все скобки на пробелы (оно убирает самую вложенную скобку), а дальше поискать в строке "(" либо ")", если найдем, значит баланс кривой.
Но проще все таки для балансировки два счетчика и один проход по строке :)
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
от 80 000 до 220 000 руб.
от 100 000 до 200 000 руб.
iGooods.ru Санкт-Петербург
от 120 000 до 180 000 руб.
21 сент. 2019, в 00:13
5000 руб./за проект
20 сент. 2019, в 20:02
3000 руб./за проект
20 сент. 2019, в 19:04
80000 руб./за проект