Inverser une expression régulière

27

Le défi

Étant donné une expression régulière valide, affichez une expression régulière qui correspond au même ensemble de chaînes, mais inversée.

La tâche

Ce défi utilise le plus les opérations de base regex: ^, $, ?, +, *, [], {}, |. Il n'y a rien de tel que des groupes de capture ou tout ce genre de choses compliquées. Les caractères spéciaux peuvent être échappés.

Exemple d'entrée / sortie

Remarque: Une entrée non valide ne sera jamais donnée, et il y a généralement plusieurs réponses possibles pour une entrée donnée!

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>

Démo

Démo de travail qui montre les entrées / sorties correctes. Cela a une logique supplémentaire pour valider les entrées qui n'est pas nécessaire dans une vraie réponse. Considérez les entrées non valides comme un comportement non défini.

Détails

Par souci de simplicité, tous les caractères spéciaux ont leur signification particulière ou sont échappés; c'est-à-dire, [[]n'est pas une plage de caractères pour [. Les plages de longueurs proviennent des ERE POSIX standard; c'est-à- {n}dire {n,}, et {n,m}sont pris en charge. Les caractères varient []et [^]sont pris en charge. En raison de ces règles, et comme aucune entrée non valide n'est fournie, vous n'avez vraiment besoin que de copier le contenu de celles-ci directement dans la sortie. Enfin, la gourmandise n'a pas d'importance, c'est-à-dire que peu importe si l'expression régulière inversée trouve d'abord une correspondance différente , il lui suffit de trouver une correspondance pour le même ensemble de chaînes.

Notation

Le plus petit programme en octets (sauf la tricherie comme les requêtes réseau) gagne. Le programme peut soit utiliser de vraies E / S, soit simplement définir une fonction.

TND
la source
1
Parce qu'il n'y a rien à quoi ?s'attacher. Essayez de taper /a(?bc)/dans la console du navigateur.
TND
3
Ça a l'air bien maintenant. Vous voudrez peut-être ajouter quelque chose comme (^a|b)(c$|d)un cas de test.
Martin Ender
Pouvons-nous supposer que l'entrée ne contiendra que des caractères ASCII imprimables? En particulier, pas de caractères de saut de ligne?
Martin Ender
1
Faut-il considérer les qualificatifs appliqués sur les groupes ie (a)?(b)+(b)+(a)??
kennytm
1
Votre liste d'opérations d'expression régulière est manquante (), ce qui est utilisé dans votre exemple.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Réponses:

7

Rétine , 136 114 110 110 octets

Yo dawg, je vous ai entendu comme regex ...

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

<empty>représente une ligne de fin vide. Exécutez le code à partir d'un seul fichier avec l' -sindicateur.

... lorsque vous voulez inverser l'expression régulière, vous devez utiliser l'expression régulière. Lorsque vous voulez utiliser regex, vous devez utiliser un langage de programmation basé sur regex.

Ce code suppose que l'entrée ne contient ni ;ni !ni ni espaces. Bien que je convienne que c'est une hypothèse assez forte et potentiellement invalide, vous pouvez remplacer ces trois dans le code par trois caractères non imprimables (comme les octets nuls, le caractère de cloche, <DEL>vous l' appelez ), et cela n'affecterait pas la taille ou la fonctionnalité du code du tout.

J'ajouterai une explication quand j'aurai fini de jouer au golf.

Martin Ender
la source
3
"Je troupeau * tu mens *"
lirtosiast
Je pense que le code suppose également que l'expression régulière ne contient aucun nouveau caractère de ligne brut.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oh, c'est vrai, j'étais dans l'hypothèse qu'il n'y aura pas de caractères non imprimables dans l'entrée. Je corrigerai cela une fois que nous aurons obtenu des éclaircissements du PO. (Si des personnages peuvent apparaître, il existe encore certaines combinaisons qui n'apparaîtront pas dans ce que ce défi considère comme une expression rationnelle valide, par exemple ]]], de toute façon, cette réponse n'aura pas besoin de beaucoup de modifications.)
Martin Ender
fait du golf après plus d'un an? : P
Okx
2

JavaScript ES6, 574 octets

Je peux probablement supprimer quelques vardéclarations.

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, non testé, 559 octets

Testera à la maison.

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, non golfé, 961 octets

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
la source
5
lol, vous avez utilisé l'expression régulière pour inverser l'expression
régulière
3
@ ΚριτικσιΛίθος Oui, je l'ai fait: D Je l'utiliserais pour analyser HTML si je pouvais ...
Conor O'Brien
4
"si vous le pouviez"
Optimizer
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ j'ai analysé les codes html avec regex mais j'ai eu un sérieux problème avec les caractères unicode
Abr001am
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ceci est une alternative: `code.replace (/.*/," trollolol ");
Kritixi Lithos
2

JavaScript ES6, 343 octets

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]

Code d'origine (les fonctions, mais sans 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]

Le code est implémenté comme un analyseur récursif descendant, il peut donc provoquer un débordement de pile sur une entrée profondément imbriquée.

Le code peut provoquer une boucle infinie dans des cas invalides, car je ne les teste pas, profitant de la clause "comportement indéfini".

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

Python 3, 144 octets

(Celui-ci ne prend pas en charge les qualificatifs sur un groupe comme (a)+(b)*(cde)?.)

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

Cas de test:

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))

Résultat:

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
la source