Pisząc mój interpreter języka Lisp (dokładnie dialektu Scheme) o nazwie LIPS, zdecydowałem się dodać obsługę nawiasów kwadratowych, ponieważ niektóre książki do języka Scheme, mieszają nawiasy okrągłe oraz kwadratowe. Jednak aby nie komplikować parsera, nie sprawdzał on, czy nawiasy do siebie pasują i np. można było wywołać kod z pomieszanymi nawiasami.
W tym wpisie przedstawię jak napisać poprawne parowanie nawiasów, czyli funkcję, która może się przydać nie tylko przy parsowaniu języka Lisp. [Spoiler] Do tego celu nie warto nawet próbować, używać Wyrażeń Regularnych (RegExp).
Zasada parowania nawiasów jest prosta, podobna do tej, którą mieliśmy w przypadku parsera S-Wyrażeń, czyli podstawy języka LISP. Tylko w przypadku parowania, musimy wziąć pod uwagę tylko nawiasy, możemy zignorować pozostałe tokeny.
Stos
Do parowania najprościej jest użyć stosu. Stos to jedna z najprostszych struktur danych. Mamy dwie
podstawowe operacje odkładania na stosie (push
) oraz zdejmowania (pop
). Działa to analogicznie do stosu
książek. Ostatni odłożony na stosie będzie pierwszym w kolejności do zdjęcia. Dzięki stosowi łatwiej
jest przetwarzać (parsować) znaki, które mają swój początek i koniec jak np. S-Wyrażenia, zwykłe
nawiasy czy znaczniki XML.
Obie metody (czyli push
oraz pop
posiadają także tablice, które można używać jak stosu), ale
warto napisać sobie prostą funkcja/konstruktor (lub klasę) jako abstrakcję stosu, aby uprościć kod i
lepiej nazwać operacje na tej strukturze danych. Jak np. sprawdzanie co znajduje się na szczycie
stosu.
Użyłem funkcji konstruktora oraz prototypu, ponieważ nie lubię klas ES6 (ES2015).
Algortym parowania nawiasów
Teraz przedstawię algorytm (czyli opis kroków) parowania nawiasów:
Musimy mieć pętle przechodzącą po tokenach, najlepiej po samych nawiasach.
Gdy mamy otwierający nawias, musimy wrzucić element na stos. Gdy mamy zamykający nawias, musimy sprawdzić, czy ostatni na stosie to pasujący znak (odpowiednik zamykającego). Jeśli tak zdejmujemy go ze stosu. Jeśli nie to znaczy, że mamy pomieszane nawiasy i musimy zwrócić wyjątek. Jeśli mamy zamykający nawias, ale nie ma nic na stosie, to także musimy zwrócić wyjątek, ponieważ nie ma otwierającego nawiasu, który pasuje to tego zamykającego.
Po sprawdzeniu wszystkich znaków (tokenów), jeśli coś jest na stosie, to znaczy, że nie zamknęliśmy
wszystkich nawiasów, ale taki przypadek jest poprawny, dlatego w tym przypadku po prosu zwracamy
false
, a nie wyjątek.
Jeśli stos jest pusty to zwracamy true
. Oznacza to, że mamy poprawnie skończone wyrażenie. Gdyby
to było S-Wyrażenie moglibyśmy użyć parsera, aby je przetworzyć i nie musielibyśmy się martwić o
niepoprawny wynik (oczywiście jeśli parser jest poprawnie napisany).
Kod funkcji parowania nawiasów
Poniżej kod funkcji (użyliśmy funkcji tokenize, którą możesz zobaczyć we wpisie o parsowaniu S-Wyrażeń).
Kod jest o wiele prostszy niż parser języka LISP (S-Wyrażeń), ponieważ nie musimy przetwarzać wszystkich znaków (tokenów). Parser Lispa także używał stosu.
Podsumowanie
Nie warto nawet zaczynać przetwarzać wyrażeń, które mają swoje otwierające i zamykające znaki, za pomocą wyrażeń regularnych. Na Stack Overflow jest słynne pytanie:
„RegEx match open tags except XHTML self-contained tags”
I odpowiedź trochę w stylu Monty Pythona (ciężko to opisać trzeba przeczytać).
Parowanie nawiasów to dokładnie taki sam problem, jak parsowanie HTML. Jak widać z załączonego kodu, jest to zadanie dość proste, gdy używa się stosu. Możliwe że da się napisać takie Wyrażenie Regularne, które sprawdzi czy ciąg znaków ma sparowane nawiasy. Ale sprawa się komplikuje, gdy np. mamy ciągi znaków i nawiasy wewnątrz powinny być ignorowane. Rozwiązanie okazuje się jednak proste, gdy używamy właściwych narzędzi.
Osobiście uwielbiam Wyrażenia Regularne, ale warto zawsze się zastanowić, czy jest to dobre narzędzie do danego celu.
Jeśli masz jakiś pomysł, do czego jeszcze można by użyć funkcji parującej nawiasy lub może używasz już takiej funkcji gdzieś w swoim kodzie albo masz zamiar, koniecznie napisz w komentarzu.
Komentarze
Hasło, które podasz umożliwi ponowne zalogowanie się i np. usunięcie komentarza, jest dobrowolne. Email jest szyfrowany i używany do wysyłania powiadomień o odpowiedziach do komentarzy oraz do pobierania awatara dzięki usłudze Gravatar.com.