Twoim zadaniem jest skompilowanie wyrażeń regularnych ... poprzez określenie podstawienia każdej postaci w wyrażeniu regularnym.

Regeksy

Wyrażenia regularne obsługują je

REGEX       = (LITERAL REGEX / GROUP REGEX / STAR REGEX / ALTERNATIVE)
LITERAL     = 1 / 0
GROUP       = '(' REGEX ')'
STAR        = (LITERAL / GROUP) '*'
ALTERNATIVE = '('REGEX ('|' REGEX)*')'

Dlaczego tylko 1 lub 0? To dla uproszczenia. Wyrażenie regularne ma zatem tylko następujące znaki:

*()|10

Jest interpretowany w następujący sposób:

1. * jest gwiazdą Kleene (powtórz lewą grupę lub dosłownie 0 lub więcej razy).
2. | jest naprzemiennie (dopasuj, jeśli wyrażenie regularne w lewo lub wyrażenie regularne w prawo pasuje).
3. () grupuje.
4. 1 dopasowuje znak 1.
5. 0 dopasowuje znak 0.

Jak skompilować?

Podajesz sześć fragmentów kodu: jeden, aby zastąpić każdy znak wyrażenia regularnego. Na przykład, jeśli Twoja odpowiedź brzmi:

*: FSAGFSDVADFS
|: GSDGSAG
(: GSDG
): GDSIH
1: RGIHAIGH
0:GIHEBN

Następnie zamieniasz każde wyrażenie regularne na odpowiedni fragment kodu, więc:

(0|11)*

zamienia się w:

GSDGGIHEBNGSDGSAGRGIHAIGHRGIHAIGHGDSIHFSAGFSDVADFS

Co powinien zrobić wynikowy program?

Twój program będzie:

1. Weź wkład.
2. Wypisuje prawdziwą wartość, jeśli wyrażenie regularne pasuje do całego wejścia.
3. W przeciwnym razie wypisz wartość fałsz.

Wejście na zewnątrz 01jest uważane za niezdefiniowane zachowanie. Dane wejściowe mogą być puste.

Dodatkowe zasady

1. W przypadku danego znaku wyrażenia regularnego wynikowy fragment kodu musi zawsze być taki sam.
2. Później nie jest dodawany żaden prefiks ani sufiks.
3. Wyrażenie regularne jest na pewno niepuste.

Punktacja

Najmniej połączony fragment jest zwycięzcą. Tak więc wynik dla przykładowego przypadku oblicza się w następujący sposób:

FSAGFSDVADFS+ GSDGSAG+ GSDG+ GDSIH+ RGIHAIGH+GIHEBN

12 + 7 + 4 + 5 + 8 + 6 = 42

Ślimaki , 48 bajtów

0 -> )0(\0!(l.)(~

1 -> )0(\1!(l.)(~

( -> )0({{(

) -> )0}}(~

| -> )0}|{(

* -> )0),(~

Gdybyśmy musieli szukać częściowych dopasowań zamiast dopasowywać tylko pełne dane wejściowe, byłoby to bardzo łatwe. 0stanie się \0, 1stanie się \1, *stanie się ,, a inni odwzorują się na sobie. Zamiast tego istnieje wiele shenaniganów, aby zapobiec rozpoczynaniu się meczów w innym miejscu niż początek lub kończeniu w innym niż koniec. !(l.)jest twierdzeniem, które zawiedzie, jeśli początek dopasowania nie będzie na początku danych wejściowych. ~dopasowuje komórkę poza wejściem, więc jest dodawana do wszystkich znaków, które mogą znajdować się na końcu wyrażenia regularnego. Jeśli występuje inny znak wyrażenia regularnego, jest on anulowany przez kwantyfikator numeryczny0co wymaga dopasowania 0 razy, w zasadzie komentowania. Aby zezwolić *( ,) na poprawne działanie, pomimo tego, że przeszkadza w tym fikcyjny test „out-out-out”, reguły dopasowania nawiasów językowych są mocno używane. Z dokumentacji:

Pasujące pary nawiasów ()lub nawiasów klamrowych {}będą zachowywać się zgodnie z oczekiwaniami (jak nawiasy okrągłe w wyrażeniu regularnym), ale można również pominąć połowę pary i wnioskować o niej, zgodnie z następującymi regułami. )lub }grupuje wszystko w lewo, aż do najbliższej niezamkniętej instrukcji otwierania grupy tego samego typu ( (lub {odpowiednio) lub do początku wzorca, jeśli nie istnieje. Zamyka wszystkie niezamknięte instrukcje otwierania przeciwnego typu w środku tego zakresu. W przeciwnym razie niedopasowane (lub {zostanie zamknięte do końca wzoru.

Czysty jak błoto, prawda?

CJam, 151 bajtów

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

Wiersze odpowiadają znakom 01(|)*(w tej kolejności). Wypróbuj online!

Nie używa to wbudowanego wyrażenia regularnego ani innych typów dopasowywania wzorców. W rzeczywistości CJam nie ma żadnej z tych funkcji. Zamiast tego zaczyna się od wyrażenia regularnego, które reprezentuje, i buduje wszystkie możliwe ciągi, które mógłby dopasować, aby w końcu sprawdzić, czy dane wejściowe użytkownika są jednym z nich.

Przebiegi testowe

W poniższym przykładzie użyto programu, który odczytuje wyrażenie regularne ze STDIN, zastępuje każdy z jego znaków odpowiednim fragmentem kodu i ostatecznie ocenia wygenerowany kod, aby sprawdzić, czy pasuje on do danych wejściowych określonych w argumencie wiersza poleceń.

$ cat regex.cjam
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+ea`,m*\"T

"N%ers~
$ cjam regex.cjam '' <<< '(|)'
1
$ cjam regex.cjam '0' <<< '(|)'
0
$ cjam regex.cjam '' <<< '0(|)'
0
$ cjam regex.cjam '0' <<< '0(|)'
1
$ cjam regex.cjam '' <<< '(0|11)*'
1
$ cjam regex.cjam '0' <<< '(0|11)*'
1
$ cjam regex.cjam '11' <<< '(0|11)*'
1
$ cjam regex.cjam '011011000' <<< '(0|11)*'
1
$ cjam regex.cjam '1010' <<< '(0|11)*'
0

Niestety nie jest to szczególnie szybkie. Dusi się dość szybko, jeśli na wejściu jest więcej niż 9 znaków lub więcej niż jedna gwiazda Kleene w wyrażeniu regularnym.

Kosztem 5 dodatkowych bajtów - w sumie 156 bajtów - możemy wygenerować krótsze ciągi, aby dopasować potencjalne dane wejściowe i deduplikować je. Nie zmienia to działania kodu; po prostu sprawia, że ​​jest bardziej wydajny.

$ cat regex-fast.cjam 
l"01(|)*""

{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM0sa`T
{]Na/Saf+{:m*:sSf-~}%}:J{+:MU{]W=~Jea&,}|}:TM1sa`T
M{{+:M];eas!}:T}|U):UM'[T
MN`T
U(:UM'JT
M\"S+eas,)m*:sSf-L|\"T

"N%ers~
$ cjam regex-fast.cjam '0101001010' <<< '(01|10)*'
0
$ cjam regex-fast.cjam '011001101001' <<< '(01|10)*'
1
$ cjam regex-fast.cjam '0' <<< '(0*1)*'
0
$ time cjam regex-fast.cjam '101001' <<< '(0*1)*'
1