Poprawność nawiasów — Zadanie rekrutacyjne #13

Czego szuka rekruter: Stack<T>, algorytm push/pop, poprawność działania na pełnym zestawie nawiasów
Poziom: Junior / Mid

Zadanie

Napisz funkcję, która sprawdza czy nawiasy w stringu są poprawnie zbalansowane. Program musi obsługiwać trzy typy nawiasów: (), [], {}. Dla "({[]})" wynik to true, dla "({)}" wynik to false.

Czego szuka rekruter

To klasyczne zadanie ze stosu (Stack). Rekruter sprawdza:

• Czy kandydat w ogóle zna tę strukturę danych i jej zastosowanie tutaj
• Czy rozumie dlaczego Stack a nie np. counter (counter nie działałby dla "({)}")
• Czy obsługuje przypadek gdy spotykamy nawias zamykający przy pustym stosie
• Czy wie jak zmapować nawias zamykający do otwierającego (Dictionary vs switch)

Błąd: counter-based podejście (if '(' count++, if ')' count--) nie sprawdza typów nawiasów — "(]" policzyłby jako zbalansowany.

Dlaczego Stack, a nie counter?

Wejście: "({)}"
Counter approach:  ( → +1, { → +1, ) → -1, } → -1, wynik count=0 → true  ❌ BŁĘDNIE
Stack approach:
  '(' → push '('
  '{' → push '{'
  ')' → peek = '{', oczekiwano '(' → false ✓ POPRAWNIE

Stos wykrywa że nawias zamykający nie pasuje do ostatnio otwartego — counter tego nie potrafi.

✅ Rozwiązanie z Dictionary dla mapowania

static bool IsBalanced(string? input)
{
    if (string.IsNullOrEmpty(input))
        return true;  // pusty string jest zbalansowany
    
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char>
    {
        [')'] = '(',
        [']'] = '[',
        ['}'] = '{',
    };
    
    foreach (char c in input)
    {
        if (c is '(' or '[' or '{')
        {
            stack.Push(c);
        }
        else if (pairs.TryGetValue(c, out char expected))
        {
            // Nawias zamykający — sprawdź czy stos ma pasujący otwierający
            if (stack.Count == 0 || stack.Pop() != expected)
                return false;
        }
        // Inne znaki (litery, spacje) ignorujemy
    }
    
    return stack.Count == 0;  // Wszystkie otwarte zostały zamknięte
}

Alternatywa — switch expression (bez Dictionary)

static bool IsBalancedSwitch(string? input)
{
    if (string.IsNullOrEmpty(input)) return true;
    
    var stack = new Stack<char>();
    
    foreach (char c in input)
    {
        switch (c)
        {
            case '(' or '[' or '{':
                stack.Push(c);
                break;
            case ')' when stack.TryPop(out char top) && top == '(':
            case ']' when stack.TryPop(out top) && top == '[':
            case '}' when stack.TryPop(out top) && top == '{':
                break;
            case ')' or ']' or '}':
                return false;  // Stos pusty lub zły typ
        }
    }
    
    return stack.Count == 0;
}

Przypadki testowe — myśl o nich PRZED napisaniem kodu

"()"          → true   (podstawowy)
"()[]{}"      → true   (wiele par)
"({[]})"      → true   (zagnieżdżone)
"({)}"        → false  (zły porządek)
"((("         → false  (nieskończone otwarte)
")))"         → false  (zamykające bez otwierających)
""            → true   (pusty)
"hello (world)" → true (inne znaki ignorowane)

Testy jednostkowe

[Theory]
[InlineData("()",        true)]
[InlineData("()[]{}",   true)]
[InlineData("({[]})",   true)]
[InlineData("({)}",     false)]
[InlineData("((((",     false)]
[InlineData(")))",      false)]
[InlineData("",         true)]
[InlineData("abc(def)ghi", true)]
[InlineData("(]",       false)]
public void IsBalanced_ReturnsCorrectResult(string input, bool expected)
{
    Assert.Equal(expected, IsBalanced(input));
}

Co powiedzieć na rozmowie

“Counter nie wystarczy bo nie sprawdza typów — '(]' miałby counter=0 ale nie jest zbalansowany. Stos pozwala zapamiętać kolejność nawiasów: każdy otwierający odkladam na stos, przy zamykającym zdejmuję wierzchołek i sprawdzam czy pasuje. Jeśli stos jest pusty gdy spotykam nawias zamykający lub wierzchołek nie pasuje — string nie jest zbalansowany. Na końcu stos musi być pusty.”

Podsumowanie

Stos to naturalna struktura dla tego problemu — LIFO pasuje do “ostatni otworzony musi być pierwszym zamkniętym”. Zadanie pojawia się często w rekrutacjach bo testuje znajomość Stack i myślenie algorytmiczne w konkretnym scenariuszu (walidacja XML/JSON/kodu).