Membalikkan regex

27

Tantangan

Diberikan regex yang valid, hasilkan regex yang cocok dengan rangkaian string yang sama, tetapi dibalik.

Tugas

Tantangan ini menggunakan sebagian besar operasi regex dasar: ^, $, ?, +, *, [], {}, |. Tidak ada yang namanya kelompok tangkap atau hal rumit lainnya. Karakter khusus dapat lolos.

Contoh Input / Output

Catatan: Input yang tidak valid tidak akan pernah diberikan, dan umumnya ada beberapa kemungkinan jawaban untuk input yang diberikan!

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

Demo kerja yang menunjukkan input / output yang benar. Ini memiliki beberapa logika tambahan untuk memvalidasi input yang tidak perlu dalam jawaban nyata. Pertimbangkan input yang tidak valid sebagai perilaku yang tidak terdefinisi.

Spesifik

Untuk kesederhanaan, semua karakter khusus memiliki arti khusus atau melarikan diri; yaitu, [[]bukan rentang karakter untuk [. Rentang panjang berasal dari ERE POSIX standar; yaitu, {n}, {n,}, dan {n,m}didukung. Rentang karakter []dan [^]didukung. Karena aturan ini, dan karena tidak ada input yang tidak valid diberikan, Anda benar-benar hanya perlu menyalin konten ini langsung ke output. Terakhir, keserakahan tidak masalah, artinya tidak masalah jika regex yang terbalik menemukan kecocokan yang berbeda terlebih dahulu, hanya perlu menemukan kecocokan untuk rangkaian string yang sama.

Mencetak gol

Program terkecil dalam byte (kecuali kecurangan seperti permintaan jaringan) menang. Program dapat menggunakan IO nyata atau hanya mendefinisikan suatu fungsi.

TND
sumber
1
Karena tidak ada yang ?bisa dilampirkan. Coba ketikkan /a(?bc)/konsol konsol browser.
TND
3
Terlihat bagus sekarang. Anda mungkin ingin menambahkan sesuatu seperti (^a|b)(c$|d)sebagai test case.
Martin Ender 4-15
Bisakah kita berasumsi bahwa input hanya akan berisi karakter ASCII yang dapat dicetak? Khususnya, tidak ada karakter linefeed?
Martin Ender 4-15
1
Haruskah kita mempertimbangkan kualifikasi yang diterapkan pada grup yaitu (a)?(b)+(b)+(a)??
kennytm
1
Daftar operasi regex Anda tidak ada (), yang digunakan dalam contoh Anda.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Jawaban:

7

Retina , 136 114 110 byte

Yo dawg, saya mendengar Anda suka regex ...

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

Dimana <empty>mewakili garis trailing kosong. Jalankan kode dari satu file dengan -sbendera.

... ketika Anda ingin membalikkan regex Anda harus menggunakan regex. Saat Anda ingin menggunakan regex, Anda harus menggunakan bahasa pemrograman berbasis regex.

Kode ini mengasumsikan bahwa input tidak berisi ;atau !atau ruang. Meskipun saya setuju bahwa itu adalah asumsi yang cukup kuat dan berpotensi tidak valid, Anda dapat mengganti ketiganya dalam kode dengan tiga karakter yang tidak diinginkan (seperti null byte, karakter lonceng, beri <DEL>nama), dan itu tidak akan memengaruhi ukuran kode atau fungsionalitas sama sekali.

Saya akan menambahkan penjelasan ketika saya selesai bermain golf.

Martin Ender
sumber
3
"Aku kawan * kamu suka *"
lirtosiast
Saya pikir kode juga mengasumsikan bahwa regex tidak mengandung karakter baris baru yang mentah.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Oh, itu benar, saya berada di bawah asumsi bahwa tidak akan ada karakter yang tidak patut dalam input. Saya akan memperbaikinya setelah kami mendapatkan klarifikasi dari OP. (Jika ada karakter yang dapat muncul, masih ada kombinasi tertentu yang tidak akan muncul dalam apa yang dianggap tantangan ini sebagai regex yang valid, misalnya ]]], jadi bagaimanapun, jawaban ini tidak perlu banyak modifikasi.)
Martin Ender
melakukan golf setelah lebih dari setahun? : P
Okx
2

JavaScript ES6, 574 byte

Saya mungkin dapat menghapus beberapa varpernyataan.

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, belum teruji, 559 byte

Akan tes di rumah.

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 byte

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
sumber
5
lol, Anda menggunakan regex untuk membalikkan regex: D
Kritixi Lithos
3
@ ΚριτικσιΛίθος Ya, saya lakukan: D Saya akan menggunakannya untuk mem-parsing HTML jika saya bisa ...
Conor O'Brien
4
"jika Anda bisa"
Pengoptimal
1
@CᴏɴᴏʀO'Bʀɪᴇɴ saya mem-parsing kode html dengan regex tetapi mendapat masalah serius dengan karakter unicode
Abr001am
2
@ CᴏɴᴏʀO'Bʀɪᴇɴ Ini adalah alternatif: `code.replace (/.*/," trollolol ");
Kritixi Lithos
2

JavaScript ES6, 343 byte

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]

Kode asli (fungsinya, tetapi tanpa 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]

Kode ini diimplementasikan sebagai parser top-down rekursif, sehingga dapat menyebabkan stack overflow pada input yang sangat bersarang.

Kode dapat menyebabkan loop tak terbatas dalam kasus yang tidak valid, karena saya tidak mengujinya, mengambil keuntungan dari klausa "perilaku tidak terdefinisi".

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

Python 3, 144 byte

(Yang ini tidak mendukung kualifikasi pada grup seperti (a)+(b)*(cde)?.)

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

Kasus uji:

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

Hasil:

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
sumber