Книга: Программирование на языке Ruby

9.2.2. Обнаружение несбалансированных скобок

9.2.2. Обнаружение несбалансированных скобок

В силу самой природы употребления различного вида скобок в выражениях проверить корректность написания можно с помощью стека. При открытии каждого следующего уровня вложенности скобок стек растет. Как только встречается закрывающая скобка, соответствующий элемент выталкивается из стека. Если при обнаружении закрывающей скобки в стеке ничего не оказалось или, наоборот, выражение уже закончилось, а в стеке что-то осталось, значит, выражение записано неверно.

def paren_match(str)
 stack = Stack.new
 lsym = "{I(<"
 rsym = "}])>"
 str.each_byte do |byte|
  sym = byte.chr
  if lsym.include? sym
   stack.push(sym)
  elsif rsym.include? sym
   top = stack.peek
   if lsym.index(top) != rsym.index(sym)
    return false
   else
    stack.pop
   end
   # Игнорируем символы, отличные от скобок...
  end
 end
 # Убедимся, что стек пуст...
 return stack.empty?
end
str1 = "(((a+b))*((c-d)-(e*f))"
str2 = "[[(a-(b-c))], [[x,y]]]"
paren_match str1 # false
paren_match str2 # true

Наличие вложенности естественным образом наводит на мысль о применении стека. Чуть сложнее распознать несбалансированные теги в HTML- или XML-документе. Лексемы состоят из нескольких символов, но логическая структура задачи остается той же самой. Вот еще типичные примеры задач, требующих стека: преобразование выражений из инфиксной формы в постфиксную (и наоборот), вычисление постфиксного выражения (как делается в виртуальной машине Java и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

Оглавление книги