Сбалансированные символы (общий случай)

Показанная выше задача о сбалансированных скобках является частным случаем более общей ситуации, возникающей во многих языках программирования. Обобщённая проблема балансировки и вложенности различных типов открывающих и закрывающих символов возникает очень часто. Например, в Python квадратные скобки, [ и ], используются для списков, фигурные скобки, { и }, - для словарей, а круглые (( и )) - для кортежей и арифметических выражений. Можно сколько угодно перемешивать символы до тех пор, пока каждый из них поддерживает свои открывающие и закрывающие отношения. Для строк вроде

{ { ( [ ] [ ] ) } ( ) }

[ [ { { ( ( ) ) } } ] ]

[ ] [ ] [ ] ( ) { }

“хорошая сбалансированность” заключается не только в том, что каждый открывающий символ имеет соответствующий закрывающий, но и в совпадении типов этих символов.

Сравните верхний пример со следующими несбалансированными строками:

( [ ) ]

( ( ( ) ] ) )

[ { ( ) ]

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

Реализующая эту идею программа на Python показана в ActiveCode 5. Единственное изменение коснулось строки 16, где вызывается вспомогательная функция matches, помогающая с соотнесением символов. Каждый символ, удаляемый из стека, должен быть проверен на то, что он верно сопоставляется с текущим закрывающим символом. Если возникает ошибка, то булева переменная balanced устанавливается в False




Решение общего случая балансирования символов (parcheck2)

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

Next Section - Конвертирование десятичных чисел в двоичные