Зміст дописунатисність на посилання, щоб перейти до потрібного місця
Умова для задачі наступна. Створіть функцію valid_braces, яка приймає рядок, що складається лише з дужок: ()[]{}. Функція повинна повертати true, якщо всі дужки відкриваються та закриваються в правильному порядку, або false — якщо дужки розставлені некоректно.
Приклад виконання методу:
valid_braces("()") → true
valid_braces("({[]})") → true
valid_braces("({[)]}") → false
valid_braces("(((()") → false
valid_braces("{[()]}[]") → true
Як працює перевірка дужок?
Ця задача класично розв'язується за допомогою стека — структури даних, яка працює за принципом «останній увійшов — перший вийшов». Ідея полягає в тому, щоб додавати відкривальні дужки в стек, а коли натрапляємо на закривальну дужку — перевіряти, чи відповідає вона тій, що на вершині стеку. Якщо так — видаляємо зі стеку; якщо ні — рядок невірний.
Тест (RSpec) для перевірки методу
RSpec.describe '#valid_braces' do
it 'повертає true для валідних дужок' 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 'повертає false для невалідних дужок' 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
Метод 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
Принцип роботи алгоритму
- Кожного разу, коли бачимо відкриваючу дужку — додаємо її в стек.
- Якщо натрапили на закривальну — порівнюємо її з останньою відкривальною (з вершини стеку).
- Якщо збігаються — продовжуємо.
- Якщо ні — одразу повертаємо false.
- Якщо після проходу рядка стек порожній — всі дужки були правильно закриті, тому повертаємо true.
Цей підхід можна використовувати для парних символів будь-якого типу — не лише дужок. Він чудово підходить для перевірки правильності вкладених структур, наприклад, у парсерах або HTML-аналізаторах.
