Poprawność rozmieszczonych nawiasów

Poprawność rozmieszczonych nawiasów

Napiszemy funkcję sprawdzającą poprawność rozmieszczonych nawiasów w stringu. Będziemy sprawdzać ciąg pod kątem zrównoważonego nawiasu, czyli czy wszystkie nawiasy otwierające mają nawias zamykający i czy są one logicznie umieszczone w ciągu. Takie sprawdzanie może służyć do sprawdzania plików xml, json itp…

Poprawne rozmieszczenie nawiasów

np. ( ) (( )) [] {} <> [<({})>] [[]] (((())))

Niepoprawne rozmieszczenie:

np. )
(
><
())[] ((( )) ( ) ( ) (( )) ( ) ) (

przykładowe rozwiązanie:

Użyjemy Stosu podczas iteracji przez każdy znak ciągu wejściowego, aby odłożyć wszystkie nawiasy otwierające na stos i zdjąć nawias jeśli pasuje. Pod koniec iteracji, jeśli stos jest pusty, wszystkie nawiasy zostały zrównoważone, czyli ciąg jest prawidłowy.

private static bool Solution(string input)
{
   Stack<char> brackets = new Stack<char>();
   Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {   
          { '(', ')' }, 
          { '{', '}' }, 
          { '[', ']' }, 
          { '<', '>' }  
   };

   try
   {               
      foreach (char mark in input) 
      {                  
         if (bracketPairs.Keys.Contains(mark))                   
            brackets.Push(mark);                                       
         else if (bracketPairs.Values.Contains(mark))    
         {                      
            if (mark == bracketPairs[brackets.First()]) 
               brackets.Pop();                      
            else            
               return false;
         }
         else                               
            continue;
      }
   }
   catch
   {         
      return false;
   }
        
   return brackets.Count() == 0 ? true : false;
}

Teraz co tutaj się dzieje:

  • używamy stosu do odkładania i zdejmowania przeglądanych nawiasów
  • korzystamy słownika do zdefiniowania nawiasów jakie będziemy sprawdzać
  • używamy try catch, gdzie wyjątek zostanie przechwycony w przypadku znalezienia nawiasu zamykającego, przed dowolnym nawiasem otwierającym. Co oznacza, że łańcuch nie jest zbalansowany, zwracamy false.
  • w pętli foreach przechodzimy przez każdy znak w ciągu wejściowym
  • następnie w if sprawdzamy, czy znak jest jednym z nawiasów otwierających
  • jeśli tak to odkładamy go na stos
  • jeśli nie sprawdzamy w else if, czy znak jest jednym z nawiasów zamykających
  • następnie sprawdzamy, czy nawias zamykający pasuje do ostatniego nawiasu otwierającego
  • jeśli tak to zdejmujemy go ze stosu
  • jeśli nie, to znaczy ze jest to niezrównoważony string i zwracamy false
  • w przeciwnym razie else, dalej przeglądamy znaki
  • na koniec upewniamy się, że wszystkie nawiasy są zamknięte

I teraz sprawdzamy nasze rozwiązanie.

static void Main(string[] args)
{
   Console.Write("Podaj string: ");
   string expression = Console.ReadLine();
   Console.WriteLine(Solution(expression));
} 

Przykładowe ciągi do sprawdzenia i spodziewane wyniki:

[Ala ma kota {"wszystko dobrze" (12 000), C# (test), Marcin (18), Tomek (44), Web Dev ()}]
[{}()<witaj swiecie>[[{{}}]]]
<test><imie>Tekst</imie)</test>

4 comments

Dodaj komentarz

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