С точки зрения поставленной задачи все символы из файла делятся на три
категории: открывающие скобки, закрывающие скобки, и все прочие символы. Нам
нужен способ быстро определять тип символа. Perl, как всегда, позволяет сделать
это многими разными способами. Мы выберем такой: поместим в строку все
интересующие скобки парами. В результате получится что-то вроде этого:
()[]{}
. Для определения типа символа будем искать его индекс
в такой строке. Если индекс окажется чётным, наш символ — открывающая скобка,
если нечётный — закрывающая. Если символ отсутствует в строке, он не является
скобкой, и попадает в категорию прочих. Отправим строку со скобками
в переменную $brackets
:
Perlmy $brackets='()[]{}';
Для поиска символа в строке применим встроенную процедуру
index
. При неудачном поиске процедура вернёт значение
-1
. Если символ является скобкой, будет возвращено
неотрицательное значение.
Для организации стека можно использовать возможность, которая напрашивается:
массив. Мы же снова пойдём непроторенной дорогой, и организуем стек символов
на базе строки. Строку разместим в переменной $charStack
,
изначально пустой:
Perlmy $charStack='';
Добавление символа в стек осуществляется командой
Perl$charStack.=$char;
Для удаления символа из стека годится встроенная процедура
chop
. Эта процедура возвращает символ, удалённый из конца
строки:
Perl$char=chop $charStack;
Поскольку наш стек состоит только лишь из символов, использовать стек на базе массива было бы неоправданной роскошью, поскольку массив — довольно массивная структура.
Представим, что символы проверяемого файла в цикле по очереди попадают
в переменную $char
. Первым делом определим тип этого
символа. Если символ оказался не скобкой, сразу же переходим к следующему:
Perlmy $type=index($brackets, $char); next if $type==-1;
Открывающую скобку (unless($type % 2)
) добавляем
в стек. Действия в случае закрывающей скобки требуют подробного обсуждения.
Если встретилась закрывающая скобка, стек не должен быть пуст, а на его вершине
должная располагаться парная открывающая скобка. Если хотя бы одно из этих
условий не выполнено, можно заключить, что баланс скобок нарушен, и тогда
программу можно завершать с выдачей сообщения о непарной закрывающей скобке.
Стек непуст, если выполнено условие length
$charStack
. Проверить, находится ли на вершине стека парная скобка,
поможет следующий приём. Снимем со стека вершину: chop
$charStack
. Присоединим к ней проверяемый символ — закрывающую скобку:
(chop $charStack).$char
. Будем искать полученную
двухсимвольную строку в переменной $brackets
. Для поиска
снова применим процедуру index
. Если поиск привёл
к успеху, скобки соответствуют друг другу, в этом случае переходим к следующему
символу. В противном случае, если, к примеру, выражение (chop $charStack).$char
равно [)
,
баланс скобок нарушен, и программа завершается всё с тем же сообщением
о непарной закрывающей скобке.
Итак, остаток цикла представляет собой следующую условную конструкцию:
Perlunless($type % 2) { $charStack.=$char; } else { die "$0: Баланс нарушен: непарная закрывающая скобка\n" unless length $charStack and index($brackets, (chop $charStack).$char)>=0 }
Непустой стек по завершении цикла свидетельствует о наличии непарной открывающей скобки:
Perldie "$0: Баланс нарушен: непарная открывающая скобка\n" if length $charStack;