Napisz program, który pobiera ciąg czterech znaków, ()[]
który spełnia następujące warunki:
- Każdy lewy nawias
(
ma pasujący prawy nawias)
. - Każdy lewy wspornik
[
ma pasujący prawy wspornik]
. - Pasujące pary nawiasów i nawiasów nie będą się nakładać. np.
[(])
jest niepoprawny, ponieważ pasujące nawiasy nie są w pełni zawarte w pasujących nawiasach, i odwrotnie. - Pierwszy i ostatni znak to pasująca para nawiasów lub nawiasów. Tak
([]([]))
i[[]([])]
są ważne, ale[]([])
nie są.
( Gramatyka formatu wejściowego to <input> ::= [<input>*] | (<input>*)
.)
Każda para pasujących nawiasów i nawiasów przyjmuje wartość całkowitą nieujemną:
- Wszystkie pary w pasujących nawiasach są sumowane . Puste dopasowanie
()
ma wartość0
. - Wszystkie pary w pasujących nawiasach są mnożone . Puste dopasowanie
[]
ma wartość1
.
( Suma lub iloczyn jednego numeru to ta sama liczba).
Na przykład ([](())([][])[()][([[][]][][])([][])])
można podzielić i ocenić jako 9
:
([](())([][])[()][([[][]][][])([][])]) <input>
(1 (0 )(1 1 )[0 ][([1 1 ]1 1 )(1 1 )]) <handle empty matches>
(1 0 2 0 [(1 1 1 )2 ]) <next level of matches>
(1 0 2 0 [3 2 ]) <and the next>
(1 0 2 0 6 ) <and the next>
9 <final value to output>
Inny przykład:
[([][][][][])([][][])([][][])(((((([][]))))))] <input>
[(1 1 1 1 1 )(1 1 1 )(1 1 1 )((((((1 1 ))))))]
[5 3 3 (((((2 )))))]
[5 3 3 ((((2 ))))]
[5 3 3 (((2 )))]
[5 3 3 ((2 ))]
[5 3 3 (2 )]
[5 3 3 2 ]
90 <output>
Twój program musi ocenić i wydrukować liczbę całkowitą reprezentowaną przez cały ciąg wejściowy. Możesz założyć, że dane wejściowe są prawidłowe. Najkrótszy kod w bajtach wygrywa.
Zamiast programu możesz napisać funkcję, która pobiera ciąg znaków i wypisuje lub zwraca liczbę całkowitą.
code-golf
arithmetic
balanced-string
recursion
Hobby Calvina
źródło
źródło
Odpowiedzi:
CJam, 23
Z DUŻYMI kredytami dla Dennisa! Wypróbuj online
Wyjaśnienie:
Program konwertuje dane wejściowe na wyrażenie CJam, a następnie je ocenia.
[…]
staje się[…1]:*
(dołącz 1 i pomnóż)(…)
staje się[…0]:+
(dodaj 0 i dodaj)źródło
q"])(""1]:*0]:+["4/ers~
Common Lisp - 98
(
przez(+
[
przez(*
]
przez)
Wymaga
cl-ppcre
to załadowania biblioteki do bieżącego obrazu lisp.Wyjaśnienie
Funkcje
*
i+
są różne i zwracają swoją neutralną wartość, gdy nie podano argumentów. W twoich przykładach oceniana forma seplenienia jest następująca:i
Bez wyrażeń regularnych - 183 bajtów
Dalej, Lisp - 16 bajtów (eksperymentalnie)
Inne języki są tak zwięzłe, że kusi mnie tworzenie własnego języka golfowego opartego na Common Lisp do krótszych manipulacji strunami. Obecnie nie ma specyfikacji, a funkcja eval jest następująca:
Testy:
s
i dwa stosy,p
orazq
.p
.<
: wyskakuje zp
i popycha doq
.r
: zamienia ins
(musi być ciągiem) ze znaków inq
na charactes inp
; wynik jest przechowywany ws
;p
iq
są opróżniane.R
: odczyt z ciągus
, zapisz wynik w zmiennejs
.E
: forma ewaluacyjnas
, zapisz wynik ws
.źródło
Pyth,
353433 bajtówDemonstracja.
1 bajt dzięki @Jakube.
Zaczynamy od przeanalizowania danych wejściowych. Format wejściowy jest zbliżony do Pythona, ale niezupełnie. Potrzebujemy przecinków po każdej nawiasowej lub nawiasowej grupie. Przecinek na końcu grupy w nawiasach jest niepotrzebny, ale nieszkodliwy. Aby to osiągnąć, używamy tego kodu:
To pozostawi dodatkowy
,
na końcu łańcucha, który owinie cały obiekt w krotkę, ale jest to nieszkodliwe, ponieważ krotka zostanie zsumowana, a zatem będzie miała wartość równą jej elementowi.Teraz, gdy ciąg jest analizowany, musimy znaleźć jego wartość. Odbywa się to za pomocą funkcji zdefiniowanej przez użytkownika
y
, która jest wywoływana w analizowanym obiekcie. funkcja jest zdefiniowana w następujący sposób:źródło
Emacs lisp, 94
Format wygląda bardzo zawstydzony, więc pomyślałem, że prosta transformacja może zadziałać:
Format pośredni wygląda mniej więcej tak (na przykład w pytaniu):
Pomaga nam fakt, że dodawanie i mnożenie już robi to, co chcemy, z pustą listą argumentów.
Degolfowany i interaktywny, dla Ciebie grającego w przyjemność:
źródło
interactive
(zamiast ciągu buforowego, użyj odczytu z ciągu).Siatkówka , 111 bajtów
Daje wynik jednostkowy.
Każda linia powinna przejść do własnego pliku, ale możesz uruchomić kod jako jeden plik z
-s
flagą. Na przykład:Wyjaśnienie nastąpi później.
źródło
Java, 349 znaków
Proste podejście rekurencyjne. Oczekuje, że ciąg będzie pierwszym argumentem używanym do wywołania programu.
Rozszerzony:
źródło
Perl 5, 108
Sporządzono raczej jako tłumacz ustny niż przepisywanie i ewaluacja. Niezły pokaz, ale i tak fajnie się pisze.
Bez golfa:
źródło
Python, 99
Próbowałem różnych metod, ale najkrótszy, jaki mogłem uzyskać, był po prostu zamiennikiem i ewaluacją. Byłem mile zaskoczony, gdy stwierdziłem, że mogę zostawić wszystkie końcowe znaki
,
, ponieważ Python może analizować,[1,2,]
a końcowy przecinek końcowy po prostu stawia całość w krotce. Jedyna inna niż prosta część byłabyord(c)%31%7
do oddzielenia się różne znaki (ocenia się2
,3
,1
,0
na(
,)
,[
,]
odpowiednio)źródło
Java, 301
trochę inne podejście niż odpowiedź TheNumberOne, chociaż moja ma również charakter rekurencyjny. Dane wejściowe są pobierane z wiersza poleceń. Metoda void pozwala zaoszczędzić kilka bajtów podczas usuwania niepotrzebnych znaków.
rozszerzony:
źródło
Python,
117110109 bajtówJednym aspektem, z którym walczyłem, jest to, że funkcja ma zasadniczo dwie zwracane wartości: iloczyn / sumę i nową pozycję w ciągu. Ale potrzebuję funkcji, która zwraca tylko wynik, więc zwrócenie krotki nie działa. Ta wersja wykorzystuje argument „referencyjny” (lista z jednym elementem), aby przekazać pozycję z powrotem z funkcji.
Mam krótszą wersję (103 bajty), która używa zmiennej globalnej dla pozycji. Ale to zadziała tylko przy pierwszym połączeniu. A funkcja, która działa tylko raz, wydaje się nieco podejrzana. Nie jestem pewien, czy byłoby to dopuszczalne w przypadku golfa kodowego.
Algorytm jest prostą rekurencją. Wypróbowałem wiele wariantów wyrażenia aktualizującego produkt / sumę. Wymyśliłem kilka wersji, które były dokładnie tej samej długości, ale żadna z nich nie była krótsza.
Oczekiwałem, że podejście, które przekształci to w wyrażenie, które zostanie ocenione, prawdopodobnie wygra. Ale jak mówią: „iteracja jest człowiekiem, rekursja boska”.
źródło
Clojure - 66 bajtów
Zauważ, że
([] (()) ([] []) [()] [([[] []] [] []) ([] [])])
jest to prawidłowy formularz Clojure. Więc:g
.g
funkcja lokalna+
lub*
wynik wywołaniag
podelementów jej argumentów.x
w pustej sekwencji;(map g x)
zwracanil
iapply
zwraca wartość neutralną dla operacji.źródło
JavaScript (ES6), 116 bajtów
źródło