Odwróć wyrażenie regularne

27

Wyzwanie

Biorąc pod uwagę poprawną regex, wypisz regex, który pasuje do tego samego zestawu ciągów, ale jest odwrócony.

Zadanie

To wyzwanie wykorzystuje najbardziej podstawowe operacje regex: ^, $, ?, +, *, [], {}, |. Nie ma czegoś takiego jak grupy przechwytywania lub jakiekolwiek inne skomplikowane rzeczy. Znaki specjalne można uciec.

Przykładowe wejście / wyjście

Uwaga: Niepoprawne dane wejściowe nigdy nie zostaną podane i dla wielu danych istnieje wiele możliwych odpowiedzi!

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>

Próbny

Działające demo, które pokazuje prawidłowe wejścia / wyjścia. Ma to pewną dodatkową logikę do sprawdzania poprawności danych wejściowych, które nie są konieczne w prawdziwej odpowiedzi. Uważaj niepoprawne dane wejściowe za niezdefiniowane zachowanie.

Specyfika

Dla uproszczenia wszystkie znaki specjalne mają albo specjalne znaczenie, albo uciekają; to [[]znaczy nie jest zasięgiem postaci [. Zakresy długości pochodzą ze standardowych POSIX ERE; to znaczy {n}, {n,}i {n,m}są obsługiwane. Zakresy znaków []i [^]są obsługiwane. Z powodu tych reguł i ponieważ nie podano niepoprawnych danych wejściowych, naprawdę potrzebujesz tylko ich zawartości bezpośrednio na dane wyjściowe. Wreszcie, zachłanność nie ma znaczenia, tzn. Nie ma znaczenia, czy odwrotna regex znajdzie najpierw inne dopasowanie, musi tylko znaleźć dopasowanie dla tego samego zestawu ciągów.

Punktacja

Najmniejszy program w bajtach (z wyjątkiem oszustw, takich jak żądania sieciowe) wygrywa. Program może użyć rzeczywistego We / Wy lub po prostu zdefiniować funkcję.

TND
źródło
1
Ponieważ nie ma się do czego ?przyczepić. Spróbuj wpisać /a(?bc)/w konsoli przeglądarki.
TND
3
Teraz wygląda dobrze. Możesz jednak dodać coś takiego (^a|b)(c$|d)jak przypadek testowy.
Martin Ender,
Czy możemy założyć, że dane wejściowe będą zawierać tylko drukowalne znaki ASCII? W szczególności nie ma znaków linii?
Martin Ender
1
Czy powinniśmy rozważyć kwalifikatory stosowane w grupach, tj. (a)?(b)+(b)+(a)??
kennytm,
1
Brakuje twojej listy wyrażeń regularnych (), która jest używana w twoim przykładzie.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳

Odpowiedzi:

7

Siatkówka , 136 114 110 bajtów

Yo dawg, słyszałem, że lubisz wyrażenia regularne ...

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

Gdzie <empty>reprezentuje pustą linię końcową. Uruchom kod z jednego pliku z -sflagą.

... kiedy chcesz odwrócić regex, powinieneś użyć regex. Jeśli chcesz użyć wyrażenia regularnego, powinieneś użyć języka programowania opartego na wyrażeniach regularnych.

Kod ten zakłada, że wejście nie zawiera ;ani !nie obowiązuje. Chociaż zgadzam się, że jest to dość mocne i potencjalnie nieprawidłowe założenie, możesz zastąpić te trzy w kodzie dowolnymi trzema niedrukowalnymi znakami (np. Bajtami zerowymi, znakiem dzwonka, <DEL>jak go nazwiesz) i nie wpłynie to na rozmiar ani funkcjonalność kodu w ogóle.

Dodam wyjaśnienie, kiedy skończę grać w golfa.

Martin Ender
źródło
3
„I herd * you liek *”
lirtosiast
Myślę, że kod zakłada również, że wyrażenie regularne nie zawiera surowego nowego znaku wiersza.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ Och, to prawda, zakładałem, że na wejściu nie będzie żadnych znaków, które nie mogą zostać wydrukowane. Naprawię to, gdy otrzymamy wyjaśnienie od PO. (Jeśli pojawią się jakieś postacie, nadal istnieją pewne kombinacje, które nie pojawią się w tym, co wyzwanie uznaje za poprawne wyrażenie regularne, np. ]]]Tak czy inaczej, ta odpowiedź nie będzie wymagać wielu modyfikacji.)
Martin Ender
grałeś w golfa po ponad roku? : P
Okx
2

JavaScript ES6, 574 bajty

Prawdopodobnie mogę usunąć kilka varinstrukcji.

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, nieprzetestowane, 559 bajtów

Testuje w domu.

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, bez golfa, 961 bajtów

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
źródło
5
lol, użyłeś wyrażenia regularnego do odwrócenia wyrażenia regularnego: D
Kritixi Lithos
3
@ ΚριτικσιΛίθος Tak, zrobiłem: D Użyłbym go do parsowania HTML, gdybym mógł ...
Conor O'Brien
4
„jeśli możesz”
Optymalizator
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ parsowałem kody html z regex, ale mam poważny problem z
znakami
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Jest to alternatywa: `code.replace (/.*/,„ trollolol ”);
Kritixi Lithos
2

JavaScript ES6, 343 bajty

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]

Oryginalny kod (funkcje, ale bez 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]

Kod jest implementowany jako rekursywny analizator składni z góry na dół, więc może powodować przepełnienie stosu przy głęboko zagnieżdżonych danych wejściowych.

Kod może powodować nieskończoną pętlę w niepoprawnych przypadkach, ponieważ nie testuję ich, wykorzystując klauzulę „niezdefiniowane zachowanie”.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
źródło
0

Python 3, 144 bajty

(Ten nie obsługuje kwalifikatorów w grupie takiej jak (a)+(b)*(cde)?.)

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

Przypadki testowe:

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

Wynik:

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
źródło