Regex для проверки того, имеет ли строка несогласованные скобки?
В PHP script, какое регулярное выражение следует использовать для проверки несогласованных скобок в строке? Вещи, которые я хочу разрешить, включают:
Вещи, которые я хочу предотвратить:
- Это) плохо (
- Это также (плохой
- Это (плохо) (тоже)
Спасибо!
Обновление: вы, ребята, все рок. Выполнение этого с помощью регулярного выражения казалось более сложным, чем должно было быть, и эти ответы второго уровня - вот что делает stackoverflow красивым. Спасибо за ссылки и псевдокод. Я не уверен, кому дать ответ, поэтому я приношу свои извинения всем, чьи ответы я не могу принять.
Ответы
Ответ 1
Regex не подходит для работы. Сканирование строки вручную.
Псевдо-код:
depth = 0
for character in some_string:
depth += character == '('
depth -= character == ')'
if depth < 0:
break
if depth != 0:
print "unmatched parentheses"
Ответ 2
Вы можете сделать это с помощью регулярного выражения - PCRE, используемый PHP, позволяет рекурсивные шаблоны. Руководство PHP дает пример, который почти точно вы хотите:
\(((?>[^()]+)|(?R))*\)
Это соответствует любой правильно заключенной в скобки подстроке до тех пор, пока она начинается и заканчивается круглыми скобками. Если вы хотите, чтобы вся строка была сбалансирована, это позволяет использовать строки
"wiggedy (wiggedy) (wiggedy (wack))", вот что я придумал:
^((?:[^()]|\((?1)\))*+)$
Здесь объясняется картина, которая может быть более освещающей, чем обфускаторная:
^ Beginning of the string
( Start the "balanced substring" group (to be called recursively)
(?: Start the "minimal balanced substring" group
[^()] Minimal balanced substring is either a non-paren character
| or
\((?1)\) a set of parens containing a balanced substring
) Finish the "minimal balanced substring" group
* Our balanced substring is a maximal sequence of minimal
balanced substrings
+ Don't backtrack once we've matched a maximal sequence
) Finish the "balanced substring" pattern
$ End of the string
Есть много соображений эффективности и правильности, которые возникают с этими типами регулярных выражений. Будьте осторожны.
Ответ 3
Невозможно выполнить это с помощью регулярного выражения. Согласование скобок требует рекурсивной/счетной функции, недоступной в регулярном выражении. Для этого вам понадобится парсер.
Более подробная информация доступна здесь: http://blogs.msdn.com/jaredpar/archive/2008/10/15/regular-expression-limitations.aspx
Ответ 4
Согласитесь с тем, что это невозможно с 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;
}
?>
Ответ 5
В ваших примерах нет вложенных круглых скобок... если вы не связаны с вложением, то это можно сделать, используя следующее выражение:
^[^()]*(?:\([^()]*\)[^()]*)*$
Это будет соответствовать всем строкам в списке "разрешить" и не будет выполняться против строк в списке "предотвратить". Тем не менее, он также потерпит неудачу в отношении любой строки с вложенными круглыми скобками. например "это ((не) нормально)"
Как уже указывали другие, регулярные выражения не являются правильным инструментом, если вам нужно обрабатывать вложенность.
Ответ 6
Чтобы продлить ответ JaredPar, его не очень сложно решить без использования регулярного выражения, просто напишите функцию, которая проверяет каждый символ в строке и увеличивает/уменьшает счетчик. Если вы найдете "(", увеличьте его, и если вы найдете ")", уменьшите его. Если счетчик когда-либо опускается ниже 0, вы можете сломаться, строка недействительна. Когда вы обработали всю строку, если счетчик не равен 0, была открытая открытая скобка.
Ответ 7
Почему это невозможно с регулярным выражением
Другие ответы правильны, но я просто хочу вставить пробную версию для теоретической информатики... это случай, когда знание теории дает практическое практическое преимущество.
Регулярное выражение соответствует детерминированному конечному автомату (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
Ответ 8
Рабочая 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
}