Das Problem

Ich habe einige reguläre Ausdrücke, die ich in einem Code verwenden muss, aber ich verwende eine Programmiersprache, die Regex nicht unterstützt! Zum Glück weiß ich, dass der Teststring eine maximale Länge hat und nur aus druckbarem ASCII besteht.

Die Herausforderung

Sie müssen einen regulären Ausdruck und eine Zahl eingeben und njede Zeichenfolge ausgeben, die aus druckbarem ASCII (einschließlich ASCII-Codes 32 bis 126, bis ~, ohne Tabulatoren oder Zeilenumbrüche) besteht und deren Länge der des regulären Ausdrucks entspricht oder ndieser entspricht. Sie dürfen in Ihrem Code überhaupt keine integrierten regulären Ausdrücke oder Regex-Abgleichsfunktionen verwenden. Reguläre Ausdrücke sind auf Folgendes beschränkt:

• Literalzeichen (und Escapes, die ein Zeichen zum Literal machen, also \.ein Literal ., \nist ein Literal n(entspricht nur n) und \wentspricht w. Escape-Sequenzen müssen nicht unterstützt werden.)
• . - Platzhalter (beliebiges Zeichen)
• Zeichenklassen [abc]bedeuten "a oder b oder c" und [d-f]bedeuten alles von d bis f (so, d oder e oder f). Die einzigen Zeichen, die in einer Zeichenklasse eine besondere Bedeutung haben, sind [und ](die immer ausgeblendet werden, machen Sie sich also keine Sorgen) \(natürlich das Escape-Zeichen) ^am Anfang der Zeichenklasse (was eine Negation ist) ), und -(das ist ein Bereich).
• |- der OP-Operator, Wechsel. foo|barbedeutet entweder foooder bar, und (ab|cd)eentspricht entweder abeoder cde.
• * - den vorherigen Token null oder mehrmals abgleichen, gierig (es wird versucht, so oft wie möglich zu wiederholen)
• + - ein oder mehrmals wiederholt, gierig
• ? - Null oder einmal
• Gruppierung mit Klammern gruppieren Token für |, *. +, oder?

Der reguläre Ausdruck für die Eingabe ist immer gültig (dh Sie müssen keine Eingaben wie ?abcoder (foooder ungültige Eingaben verarbeiten). Sie können die Zeichenfolgen in beliebiger Reihenfolge ausgeben, aber jede Zeichenfolge darf nur einmal vorkommen (keine Duplikate ausgeben).

Die Testfälle

Input: .*, 1
Output: (leere Zeichenkette), , !, ", ..., },~

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}

Der Gewinner

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes!

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

Ausgabe:

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}"]

Erläuterung: Dies ist eine Regex-Implementierung für Lehrbücher. R ist der Regex-Typ mit den Konstruktoren A (alternierend), L (wörtlich), T (dann) und E (leer / epsilon). Der übliche 'Stern' wird nicht angezeigt, da ich ihn während des Parsens als Alternative eingebunden habe (siehe '%'). 'm' führt die Simulation aus. Der Parser (Start bei 'rs = ....') ist nur ein rekursiver Abstieg. 'k' analysiert Bereiche. Die Funktion '#' erweitert Bereiche zu Alternationen.

Python 2.7 1069 1036 950 925 897 884 871 833 822

Diese Antwort scheint für einen Code Golf ziemlich lang zu sein, aber es gibt eine Menge Operatoren, die gehandhabt werden müssen, und ich weiß, welchen Zweck jedes Byte in dieser Antwort hat. Da es keine Antwort gibt, sende ich diese als Ziel für andere Benutzer, um sie zu schlagen. Sehen Sie, ob Sie eine kürzere Antwort machen können :).

Die zwei Hauptfunktionen sind, fdie den regulären Ausdruck ab dem achten iZeichen analysieren und ddie passenden Zeichenfolgen unter Verwendung rder regulären Ausdrücke erzeugen, in die wir rekursiv eingreifen können. und ein String-Suffix, sdas den bisher erzeugten Teil des Strings darstellt.

Überprüfen Sie auch die Beispielausgabe und einen Test-Kabelbaum .

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],"")

Beachten Sie, dass Registerkarten in der ursprünglichen Lösung bearbeitet wurden expand. Um die Anzahl der Zeichen in der ursprünglichen Verwendung zu zählen unexpand < regex.py | wc.