Kehre einen regulären Ausdruck um

27

Die Herausforderung

Bei einem gültigen regulären Ausdruck wird ein regulärer Ausdruck ausgegeben, der mit demselben Satz von Zeichenfolgen übereinstimmt, jedoch umgekehrt ist.

Die Aufgabe

Diese Herausforderung nutzt die grundlegendsten regex Operationen: ^, $, ?, +, *, [], {}, |. Es gibt keine Capture-Gruppen oder so etwas Kompliziertes. Sonderzeichen können maskiert werden.

Sample Input / Output

Hinweis: Ungültige Eingaben werden niemals gegeben, und es gibt im Allgemeinen mehrere mögliche Antworten für eine bestimmte Eingabe!

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

Arbeitsdemo , das korrekte Ein- / Ausgänge demonstriert. Dies hat einige zusätzliche Logik zum Validieren von Eingaben, die in einer realen Antwort nicht erforderlich sind. Betrachten Sie ungültige Eingaben als undefiniertes Verhalten.

Besonderheiten

Der Einfachheit halber haben alle Sonderzeichen entweder ihre spezielle Bedeutung oder werden maskiert. Das heißt, es [[]ist kein Zeichenbereich für [. Längenbereiche stammen aus Standard-POSIX-EREs; das heißt {n}, {n,}und {n,m}werden unterstützt. Die Zeichenbereiche []und [^]werden unterstützt. Aufgrund dieser Regeln und da keine ungültige Eingabe angegeben wird, müssen Sie den Inhalt nur direkt in die Ausgabe kopieren. Schließlich spielt Gier keine Rolle, dh es spielt keine Rolle, ob der umgekehrte reguläre Ausdruck zuerst eine andere Übereinstimmung findet , sondern nur eine Übereinstimmung für denselben Satz von Zeichenfolgen.

Wertung

Das kleinste Programm in Bytes (außer bei Betrug wie Netzwerkanforderungen) gewinnt. Das Programm kann entweder echte E / A verwenden oder einfach eine Funktion definieren.

TND
quelle
1
Weil es nichts gibt, an dem ?man sich festmachen kann. Versuchen Sie, /a(?bc)/in die Konsole des Browsers zu tippen.
TND
3
Sieht jetzt gut aus. Vielleicht möchten Sie jedoch etwas wie (^a|b)(c$|d)einen Testfall hinzufügen .
Martin Ender
Können wir davon ausgehen, dass die Eingabe nur druckbare ASCII-Zeichen enthält? Insbesondere keine Zeilenvorschubzeichen?
Martin Ender
1
Sollten wir Qualifikationsmerkmale berücksichtigen, die auf Gruppen angewendet werden, z. B. (a)?(b)+(b)+(a)??
kennytm
1
Ihre Liste der regulären Ausdrücke fehlt (), die in Ihrem Beispiel verwendet wird.
n̴̖̋h̴̖̋a̷̭̿h̷̭̿d̸̡̅ẗ̵̨́

Antworten:

7

Retina , 136 114 110 Bytes

Yo dawg, ich habe gehört, du magst Regex ...

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

Wobei <empty>eine leere abschließende Zeile darstellt. Führen Sie den Code aus einer einzelnen Datei mit dem -sFlag aus.

... wenn Sie Regex umkehren möchten, sollten Sie Regex verwenden. Wenn Sie Regex verwenden möchten, sollten Sie eine auf Regex basierende Programmiersprache verwenden.

Dieser Code geht davon aus, dass der Eingang enthält weder ;noch !noch Räume. Ich bin damit einverstanden, dass dies eine ziemlich starke und möglicherweise ungültige Annahme ist, aber Sie können diese drei Zeichen im Code durch drei nicht druckbare Zeichen (wie Null-Bytes, Bell-Zeichen, <DEL>Sie nennen es) ersetzen , ohne dass sich dies auf die Codegröße oder -funktionalität auswirkt überhaupt.

Ich werde eine Erklärung hinzufügen, wenn ich mit dem Golfen fertig bin.

Martin Ender
quelle
3
"Ich
hüte
Ich denke, der Code geht auch davon aus, dass der reguläre Ausdruck kein Zeilenumbruchzeichen enthält.
n̴̖̋h̴̖̋a̷̭̿h̷̭̿d̸̡̅ẗ̵̨́
@ n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳ Oh, das stimmt, ich ging davon aus, dass die Eingabe keine nicht druckbaren Zeichen enthält. Ich werde das beheben, sobald wir Klarheit vom OP bekommen. (Wenn irgendwelche Zeichen auftreten können, gibt es immer noch bestimmte Kombinationen, die in dieser Herausforderung als gültiger regulärer Ausdruck nicht angezeigt werden, z. B. ]]]muss für diese Antwort in keiner Weise viel geändert werden.)
Martin Ender,
Nach über einem Jahr Golf gespielt? : P
Okx
2

JavaScript ES6, 574 Bytes

Ich kann wohl ein paar varAussagen entfernen .

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, ungetestet, 559 Bytes

Wird zu Hause testen.

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
quelle
5
lol, Sie haben Regex verwendet, um Regex umzukehren: D
Kritixi Lithos
3
@ ΚριτικσιΛίθος Ja, ich habe: D Ich würde es verwenden, um HTML zu analysieren, wenn ich könnte ...
Conor O'Brien
4
"Wenn Sie könnten"
Optimierer
1
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ich habe HTML-Codes mit Regex analysiert, aber ein ernstes Problem mit Unicode-Zeichen bekommen
Abr001am
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Dies ist eine Alternative: `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]

Originalcode (die Funktionen, aber ohne 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]

Der Code wird als rekursiver Top-Down-Parser implementiert, sodass es bei tief verschachtelten Eingaben zu einem Stapelüberlauf kommen kann.

In ungültigen Fällen kann der Code eine Endlosschleife verursachen, da ich sie nicht teste und dabei die Klausel "undefiniertes Verhalten" ausnütze.

n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳
quelle
0

Python 3, 144 Bytes

(Dieser unterstützt keine Qualifikanten für eine Gruppe wie (a)+(b)*(cde)?.)

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

Testfälle:

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

Ergebnis:

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
quelle