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 и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.
Данный текст является ознакомительным фрагментом.