Jesteś kierownikiem projektu. Pewnego dnia jeden z twoich programistów oszalał ( nie twoja wina ) i wziął wszystkie wyrażenia z bazy kodu i dodał do nich losowe nawiasy, zanim odszedł na miejscu, narzekając na twoją niekompetencję ( również nie twoją winę ). Byłoby to łatwe rozwiązanie, jednak z jakiegoś powodu nie używasz kontroli wersji ( całkowicie nie twoja wina ). I z jakiegoś powodu żaden inny programista nie chce przejrzeć każdego wyrażenia, aby naprawić niedopasowane nawiasy ( nawiasem mówiąc, to nie twoja wina ). Programiści w dzisiejszych czasach, myślicie sobie. Musisz to zrobić sam. Horror! Takie zadania miały być pod tobą ...
Wejście będzie pojedynczym wierszem, który będzie zawierał lewy nawias kwadratowy ( ( [ {
) i prawy nawias kwadratowy ( ) ] }
). Może także, ale nie zawsze, zawierać komentarze ( /* */
) i literały łańcuchowe ( " "
lub ' '
) oraz różne liczby, litery lub symbole.
Będzie co najmniej jeden nawias (poza komentarzem lub dosłownym ciągiem znaków), który nie ma przeciwnej strony (poza komentarzem lub dosłownym ciągiem znaków). Na przykład błąd }
bez {
uprzedniego. Kolejny przykład: a, (
który nie ma )
później. Twój program zastąpi spacją minimalną liczbę nawiasów wymaganych do dopasowania nawiasów.
Przykłady:
(4 + (2 + 3))]
==> (4 + (2 + 3))
(nawias kwadratowy na końcu)
][][[]]
==> [][[]]
(nawias kwadratowy na początku)
("Hel(o!"))
==> ("Hel(o!")
(nawias na końcu)
( /* )]*/
==> /* )]*/
(nawias na początku)
{()]
==> ()
(nawias klamrowy i nawias kwadratowy)
- Dane wejściowe można pobierać z dowolnej dogodniejszej metody (STDIN, argument wiersza poleceń, odczyt z pliku itp.)
- Jeśli istnieje więcej niż jeden sposób rozwiązania problemu niedopasowania przy takiej samej liczbie usunięć, jest to dopuszczalne.
- Dopuszczalne będą jedynie niedopasowania w nawiasach. Literały ciągów i komentarze zawsze będą poprawnie tworzone.
- Tytuł pochodzi z tego wątku SO
- Nigdy nie będzie żadnych cytatów w komentarzach, cytatów w cytatach, komentarzy w komentarzach ani komentarzy w cytatach.
To jest kod golfowy, więc minimalna liczba bajtów wygrywa. Zadawaj pytania w komentarzach, jeśli specyfikacja nie jest jasna.
źródło
("foo (\") bar")
)?{{(})
powinno być{ }
równoważne, ponieważ scenariusz otwierający sugeruje, że kod działał od samego początku i{(})
liczy się jako niedopasowane nawiasy w każdym języku programowania, który znam (tj. „Powoduje zastój” ??). Ale już napisałem odpowiedź, więc jestem stronniczy.Odpowiedzi:
Ruby, 223 znaków
Ten okazał się trochę długi.
W pierwszej kolejności usuwa ciągi i komentarze, aby nie były liczone (i odkładały je później).
Następnie przechodzi przez ciąg znaków po znaku. Gdy znajdzie nawias otwierający, zapisuje swoją pozycję. Gdy znajdzie nawias zamykający, wyskakuje z odpowiedniej tablicy pamięci otwartego nawiasu.
Jeśli
pop
zwracanil
(tzn. Nie było wystarczającej liczby nawiasów otwierających), usuwa nawias zamykający. Po wykonaniu tej czynności usuwa pozostałe dodatkowe otwierające nawiasy klamrowe (tj. Nie było wystarczającej liczby nawiasów zamykających).Pod koniec programu odkłada wszystkie ciągi i komentarze z powrotem i wysyła je.
Nie golfowany:
źródło
(("string"/*comment*/)"string"
? Jeśli poprawnie czytam (wersję bez golfa), zastępujesz ciągi i komentarze ich indeksem wunparsed
tablicy, co prowadziłoby do podstawienia,((12)3
a następnie szukania nieistniejącego indeksu12
(lub11
). Widzę, że po prostushift
gra w golfa , ale czy nadal nie może mieć podobnego problemu?Python 3,
410322317Próbuje każdego możliwego zestawu usunięć, zaczynając od mniejszych, aż znajdzie taki, w którym nawiasy klamrowe są zrównoważone. (Rozumiem przez to w pełni poprawnie wyważone:
{{(})
produkuje( )
, a nie{(})
.)Pierwsza wersja używała generatora rekurencyjnego, co było naprawdę fajne, ale także bardzo długie. Ta wersja wykonuje proste pierwsze wyszukiwanie przy użyciu kolejki. (Tak, to algorytm czynnikowy. Jaki jest problem?: ^ D)
źródło
C - 406
Próba w C bez użycia wyrażeń regularnych.
Aby skompilować i uruchomić (na komputerze z systemem Linux):
gcc -o brackets.c
./brackets „[(])”
W niezdefiniowanych przypadkach, takich jak [(]), zwraca ostatnią prawidłową parę nawiasów ()
źródło
Python 3, 320
Podobnie jak rozwiązanie DLosc, sprawdza to każde możliwe usunięcie, ale wykorzystuje rekurencyjną strategię eksploracji i cofania, która jest znacznie szybsza. Wiem, że prędkość nie jest kryterium w golfie kodu, a wyczerpujące wyszukiwanie jest w każdym przypadku wykładnicze, ale to może obsłużyć dane wejściowe jak
({({({({({({({({(}}}}}}}}
za kilka sekund.źródło
O(n!!)
rozwiązanie, a nieO(n!)
. (Mój golf jestO(n*2^n)
zamiastO(2^n)
, ponieważo
faktycznie produkuje wszystkie wzory aż dor
usunięcia, zamiast dokładnier
usuwania. Łatwy do naprawy, ale kosztowałby kilka znaków.)