Masalah

Saya memiliki banyak ekspresi reguler yang perlu saya gunakan dalam beberapa kode, tapi saya menggunakan bahasa pemrograman yang tidak mendukung regex! Untungnya, saya tahu bahwa string uji akan memiliki panjang maksimum dan hanya akan terdiri dari ASCII yang dapat dicetak.

Tantangan

Anda harus memasukkan regex dan angka n, dan mengeluarkan setiap string yang terdiri dari ASCII yang dapat dicetak (kode ASCII 32 hingga 126 inklusif, hingga ~, tanpa tab atau baris baru) dengan panjang kurang dari atau sama dengan nyang cocok dengan regex tersebut. Anda tidak boleh menggunakan persamaan reguler bawaan atau fungsi pencocokan regex dalam kode Anda sama sekali. Ekspresi reguler akan dibatasi sebagai berikut:

• Karakter literal (dan lolos, yang memaksa karakter menjadi literal, demikian \.juga literal ., \nadalah literal n(setara dengan adil n), dan \wsetara dengan w. Anda tidak perlu mendukung urutan pelarian.)
• . - wildcard (karakter apa saja)
• Kelas karakter, [abc]berarti "a atau b atau c" dan [d-f]berarti apa saja dari d ke f (jadi, d atau e atau f). Satu-satunya karakter yang memiliki arti khusus dalam kelas karakter adalah [dan ](yang akan selalu lolos, jadi jangan khawatir tentang itu), \(karakter pelarian, tentu saja), ^di awal kelas karakter (yang merupakan negasi ), dan -(yang merupakan kisaran).
• |- operator ATAU, bergantian. foo|barberarti salah fooatau bar, dan (ab|cd)ecocok dengan abeatau cde.
• * - cocok dengan token sebelumnya yang diulang nol atau lebih, serakah (mencoba untuk mengulang sebanyak mungkin)
• + - Diulang satu atau lebih kali, serakah
• ? - nol atau satu kali
• Pengelompokan dengan tanda kurung, untuk token kelompok untuk |, *. +, atau?

Input regex akan selalu valid (yaitu, Anda tidak harus menangani input seperti ?abcatau (fooatau input yang tidak valid). Anda dapat menampilkan string dalam urutan apa pun yang Anda inginkan, tetapi setiap string harus muncul hanya sekali (jangan hasilkan duplikat).

Kasus Uji

Input: .*, 1
Output: (string kosong), , !, ", ..., },~

Input: w\w+, 3
Output: ww,www

Input: [abx-z][^ -}][\\], 3
Output: a~\, b~\, x~\, y~\,z~\

Input: ab*a|c[de]*, 3
Output: c, cd, ce, aa, cde, ced, cdd, cee,aba

Input: (foo)+(bar)?!?, 6
Output: foo, foo!, foofoo,foobar

Input: (a+|b*c)d, 4
Output: ad, cd, aad, bcd, aaad,bbcd

Input: p+cg, 4
Output: pcg,ppcg

Input: a{3}, 4
Output:a{3}

Pemenang

Ini adalah kode-golf , jadi kode terpendek dalam byte akan menang!

Haskell 757 705 700 692 679 667

import Data.List
data R=L Char|A R R|T R R|E
h=[' '..'~']
k(']':s)a=(a,s)
k('^':s)_=l$k[]s
k('-':c:s)(a:b)=k([a..c]++b)s
k('\\':c:s)a=k s$c:a
k(c:s)a=k s$c:a
l(a,b)=(h\\a,b)
c#E=L c
c#r=A(L c)r
o(a,b)=(foldr(#)E a,b)
t%0=E
t%n=A(t%(n-1))$T t$t%(n-1)
d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s$m r a;r s=w$e s E;w(u,'|':v)=(\(a,b)->(A u a,b))$r v;w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f$b s;e[]t=(t,[]);g t(u,v)=e v$T t u;f(t,'*':s)=(t%n,s);f(t,'+':s)=(T t$t%n,s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o$k s[];b(s:t)=(L s,t)}

keluaran:

ghci> d ".*" 1
[""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"]
ghci> d "w\\w+" 3
["ww","www"]
ghci> d "[abx-z][^ -}][\\\\]" 3
["x~\\","y~\\","z~\\","b~\\","a~\\"]
ghci> d "ab*a|c[de]*" 3
["aa","aba","c","ce","cd","cee","cde","ced","cdd"]
ghci> d "(foo)+(bar)?!?" 6
["foo!","foobar","foo","foofoo"]
ghci> d "(a+|b*c)d" 4
["ad","aad","aaad","cd","bcd","bbcd"]
ghci> d "p+cg" 4
["pcg","ppcg"]
ghci> d "a{3}" 4
["a{3}"]

Penjelasan: ini adalah implementasi regex buku teks. R adalah tipe regex, dengan konstruktor A (alternatif), L (literal), T (lalu) dan E (kosong / epsilon). 'Bintang' yang biasa tidak muncul karena saya sebariskan sebagai alternatif selama parse (lihat '%'). 'm' menjalankan simulasi. Parser (mulai dari 'rs = ....') hanyalah turunan rekursif; rentang k 'p'. Fungsi '#' memperluas rentang menjadi bergantian.

Python v2.7 1069 1036 950 925 897 884 871 833 822

Jawaban ini sepertinya agak panjang untuk kode golf, tetapi ada banyak operator yang perlu ditangani dan saya tahu apa tujuan setiap byte dalam jawaban ini. Karena tidak ada jawaban yang ada, saya mengirimkan ini sebagai target untuk dikalahkan oleh pengguna lain. Lihat apakah Anda dapat membuat jawaban yang lebih pendek :).

Dua fungsi utama adalah fmem-parsing regex mulai dari ikarakter th, dan dyang menghasilkan string yang cocok, menggunakan rsub-regex yang dapat kita rekur ulang menjadi, 'a' array yang mewakili bagian dari sub-regex saat ini yang belum diproses, dan akhiran string syang mewakili bagian dari string yang dihasilkan sejauh ini.

Periksa juga keluaran sampel dan alat uji .

import sys;V=sys.argv;n=int(V[2]);r=V[1];S=len;R=range;C=R(32,127)
Z=[];z=-1;D='d(r,p,';F='for j in '
def f(i,a):
 if i>=S(r):return a,i
 c=r[i];x=0;I="|)]".find(c)
 if c in"([|":x,i=f(i+1,Z)
 if I+1:return([c,a,x],[a],[c,a])[I],i
 if'\\'==c:i+=1;x=c+r[i]
 return f(i+1,a+[x or c])
def d(r,a,s):
 if S(s)>n:return
 while a==Z:
        if r==Z:print s;return
        a=r[z];r=r[:z]
 e=a[z];p=a[0:z]
 if'|'==a[0]:d(r,a[1],s);d(r,a[2],s)
 elif']'==a[0]:
        g=a[1];N=g[0]=='^';g=(g,g[1:])[N];B=[0]*127;O=[ord(c[z])for c in g]
        for i in R(0,S(g)):
         if'-'==g[i]:exec F+'R(O[i-1],O[i+1]):B[j]=1'
         else:B[O[i]]=1
        for c in C:N^B[c]<1or d(r,Z,chr(c)+s)
 elif' '>e:d(r+[p],e,s)
 else:c=p[:z];exec{'.':F+'C:'+D+'chr(j)+s)','?':D+'s);d(r,p[:z],s)','*':F+'R(0,n+1):d(r,c,s);c+=[p[z]]','+':"d(r,p+['*',p[z]],s)"}.get(e,D+'e[z]+s)')
d(Z,f(0,Z)[0],"")

Perhatikan bahwa tab dalam solusi asli telah expanddiedit. Untuk menghitung jumlah karakter dalam penggunaan aslinya unexpand < regex.py | wc.