Generalización para la expresión regular en cualquier lista

Question

Estoy trabajando con una lista grande que contiene enteros y me gustaría hacer una coincidencia de patrones en ellos (como encontrar ciertas secuencias). Las expresiones regulares serían la opción perfecta, excepto que siempre parecen manejar solo listas de caracteres, a.k.a. cadenas. ¿Hay alguna biblioteca (en cualquier idioma) que pueda manejar listas de un tipo arbitrario?

Soy consciente de que podría convertir mi lista de enteros en una cadena y luego hacer una búsqueda normal de expresiones regulares, pero eso parece un poco derrochador y poco elegante.

edición:

Mis requisitos son bastante simples. No hay necesidad de listas anidadas, no hay necesidad de clases de personajes extravagantes. Básicamente me interesan las ocurrencias de secuencias que pueden ser bastante complicadas. (por ejemplo, algo como "[abc]{3,}.([ab]?[^a]{4,7})", etc. donde a, b, c son enteros). Esto debería ser posible generalizar sobre cualquier tipo que se pueda verificar para la igualdad. Para un tipo enumerable también puede obtener cosas como "[a-z]" para trabajar.

Answer 1

Las expresiones regulares coinciden solo con cadenas, by definition.

Por supuesto, en teoría, podría construir una gramática equivalente, por ejemplo, para listas de números. Con las nuevas fichas como \e de números pares, \o de números impares, \s para los números cuadrados, \r para los números reales etc., para que

[1, 2, 3, 4, 5, 6] 

podría verse igualado por

^(\o\e)*$ 

o

[ln(3), math.pi, sqrt(-1)] 

se correspondería con

^\R*$ 

etc. Suena como un proyecto divertido, pero también como uno muy difícil. Y cómo podría expandirse para manejar listas arbitrarias, anidadas y todo, está más allá de mí.

Answer 2

Si realmente necesita una gramática libre como en expresiones regulares, entonces tiene que seguir el camino descrito en la respuesta de Tim. Si solo tiene un número fijo de patrones para buscar, entonces la forma más fácil y rápida es escribir sus propias funciones de búsqueda/filtro.

Answer 3

Problema interesante de hecho.

Pensamiento lateral: descargue .Net Framework Source code, levante el código fuente de Regex y adáptelo para trabajar con enteros en lugar de caracteres.

Solo una idea.

Answer 4

Parte de la sintaxis de expresiones regulares se generaliza a secuencias genéricas. Además, para poder especificar cualquier objeto, las cadenas no son el mejor medio para la expresión.

ejemplo "pequeño" en pitón:

def choice(*items): 
    return ('choice',[value(item) for item in items]) 

def seq(*items): 
    return ('seq',[value(item) for item in items]) 

def repeat(min,max,lazy,item): 
    return ('repeat',min,max,lazy,value(item)) 

def value(item): 
    if not isinstance(item,tuple): 
    return ('value',item) 
    return item 

def compile(pattern): 
    ret = [] 
    key = pattern[0] 
    if key == 'value': 
    ret.append(('literal',pattern[1])) 
    elif key == 'seq': 
    for subpattern in pattern[1]: 
     ret.extend(compile(subpattern)) 
    elif key == 'choice': 
    jumps = [] 
    n = len(pattern[1]) 
    for i,subpattern in enumerate(pattern[1]): 
     if i < n-1: 
     pos = len(ret) 
     ret.append('placeholder for choice') 
     ret.extend(compile(subpattern)) 
     jumps.append(len(ret)) 
     ret.append('placeholder for jump') 
     ret[pos] = ('choice',len(ret)-pos) 
     else: 
     ret.extend(compile(subpattern)) 
    for pos in jumps: 
     ret[pos] = ('jump', len(ret)-pos) 
    elif key == 'repeat': 
    min,max,lazy,subpattern = pattern[1:] 
    for _ in xrange(min): 
     ret.extend(compile(subpattern)) 
    if max == -1: 
     if lazy: 
     pos = len(ret) 
     ret.append('placeholder for jump') 
     ret.extend(compile(subpattern)) 
     ret[pos] = ('jump',len(ret)-pos) 
     ret.append(('choice',pos+1-len(ret))) 
     else: 
     pos = len(ret) 
     ret.append('placeholder for choice') 
     ret.extend(compile(subpattern)) 
     ret.append(('jump',pos-len(ret))) 
     ret[pos] = ('choice',len(ret)-pos) 
    elif max > min: 
     if lazy: 
     jumps = [] 
     for _ in xrange(min,max): 
      ret.append(('choice',2)) 
      jumps.append(len(ret)) 
      ret.append('placeholder for jump') 
      ret.extend(compile(subpattern)) 
     for pos in jumps: 
      ret[pos] = ('jump', len(ret)-pos) 
     else: 
     choices = [] 
     for _ in xrange(min,max): 
      choices.append(len(ret)) 
      ret.append('placeholder for choice') 
      ret.extend(compile(subpattern)) 
      ret.append(('drop,')) 
     for pos in choices: 
      ret[pos] = ('choice',len(ret)-pos) 
    return ret 

def match(pattern,subject,start=0): 
    stack = [] 
    pos = start 
    i = 0 
    while i < len(pattern): 
    instruction = pattern[i] 
    key = instruction[0] 
    if key == 'literal': 
     if pos < len(subject) and subject[pos] == instruction[1]: 
     i += 1 
     pos += 1 
     continue 
    elif key == 'jump': 
     i += instruction[1] 
     continue 
    elif key == 'choice': 
     stack.append((i+instruction[1],pos)) 
     i += 1 
     continue 
    # fail 
    if not stack: 
     return None 
    i,pos = stack.pop() 
    return pos 

def find(pattern,subject,start=0): 
    for pos1 in xrange(start,len(subject)+1): 
    pos2 = match(pattern,subject,pos1) 
    if pos2 is not None: return pos1,pos2 
    return None,None 

def find_all(pattern,subject,start=0): 
    matches = [] 
    pos1,pos2 = find(pattern,subject,start) 
    while pos1 is not None: 
    matches.append((pos1,pos2)) 
    pos1,pos2 = find(pattern,subject,pos2) 
    return matches 

# Timestamps: ([01][0-9]|2[0-3])[0-5][0-9] 
pattern = compile(
    seq(
    choice(
     seq(choice(0,1),choice(0,1,2,3,4,5,6,7,8,9)), 
     seq(2,choice(0,1,2,3)), 
    ), 
    choice(0,1,2,3,4,5), 
    choice(0,1,2,3,4,5,6,7,8,9), 
) 
) 

print find_all(pattern,[1,3,2,5,6,3,4,2,4,3,2,2,3,6,6,5,3,5,3,3,2,5,4,5]) 
# matches: (0,4): [1,3,2,5]; (10,14): [2,2,3,6] 

Unos puntos de mejora:

• más construcciones: clases con negación, oscila
• clases en lugar de tuplas

Answer 5

Bueno, Erlang tiene una coincidencia de patrones (de su tipo) integrada. Hice algo similar onc e en Ruby - un poco de piratería probablemente no demasiado bien, vea http://radiospiel.org/0x16-its-a-bird

Answer 6

Puede probar pamatcher, es una biblioteca de JavaScript que generaliza la noción de expresiones regulares para cualquier secuencia de elementos (de cualquier tipo).

Un ejemplo para "[abc] {3,} (? [Ab] [^ a] {4,7})" coincidencia de patrones, donde a, b, c son números enteros:

var pamatcher = require('pamatcher'); 

var a = 10; 
var b = 20; 
var c = 30; 

var matcher = pamatcher([ 
    { repeat: 
     { or: [a, b, c] }, 
    min: 3 
    }, 
() => true, 
    { optional: 
    { or: [a, b] } 
    }, 
    { repeat: (i) => i != a, 
    min: 4, 
    max: 7 
    } 
]); 

var input = [1, 4, 8, 44, 55]; 
var result = matcher.test(input); 
if(result) { 
    console.log("Pattern matches!"); 
} else { 
    console.log("Pattern doesn't match."); 
} 

Nota: Soy el creador de esta biblioteca.