Regex para comprobar si una cadena tiene paréntesis no coincidentes?

Question

En una secuencia de comandos de PHP, ¿qué expresiones regulares debo usar para buscar paréntesis no coincidentes en una cadena? Cosas que quiero para permitir que incluyen:

• Esta es (bueno)
• Este (es) (OK)

cosas que quiero para impedir:

• Esto es) malo (
• Esto también (malo
• Esto es (malo (también)

Gracias!

Actualización: Ustedes todos rock. Hacer esto con una expresión regular parecía más complicado de lo que debería, y este tipo de respuestas de segundo nivel es lo que hace que stackoverflow sea hermoso. Gracias por los enlaces y el pseudocódigo. No estoy seguro de a quién dar la respuesta, así que me disculpo con todos cuyas respuestas no puedo aceptar.

Answer 1

Regex no es la herramienta adecuada para el trabajo. Escanee una cadena manualmente.

Pseudo-código:

depth = 0 
for character in some_string: 
    depth += character == '(' 
    depth -= character == ')' 
    if depth < 0: 
     break 

if depth != 0: 
    print "unmatched parentheses" 

Answer 2

No es posible lograr esto con una expresión regular. La coincidencia de paréntesis requiere una función recursiva/de recuento que no está disponible en una expresión regular. Necesitarás un analizador para esto.

Más detalles disponibles aquí: http://blogs.msdn.com/jaredpar/archive/2008/10/15/regular-expression-limitations.aspx

Answer 3

para extender la respuesta de JaredPar, no es muy difícil de resolver sin necesidad de utilizar una expresión regular, acaba de escribir una función que examina cada carácter de la cadena y se incrementa/decrementa un contador. Si encuentra un "(", increméntelo, y si encuentra un ")", disminuya. Si el contador alguna vez cae por debajo de 0, puede romperse, la cadena no es válida. Cuando procesaste toda la cadena, si el contador no es 0, hubo un paréntesis abierto sin igual.

Answer 4

Sus ejemplos no incluyen ningún paréntesis anidados ... si no tienen que ver con la anidación, entonces esto se puede hacer mediante la siguiente expresión:

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

Esto coincidirá con todas las cadenas en su lista de "permitir" y fallará contra las cadenas en su lista de "prevención". Sin embargo, también fallará contra cualquier cadena con paréntesis anidados. p.ej. "this (is (ok) ok)"

Como ya se ha señalado, las expresiones regulares no son la herramienta correcta si necesita manejar el anidamiento.

Answer 5

Estoy de acuerdo con el hecho de que esto es imposible con un REGEX. Se podría hacer lo siguiente, sin embargo:

<?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; 
} 

?> 

Answer 6

¿Por qué no es posible con una expresión regular

Las otras respuestas son los correctos, pero sólo quiero poner en un enchufe para la informática teórica .. .este es un caso donde conocer la teoría proporciona una ventaja práctica real.

Una expresión regular corresponde a un autómata finito determinista (DFA), pero la coincidencia de pares requiere una gramática libre de contexto, que puede realizarse como un autómata finito (PDA) pero no por un DFA.

Debido a esto, sin mucho trabajo cerebral adicional, sabemos que la respuesta es no, y no tenemos que preocuparnos de que haya algo que simplemente estamos pasando por alto. Por lo tanto, puede estar seguro de las respuestas anteriores, y no se preocupe de que los autores estén pasando por alto algo cuando dan esa respuesta.

Casi todos los libros del compilador hablar de esto, aquí está un resumen rápido:

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

Answer 7

Usted puede hacer esto con una expresión regular - PCRE, tal como se utiliza por PHP, permite patrones recursivos. El Manual de PHP da una example que es casi exactamente lo que quiere:

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

Esto concuerda con cualquier subcadena correctamente parenthesised el tiempo que comienza y termina con paréntesis. Si desea asegurarse de toda la cadena es equilibrada, permitiendo cadenas como "wiggedy (wiggedy) (wiggedy (Wack))", esto es lo que ocurrió:

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

He aquí una explicación del patrón, el cual puede ser más esclarecedor que obfuscatory:

 
^    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 

Hay un montón de consideraciones de eficacia y la corrección que se presentan con este tipo de expresiones regulares. Ten cuidado.

Answer 8

php Trabajar sin expresiones regulares:

function analyse($input){ 
    $len = strlen($input); 
    $depth = 0; 
    for ($i = 0; $i < $len; $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 
}