Идеи реализации

Если бы требовалось проверять сбалансированность текста по отношению к парным скобкам только лишь одного вида, например, ( и ), можно было бы считывать символы текста один за другим, и, игнорируя все прочие символы, увеличивать на единицу некий счётчик при обнаружении открывающей скобки, и уменьшать его как только встретится закрывающая (счётчик должен быть установлен в ноль перед началом обработки). Если по завершению работы счётчик окажется положительным, очевидно, в тексте имелась непарная открывающая скобка. Стоит только счётчику уйти в минус, обработку нужно сразу же прекращать, поскольку все надежды на сбалансированность теряются. Таким образом у сбалансированного текста счётчик должен оставаться неотрицательным и обратиться в ноль в самом конце.

Наивные люди могут посчитать, что для проверки сбалансированности относительно скобок нескольких видов следует завести несколько счётчиков, и действовать так, как было описано выше, увеличивая или уменьшая соответствующий счётчик. Это заблуждение. Таким способом можно проверить сбалансированность относительно пар скобок каждого вида в отдельности, но не относительно всех пар скобок в совокупности. Простейший пример, который иллюстрирует нарушение баланса в совокупности: ([)].

Будем каждую встретившуюся открывающую скобку добавлять в конец некоторого списка (изначально пустого). Если же встретится закрывающая, мы попытаемся удалить из конца этого списка последнюю добавленную туда открывающую скобку. Мы пишем «попытаемся», так как список может оказаться пустым. Это означало бы, что к только что найденной закрывающей скобке не нашлось соответствующей открывающей, и сбалансированности уже не будет. Обработку можно на этом прекратить с формулировкой «непарная закрывающая скобка». Если же список был не пуст, проверяем, образуют ли пару найденная закрывающая и удалённая из конца списка открывающая скобки. Если да, то продолжаем обработку. Если нет, прекращаем процесс всё с той же формулировкой «непарная закрывающая скобка». Если в конце работы список открывающих скобок будет непуст, сообщаем о непарной открывающей скобке.

Таким образом, со списком открывающих скобок совершаются только два вида операций: что-то добавляется в его конец, и что-то удаляется с конца. Всё это должно напомнить нам о процедурах push и pop, которые именно так и поступают с массивом.

Такие списочные структуры, в которые можно добавлять элементы в конец, и удалять их тоже с конца, очень важны в информатике. Они называются стеками (stack — стопка каких-либо предметов, сложенных один на другой, например, тарелок). Обычно из стопки берут самую верхнюю тарелку, ту, которую положили туда последней. По аналогии со стопкой тарелок начало списка называют основанием стека, а его конец — вершиной.

Стек устроен как несправедливая очередь, в которой первым обслуживается и уходит тот, кто пришёл самым последним. Никакие крики «вас тут не стояло!» не могут изменить этот странный порядок обслуживания. Другое название стека — LIFO (Last In, First Out — последним пришёл, первым ушёл).

Так что массивы в Perl по совместительству являются стеками. Здесь следует заметить, что процедуры unshift и shift играют такую же роль по отношению к началу массива, что и процедуры push и pop по отношению к его концу. Список, который является стеком одновременно и с конца, и с начала, называют деком (DEQueue — Double Ended Queue — двухконечная очередь).

Обычная человеческая очередь, где вновь приходящий становится в хвост очереди, называется FIFO (First In, First Out).

Мы ещё неоднократно обратимся к стекам в последующих главах, тем более что массивы в Perl изначально наделены свойствами стека. Но при решении данной задачи мы организуем стек на базе строки, а не массива, поскольку в стеке будут храниться только лишь одиночные символы.

Информатика-54© А. Н. Швец