Задача на перевірку правильності розстановки дужок (Ruby)

21 трав., 10:27

2 хв. читання

Обкладинка допису: Задача на перевірку правильності розстановки дужок (Ruby)

ЗмістНатисність на посилання, щоб перейти до потрібного місця

Як працює перевірка дужок?Тест (RSpec) для перевірки методу Метод valid_braces Принцип роботи алгоритму

Умова для задачі наступна. Створіть функцію 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-аналізаторах.