Inverter uma regex

27

O desafio

Dada uma regex válida, produza uma regex que corresponda ao mesmo conjunto de cadeias, mas invertida.

A tarefa

Este desafio utiliza o maior número de operações básicas de regex: ^, $, ?, +, *, [], {}, |. Não existem grupos de captura ou coisas complicadas. Caracteres especiais podem ser escapados.

Entrada / Saída de amostra

Nota: Entrada inválida nunca será fornecida e geralmente existem várias respostas possíveis para uma entrada especificada!

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>

Demo

Demonstração de trabalho que demonstra entradas / saídas corretas. Isso tem alguma lógica adicional para validar entradas desnecessárias em uma resposta real. Considere entradas inválidas como comportamento indefinido.

Específicos

Por simplicidade, todos os caracteres especiais têm um significado especial ou são escapados; isto é, [[]não é um intervalo de caracteres para [. As faixas de comprimento são provenientes dos EREs POSIX padrão; isto é, {n}, {n,}, e {n,m}são suportados. Os caracteres variam []e [^]são suportados. Por causa dessas regras, e como nenhuma entrada inválida é fornecida, você realmente precisa apenas copiar o conteúdo delas diretamente na saída. Por fim, a ganância não importa, ou seja, não importa se a regex reversa encontra uma correspondência diferente primeiro, ela só precisa encontrar uma correspondência para o mesmo conjunto de strings.

Pontuação

O menor programa em bytes (exceto trapaças, como solicitações de rede) vence. O programa pode usar IO real ou simplesmente definir uma função.

TND
fonte
1
Porque não há nada a ?que anexar. Tente digitar /a(?bc)/no console do navegador.
TND
3
Parece bom agora. Você pode querer adicionar algo como (^a|b)(c$|d)um caso de teste.
Martin Ender
Podemos assumir que a entrada conterá apenas caracteres ASCII imprimíveis? Em particular, nenhum caractere de avanço de linha?
Martin Ender
1
Devemos considerar qualificadores aplicados em grupos, ou seja, (a)?(b)+(b)+(a)??
Kennytm
1
Sua lista de operações de regex está ausente (), usada no seu exemplo.
N

Respostas:

7

Retina , 136 114 110 bytes

Yo dawg, ouvi você gostar de regex ...

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

Onde <empty>representa uma linha de fuga vazia. Execute o código de um único arquivo com o -ssinalizador.

... quando você quiser reverter regex, você deve usar regex. Quando você deseja usar regex, você deve usar uma linguagem de programação baseada em regex.

Este código assume que a entrada não contém nem ;nem !nem espaços. Embora eu concorde que essa é uma suposição bastante forte e potencialmente inválida, você pode substituir os três no código por quaisquer três caracteres não imprimíveis (como bytes nulos, caractere de sino, <DEL>o nome dele) e isso não afetará o tamanho ou a funcionalidade do código em absoluto.

Vou adicionar uma explicação quando terminar o golfe.

Martin Ender
fonte
3
"Eu rebanho * você mente *"
lirtosiast
Eu acho que o código também pressupõe que o regex não contém nenhum caractere de nova linha bruto.
N
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̷̨̰́̀ĥ̷̳ Oh, isso é verdade, eu estava sob a suposição de que não haverá caracteres não imprimíveis na entrada. Vou consertar isso assim que recebermos esclarecimentos do OP. (Se algum caractere puder aparecer, ainda existem certas combinações que não aparecerão no que esse desafio considera uma regex válida; por exemplo ]]], de qualquer forma, essa resposta não precisará de muitas modificações.)
Martin Ender
feito golfe depois de mais de um ano? : P
Okx 03/02
2

JavaScript ES6, 574 bytes

Provavelmente posso remover algumas varinstruções.

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, não testado, 559 bytes

Vai testar em 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, ungolfed, 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
fonte
5
lol, você usou regex regex inversa: D
Kritixi Lithos
3
@ ΚριτικσιΛίθος Sim, eu fiz: D eu usá-lo para analisar HTML se eu pudesse ...
Conor O'Brien
4
"se você pudesse"
Optimizer
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ i analisado html códigos com regex, mas tem um problema sério com caracteres Unicode
Abr001am
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Esta é uma alternativa: `code.replace (/.*/," trollolol ");
Kritixi Lithos 4/11
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 (as funções, mas sem 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]

O código é implementado como um analisador de cima para baixo recursivo, portanto, pode causar estouro de pilha em entradas profundamente aninhadas.

O código pode causar loop infinito em casos inválidos, já que eu não os testo, aproveitando a cláusula "comportamento indefinido".

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

Python 3, 144 bytes

(Este não suporta qualificadores em um grupo como (a)+(b)*(cde)?.)

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

Casos de teste:

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
fonte