Nawiasy – omówienie rozwiązania

O co chodzi w zadaniu?

Dostajemy n nawiasów, zamykających “)” lub otwierających “(“. Nasze zadanie polega na sprawdzeniu czy ich ciąg jest poprawny, tj. Czy każdy nawias otwierający jest poprawnie zamknięty, np “( ( ) )“ lub “( ) ( )”.

Obserwacje

Kluczem do rozwiązania zadania jest zauważenie dwóch własności:

  1. W chwili gdy liczba nawiasów zamkniętych przekracza ilość nawiasów otwartych ciąg na pewno nie jest poprawny [np. “( ) )” ],
  2. Liczba nawiasów otwierających i zamykających musi być równa  [ciąg “ ( ( ) ) ” jest poprawny, natomiast “ ( ( ( ) ) “ już nie].

Rozwiązanie

Chcemy więc zliczać oba typy nawiasów. Przyda nam się do tego zmienna k. Przechodząc po każdym elemencie ciągu będziemy ją odpowiednio zwiększać (k++) przy napotkaniu nawiasu otwartego, lub zmniejszać (k–) kiedy nawias jest zamknięty – przechowuje informację o niezamkniętych jeszcze nawiasach. Pozwoli to nam sprawdzić wcześniej przedstawione warunki:

  1. Jeżeli ciąg jest niepoprawny, k w trakcie sprawdzania nawiasów stanie się liczbą ujemną,
  2. Jeżeli ciąg jest niepoprawny, k po sprawdzeniu całego ciągu nie będzie równe 0.

Jeżeli żadna z tych sytuacji nie zachodzi możemy stwierdzić, że ciąg jest poprawny – wypisać “TAK”, a w przeciwnym wypadku wypisać “NIE”.

Link do kodu

https://ideone.com/b9lGF4

Autor: Maciej Świetlik

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*