Regex для проверки того, имеет ли строка несогласованные скобки?

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

  • Хорошо)
  • Хорошо)

Вещи, которые я хочу предотвратить:

  • Это плохо(
  • Это также (плохо
  • Это (плохо (тоже)

Благодаря!

Обновление: Вы, ребята, все рок. Выполнение этого с помощью регулярного выражения казалось более сложным, чем должно было быть, и эти ответы второго уровня – вот что делает stackoverflow красивым. Спасибо за ссылки и псевдокод. Я не уверен, кому дать ответ, поэтому я приношу свои извинения всем, чьи ответы я не могу принять.

Solutions Collecting From Web of "Regex для проверки того, имеет ли строка несогласованные скобки?"

Regex не подходит для работы. Сканирование строки вручную.

Псевдо-код:

depth = 0 for character in some_string: depth += character == '(' depth -= character == ')' if depth < 0: break if depth != 0: print "unmatched parentheses" 

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

 \(((?>[^()]+)|(?R))*\) 

Это соответствует любой правильно заключенной в скобки подстроке до тех пор, пока она начинается и заканчивается круглыми скобками. Если вы хотите обеспечить сбалансированность всей строки, позволяя использовать такие строки, как «wiggedy (wiggedy) (wiggedy (wack))», вот что я придумал:

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

Вот объяснение шаблона, который может быть более освещающим, чем обфускатор:

 ^ Начало строки
 (Запустите группу «сбалансированная подстрока» (которая будет называться рекурсивно)
   (?: Начать группу «минимальная сбалансированная подстрока»
     [^ ()] Минимальная сбалансированная подстрока является либо символом без парнера
     |  или
     \ ((? 1) \) набор парнеров, содержащих сбалансированную подстроку
   ) Завершите группу «минимальная сбалансированная подстрока»
   * Наша сбалансированная подстрока - это максимальная последовательность минимальных
               сбалансированные подстроки
   + Не отступайте, как только мы сопоставим максимальную последовательность
 ) Завершите шаблон «сбалансированной подстроки»
 $ Конец строки

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

Невозможно выполнить это с помощью регулярного выражения. Согласование скобок требует рекурсивной / счетной функции, недоступной в регулярном выражении. Для этого вам понадобится парсер.

Более подробная информация доступна здесь: http://blogs.msdn.com/jaredpar/archive/2008/10/15/regular-expression-limitations.aspx

Согласитесь с тем, что это невозможно с REGEX. Вы могли бы сделать следующее:

 <?php $testStrings = array( 'This is (ok)', 'This (is) (ok)', 'This is )bad(', 'This is also (bad', 'This is (bad (too)' ); foreach( $testStrings as $string ) { $passed = hasMatchedParentheses( $string ) ? 'passed' : 'did not pass'; echo "The string $string $passed the check for matching parenthesis.\n"; } function hasMatchedParentheses( $string ) { $counter = 0; $length = strlen( $string ); for( $i = 0; $i < $length; $i ++ ) { $char = $string[ $i ]; if( $char == '(' ) { $counter ++; } elseif( $char == ')' ) { $counter --; } if( $counter < 0 ) { return false; } } return $counter == 0; } ?> 

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

 ^[^()]*(?:\([^()]*\)[^()]*)*$ 

Это будет соответствовать всем строкам в вашем списке «разрешить» и провалиться против строк в списке «предотвратить». Тем не менее, он также будет терпеть неудачу против любой строки с вложенными круглыми скобками . например «это ((не) нормально)»

Как уже указывали другие, регулярные выражения не являются правильным инструментом, если вам нужно обрабатывать вложенность.

Чтобы продлить ответ JaredPar, это не очень сложно решить без использования регулярного выражения, просто напишите функцию, которая проверяет каждый символ в строке и увеличивает / уменьшает счетчик. Если вы найдете «(», увеличьте его, и если вы найдете «)», уменьшите его. Если счетчик когда-либо опускается ниже 0, вы можете сломаться, строка недействительна. Когда вы обработали всю строку, если счетчик не равен 0, была открытая открытая скобка.

Почему это невозможно с регулярным выражением

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

Регулярное выражение соответствует детерминированному конечному автомату (DFA), но для сопоставления парнов требуется контекстно-свободная грамматика, которая может быть реализована как конечный автомат (PDA), а не DFA.

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

Об этом расскажут почти все книги компиляторов, вот краткий обзор:

http://books.google.com/books?id=4LMtA2wOsPcC&pg=PA94&lpg=PA94&dq=push-down+finite+automata&source=bl&ots=NisYwNO1r0&sig=ajaSHFXwpPOWG8IfbcfKoqzS5Wk&hl=en&ei=m26cSdf6DZGYsAPB-6SsAg&sa=X&oi=book_result&resnum=6&ct=result

Что сказал Джаред … Не могу этого сделать. Я даже не думаю, что вы можете сделать это с # 1 # 2, который Perl дает вам …

Рабочая php без регулярного выражения:

 function analyse($input){ $depth = 0; for ($i = 0; $i < strlen($input); $i++) { $depth += $input[$i] == '('; $depth -= $input[$i] == ')'; if ($depth < 0) break; } if ($depth != 0) return false; else return true; } $check_nestled = analyse('(5 * 2) + ((2 + 2) - 4)'); if($check_nestled){ // do stuff, everything is ok }