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>

9 comments

  1. Cześć, wszystko będzie tutaj i oczywiście każdy udostępnia dane, to naprawdę świetne, pisz dalej.

  2. Wreszcie mam znalazłem coś, co mi pomogło. Wielkie dzięki!

  3. I’ve been exploring for a lіttⅼe for any high-quality articlеs or blog
    posts in this sort of house . Exρloring in Yahoo I at last stumbled upon this site.
    Studying this information So i’m satisfied to show tһat I’ve a very
    excelⅼent uncanny feeling I came upon exaⅽtly what I needed.
    I sucһ a lot certainly will make sure to don?t forget this web site and
    provides it a glance regularly.

  4. It іs truly a great and helpful ⲣiеce of information. I am
    haрpy that you јust shared this helpful information with us.
    Please stay us up to date like this. Thanks
    for sharіng.

  5. Cóż to za strona internetowa! Ta strona internetowa przedstawia nam cenne fakty, tak trzymaj.

  6. Everyone loves what you guys are up too. This sort of clever work and coverage!
    Keep up the terrific works guys I’ve included you guys to our blogroll.

    Also visit my web site: saturation; Albert,

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *