Сбалансированные символы (общий случай)¶
Показанная выше задача о сбалансированных скобках является частным случаем
более общей ситуации, возникающей во многих языках программирования.
Обобщённая проблема балансировки и вложенности различных типов открывающих и
закрывающих символов возникает очень часто. Например, в Python квадратные
скобки, [
и ]
, используются для списков, фигурные скобки, {
и }
,
- для словарей, а круглые ((
и )
) - для кортежей и арифметических выражений.
Можно сколько угодно перемешивать символы до тех пор, пока каждый из них поддерживает
свои открывающие и закрывающие отношения. Для строк вроде
{ { ( [ ] [ ] ) } ( ) }
[ [ { { ( ( ) ) } } ] ]
[ ] [ ] [ ] ( ) { }
“хорошая сбалансированность” заключается не только в том, что каждый открывающий символ имеет соответствующий закрывающий, но и в совпадении типов этих символов.
Сравните верхний пример со следующими несбалансированными строками:
( [ ) ]
( ( ( ) ] ) )
[ { ( ) ]
Простой контролёр скобок из предыдущего раздела может быть легко расширен для обработки этих новых типов символов. Напомним, что каждый открывающий символ просто помещается в стек в ожидании появления в последовательности соответствующего закрывающего символа. Когда это происходит, единственная разница в том, что мы должны проверить, корректна ли связь с типом символа на вершине стека. Если они не соответствуют друг другу, то строка разбалансирована. Аналогично, если вся входная последовательность обработана и стек пуст, то строка сбалансирована правильно.
Реализующая эту идею программа на Python показана в ActiveCode 5.
Единственное изменение коснулось строки 16, где вызывается вспомогательная функция
matches
, помогающая с соотнесением символов. Каждый символ, удаляемый из стека,
должен быть проверен на то, что он верно сопоставляется с текущим
закрывающим символом. Если возникает ошибка, то булева переменная balanced
устанавливается в False
from pythonds.basic.stack import Stack
def parChecker(symbolString):
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "([{":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top,symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open,close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
print(parChecker('{{([][])}()}'))
print(parChecker('[{()]'))
Решение общего случая балансирования символов (parcheck2)
Эти два примера показывают, что стеки - очень важная структура данных для обработки языковых конструкций в информатике. Практически любая нотация, о которой вы можете подумать, имеет некоторый тип вложенных символов, которые должны согласовываться между собой сбалансированным образом. Кроме вышеизложенного, есть целый ряд других важных задач в области информатики, требующих применения стеков. Мы продолжим их исследовать в следующем разделе.