2012-02-24 40 views
5

Este es un caso obvio de "lo estás haciendo mal". Yo en realidad no tenemos intención de hacer esto, pero una conversación en el trabajo espoleé esta pregunta:Usar expresiones regulares para comparar números

¿Se puede generar una expresión regular para determinar si un número entero es menor que un valor arbitrario.

Para algunos valores esto es fácil. Para enteros menores de 1000, \ d {1,3} debería hacer el truco. Para los enteros < 500, es un poco más complicado, pero no tan malo, ya que puedes usar [0-4] {0,1} \ d {1,2}.

Una vez que se llega a los valores arbitrarios se vuelve mucho más complicado. Por ejemplo, todos los números menores que 255 serían algo así como \ d {1,2} | [0-1] \ d {2} | [2] [0-4] \ d | [2] [5] [0-4].

¿Hay una sola expresión regular que funcione aquí? ¿O tienes que generar programáticamente la expresión regular?

(Y de nuevo, permítanme señalar que no tengo ninguna intención de realmente hacer esto. Es evidente que el uso de "foo < bar" en su lenguaje de programación favorito es mucho más eficiente y fácil de leer.)

+0

Se puede combinar las tres expresiones que tienen que obtener uno solo si eso es lo que quiere decir. – Dervall

Respuesta

3

Usted' va a necesitar generar la expresión para cada número delimitador. Digamos que había una expresión regular que haría el trabajo. Entonces esa expresión regular debería ser capaz de tomar como entrada una secuencia de caracteres. Sin embargo, sabemos que las expresiones regulares y los autómatas de estados finitos son equivalentes, por lo que esto es lo mismo que decir que podemos construir un FSM ya que el número posible es ilimitado, que requeriría un número ilimitado de estados, lo que contradice la definición de FSA.

+0

¿Eh? ¿Estás diciendo que no se puede hacer, o es esta una forma realmente divertida de decir que sí? ¿Estás aludiendo a los números negativos, a pesar de que el PO claramente implica espacio de números no negativos? – tripleee

+0

No se puede hacer. No puede escribir una expresión regular que, en general, le dirá si un número arbitrario es mayor que un límite arbitrario, porque no son finitos. –

+0

Si OP significa solo un número en particular, puede hacerlo trivialmente: enumuerate todos los valores debajo de su límite. Entonces, si se siente ambicioso, minimice el FSM correspondiente y use la expresión regular mínima. –

2

Esto es bastante fácil.

#!/usr/bin/env perl 
use strict; 
use warnings; 
use Regexp::Assemble; 

for my $n (@ARGV) { 
    my $asm = new Regexp::Assemble; 
    for (1 .. $n) { $asm->add($_) } 
    for ($asm->re){ 
     s/\)$/\$/; 
     s/^[^:]*:/^/; 
     print "$n => /$_/\n"; 
    } 
} 

Ahora ejecutarlo para encontrar el patrón que coincida con números enteros entre 1 y ese número:

$ perl /tmp/ra 5 15 153 401 1144 
5 => /^[12345]$/ 
15 => /^(?:[23456789]|1[]?)$/ 
153 => /^(?:1(?:[6789]|5[0123]?|0\d?|1\d?|2\d?|3\d?|4\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
401 => /^(?:1(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:[123456789]|0[01]?)?|5\d?|6\d?|7\d?|8\d?|9\d?)$/ 
1144 => /^(?:1(?:0(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|1(?:[56789]|4[]?|0\d?|1\d?|2\d?|3\d?)?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|2(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|3(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|4(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|5(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|6(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|7(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|8(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?|9(?:0\d?|1\d?|2\d?|3\d?|4\d?|5\d?|6\d?|7\d?|8\d?|9\d?)?)$/ 
Cuestiones relacionadas