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

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

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

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

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

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

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