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

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

Принцип роботи алгоритму

1. Кожного разу, коли бачимо відкриваючу дужку — додаємо її в стек.
2. Якщо натрапили на закривальну — порівнюємо її з останньою відкривальною (з вершини стеку).
3. Якщо збігаються — продовжуємо.
4. Якщо ні — одразу повертаємо false.
5. Якщо після проходу рядка стек порожній — всі дужки були правильно закриті, тому повертаємо true.