Revertir una expresión regular

27

El reto

Dada una expresión regular válida, genere una expresión regular que coincida con el mismo conjunto de cadenas, pero invertida.

La tarea

Este reto utiliza la mayoría de las operaciones básicas de expresiones regulares: ^, $, ?, +, *, [], {}, |. No existen grupos de captura ni ninguna de esas cosas complicadas. Se pueden escapar caracteres especiales.

Muestra de entrada / salida

Nota: ¡Nunca se darán datos no válidos, y generalmente hay múltiples respuestas posibles para un ingreso dado!

Input      | Sample Output
-----------|-------------
abc        | cba
tuv?       | v?ut
a(b|c)     | (c|b)a
1[23]      | [23]1
a([bc]|cd) | (dc|[bc])a
^a[^bc]d$  | ^d[^bc]a$
x[yz]{1,2} | [yz]{1,2}x
p{2}       | p{2}
q{7,}      | q{7,}
\[c[de]    | [de]c\[
ab[c       | <output undefined>
a(?bc)     | <output undefined>
a[]]bc     | <output undefined>

Manifestación

Demostración de trabajo que demuestra entradas / salidas correctas. Esto tiene una lógica adicional para validar entradas que no son necesarias en una respuesta real. Considere entradas no válidas como comportamiento indefinido.

Detalles específicos

Por simplicidad, todos los caracteres especiales tienen su significado especial o se escapan; es decir, [[]no es un rango de caracteres para [. Los rangos de longitud provienen de ERE POSIX estándar; es decir, {n}, {n,}, y {n,m}son compatibles. Los rangos de caracteres []y [^]son compatibles. Debido a estas reglas, y dado que no se proporciona una entrada no válida, realmente solo necesita copiar el contenido de estas directamente a la salida. Por último, la codicia no importa, es decir, no importa si la expresión regular invertida encuentra una coincidencia diferente primero, solo necesita encontrar una coincidencia para el mismo conjunto de cadenas.

Tanteo

El programa más pequeño en bytes (salvo trampas como solicitudes de red) gana. El programa puede usar IO real o simplemente definir una función.

TND
fuente
1
Porque no hay nada a lo ?que apegarse. Intenta escribir /a(?bc)/en la consola del navegador.
TND
3
Se ve bien ahora. Sin (^a|b)(c$|d)embargo, es posible que desee agregar algo como un caso de prueba.
Martin Ender
¿Podemos suponer que la entrada contendrá solo caracteres ASCII imprimibles? En particular, ¿no hay caracteres de salto de línea?
Martin Ender
1
¿Deberíamos considerar los calificadores aplicados en grupos, es decir, (a)?(b)+(b)+(a)??
kennytm
1
Falta su lista de operaciones de expresiones regulares (), que se utiliza en su ejemplo.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Respuestas:

7

Retina , 136 114 110 bytes

Hola, te escuché como regex ...

^
;
(T`^$`$^`;.
(.*);(\[(\\.|[^]])*]|\\.|.)([*+?]|{\d+(,|,\d+)?})?
$2$4!$1;
^\(!
) 
^\)(.*)!(.+?) 
($2$1
;$|!
<empty>

Donde <empty>representa una línea final vacía. Ejecute el código desde un solo archivo con la -sbandera.

... cuando quieras regex reverso debes usar regex. Cuando desee usar expresiones regulares, debe usar un lenguaje de programación basado en expresiones regulares.

Este código se supone que la entrada no contiene ni ;ni !ni espacios. Si bien estoy de acuerdo en que es una suposición bastante fuerte y potencialmente inválida, podría reemplazar esos tres en el código con cualquiera de los tres caracteres no imprimibles (como bytes nulos, carácter de campana, <DEL>lo que sea), y no afectaría el tamaño o la funcionalidad del código en absoluto.

Agregaré una explicación cuando termine de jugar al golf.

Martin Ender
fuente
3
"Rebaño * estás acostado *"
lirtosiast
Creo que el código también supone que la expresión regular no contiene ningún carácter de línea nueva sin procesar.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oh, eso es cierto, estaba bajo la suposición de que no habrá caracteres no imprimibles en la entrada. Lo arreglaré una vez que obtengamos una aclaración del OP. (Si puede aparecer algún personaje, todavía hay ciertas combinaciones que no aparecerán en lo que este desafío considera una expresión regular válida, por ejemplo ]]], de cualquier manera, esta respuesta no necesitará mucha modificación).
Martin Ender
¿Ha jugado golf después de más de un año? : P
Okx
2

JavaScript ES6, 574 bytes

Probablemente pueda eliminar algunas vardeclaraciones.

R=e=>{for(var s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push("\\"+e[t]);break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:var l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push("("+a+")"),s=0)}c.reverse(),r=c;var i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JS ES6, no probado, 559 bytes

Lo probaré en casa.

R=e=>{for(s=0,c=[],h=/(\?|\+|\{\d*,*\d*\}|\*)(\?*)/,t=0;t<e.length;t++)switch(s){case 0:switch(e[t]){case"\\":t++,c.push`\\${e[t]}`;break;case"[":j=t,s=1;break;case"(":k=t,s=2;break;default:l=e.search(h,t);(l>=t+1||0>l)&&c.push(l==t+1?e[t]+e.slice(t,e.length).match(h)[0]:e[t])}break;case 1:"\\"==e[t]?t++:"]"==e[t]&&(c.push(e.slice(j,t+1)+(e.search(h,t)==t+1?e.slice(t,e.length).match(h)[0]:"")),s=0);break;case 2:"\\"==e[t]?t++:")"==e[t]&&(a=R(e.slice(k+1,t)),c.push`(${a})`,s=0)}c.reverse(),r=c;i=c.length-1;return"^"==c[i]&&(r[i]="$"),"$"==c[0]&&(r[0]="^"),r.join``}}

JavaScript ES5, sin golf, 961 bytes

function revRegex(str){
 var mode = 0;
 var oS = [];
 var post = /(\?|\+|\{\d*,*\d*\}|\*)(\?*)/;
 for(var i=0;i<str.length;i++){
  switch(mode){
   case 0: switch(str[i]){
    case "\\": i++; oS.push("\\"+str[i]); break;
    case "[": j=i; mode = 1; break;
    case "(": k=i; mode = 2; break;
    default:
     var pLoc = str.search(post,i);
     if(pLoc>=i+1||pLoc<0){ // current is not pLoc
      if(pLoc==i+1){
       oS.push(str[i] + str.slice(i,str.length).match(post)[0]);
      } else {
       oS.push(str[i]);
      }
     }
   }; break;
   case 1: if(str[i]=="\\") i++; else if(str[i]=="]"){oS.push

(str.slice(j,i+1)+(str.search(post,i)==i+1?str.slice

(i,str.length).match(post)[0]:""));mode = 0}; break;
   case 2: if(str[i]=="\\") i++; else if(str[i]==")")

{a=revRegex(str.slice(k+1,i));oS.push("("+a+")");mode = 

0};break;
  }
 }
 oS.reverse();
 r=oS;
 var l=oS.length-1;
 if(oS[l]=="^") r[l]="$";
 if(oS[0]=="$") r[0]="^";
 return r.join("");
}
Conor O'Brien
fuente
55
jajaja,
usaste
3
@ ΚριτικσιΛίθος Sí, lo hice: D Lo usaría para analizar HTML si pudiera ...
Conor O'Brien el
44
"si pudieras"
Optimizer
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ analicé los códigos html con regex pero tuve un serio problema con los caracteres unicode
Abr001am
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Esta es una alternativa: `code.replace (/.*/," trollolol ");
Kritixi Lithos
2

JavaScript ES6, 343 bytes

t=r=>(u="substr",T="(?:[+?*]|{\\d+(?:,\\d*)?})?)([^]*)",(c=r[0])=="(")?([n,s]=v(r[u](1)),[_,q,s]=s.match("^(\\)"+T),["("+n+q,s]):c==")"||c==null?["",r]:c=="^"?["^",r[u](1)]:c=="$"?["^",r[u](1)]:r.match("^("+/(?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])/.source+T).slice(1);(v=r=>{var o="";do{[n,r]=t(r);o=n+o;}while(n&&r);return[o,r]})(prompt())[0]

Código original (las funciones, pero sin prompt):

function reverse(regex) {
    var out = "";
    do {
        // console.log("calling term");
        var [node, regex] = term(regex);
        // console.log("reverse: " + [node, regex]);
        out = node + out;
    } while (node && regex);
    return [out, regex];
}

function term(regex) {
    switch (regex[0]) {
        case "(":
            // console.log("calling reverse");
            var [node, sequel] = reverse(regex.substr(1));
            // console.log("term: " + regex + " / " + [node, sequel]);
            var [_, quantifier, sequel] = sequel.match(/^(\)(?:[+?*]|{\d+(?:,\d*)?})?)([^]*)/);
            return ["(" + node + quantifier, sequel];
        case ")":
        case void 0:
            return ["", regex];
        case "^":
            return ["$", regex.substr(1)];
        case "$":
            return ["^", regex.substr(1)];
        default:
            return regex.match(/^((?:\[(?:[^\]\\]|\\[^])*\]|[^[\\]|\\[^])(?:[+?*]|{\d+(?:,\d+)?})?)([^]*)/).slice(1);
    }
}

reverse("^\\(([The(){}*\\] ]{2,3}world\\\\(begin(ner|ning)?|ends*)+|Con\\|ti\\*n\\)ue...[^%\\[\\]()\\\\])$")[0]

El código se implementa como un analizador recursivo de arriba hacia abajo, por lo que puede causar un desbordamiento de la pila en la entrada profundamente anidada.

El código puede causar un bucle infinito en casos no válidos, ya que no los pruebo, aprovechando la cláusula de "comportamiento indefinido".

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
fuente
0

Python 3, 144 bytes

(Este no admite calificadores en un grupo como (a)+(b)*(cde)?).

import re;f=lambda x:''.join({e:e,'^':'$','$':'^','(':')',')':'('}[e]for e in re.findall(r'(?:\\.|\[(?:\\?.)+?\]|.)(?:[?+*]|\{.+?\})?',x)[::-1])

Casos de prueba:

test_cases = [
    # Provided test cases
    r'abc',
    r'tuv?',
    r'a(b|c)',
    r'1[23]',
    r'a([bc]|cd)',
    r'^a[^bc]d$',
    r'x[yz]{1,2}',
    r'p{2}',
    r'q{7,}',
    r'\[c[de]',

    # Pathological cases
    r'a{3}b',
    r'(a)?(b)+',            # <-- currently failing!
    r'[\[]{5}[^\]]{6}',
    r'[\[]\]{7}',
    r'[\[\]]{8,9}',
    r'\(\)\^\$',

    # Undefined cases
    r'ab[c',
    r'a(?bc)',
    r'a[]]bc',
]

for t in test_cases:
    print(t, '->', f(t))

Resultado:

abc -> cba
tuv? -> v?ut
a(b|c) -> (c|b)a
1[23] -> [23]1
a([bc]|cd) -> (dc|[bc])a
^a[^bc]d$ -> ^d[^bc]a$
x[yz]{1,2} -> [yz]{1,2}x
p{2} -> p{2}
q{7,} -> q{7,}
\[c[de] -> [de]c\[
a{3}b -> ba{3}
(a)?(b)+ -> )+b))?a)                    # <-- note: wrong
[\[]{5}[^\]]{6} -> [^\]]{6}[\[]{5}
[\[]\]{7} -> \]{7}[\[]
[\[\]]{8,9} -> [\[\]]{8,9}
\(\)\^\$ -> \$\^\)\(
ab[c -> c[ba
a(?bc) -> (cb(?a
a[]]bc -> cb[]]a
kennytm
fuente