Spis treściKliknij link, aby przejść do wybranego miejsca
Ta treść została automatycznie przetłumaczona z ukraińskiego.
Warunek dla zadania jest następujący. Stwórz funkcję valid_braces, która przyjmuje ciąg składający się tylko z nawiasów: ()[]{}. Funkcja powinna zwracać true, jeśli wszystkie nawiasy otwierają się i zamykają w poprawnej kolejności, lub false — jeśli nawiasy są źle ustawione.
Przykład wykonania metody:
valid_braces("()") → true
valid_braces("({[]})") → true
valid_braces("({[)]}") → false
valid_braces("(((()") → false
valid_braces("{[()]}[]") → true
Jak działa sprawdzanie nawiasów?
To zadanie klasycznie rozwiązuje się za pomocą stosu — struktury danych, która działa na zasadzie „ostatni wszedł — pierwszy wyszedł”. Idea polega na tym, aby dodawać nawiasy otwierające do stosu, a gdy natrafimy na nawias zamykający — sprawdzać, czy odpowiada on temu, który jest na szczycie stosu. Jeśli tak — usuwamy ze stosu; jeśli nie — ciąg jest nieprawidłowy.
Test (RSpec) dla sprawdzenia metody
RSpec.describe '#valid_braces' do
it 'zwraca true dla poprawnych nawiasów' do
expect(valid_braces('()')).to eq(true)
expect(valid_braces('([])')).to eq(true)
expect(valid_braces('{[()]}')).to eq(true)
expect(valid_braces('{[()]}[]')).to eq(true)
end
it 'zwraca false dla niepoprawnych nawiasów' do
expect(valid_braces('[(])')).to eq(false)
expect(valid_braces('({[)]}')).to eq(false)
expect(valid_braces('((')).to eq(false)
expect(valid_braces(']')).to eq(false)
end
end
Metoda valid_braces
def valid_braces(string)
stack = []
pairs = { ')' => '(', ']' => '[', '}' => '{' }
string.each_char do |char|
if pairs.values.include?(char)
stack.push(char)
elsif pairs.keys.include?(char)
return false if stack.pop != pairs[char]
end
end
stack.empty?
end
Zasada działania algorytmu
- Za każdym razem, gdy widzimy nawias otwierający — dodajemy go do stosu.
- Jeśli natrafimy na nawias zamykający — porównujemy go z ostatnim nawiasem otwierającym (ze szczytu stosu).
- Jeśli się zgadzają — kontynuujemy.
- Jeśli nie — od razu zwracamy false.
- Jeśli po przejściu ciągu stos jest pusty — wszystkie nawiasy zostały poprawnie zamknięte, więc zwracamy true.
To podejście można stosować do parzystych symboli dowolnego typu — nie tylko nawiasów. Doskonale nadaje się do sprawdzania poprawności zagnieżdżonych struktur, na przykład w parserach lub analizatorach HTML.
