Разработка

С точки зрения поставленной задачи все символы из файла делятся на три категории: открывающие скобки, закрывающие скобки, и все прочие символы. Нам нужен способ быстро определять тип символа. Perl, как всегда, позволяет сделать это многими разными способами. Мы выберем такой: поместим в строку все интересующие скобки парами. В результате получится что-то вроде этого: ()[]{}. Для определения типа символа будем искать его индекс в такой строке. Если индекс окажется чётным, наш символ — открывающая скобка, если нечётный — закрывающая. Если символ отсутствует в строке, он не является скобкой, и попадает в категорию прочих. Отправим строку со скобками в переменную $brackets:

my $brackets='()[]{}';

Для поиска символа в строке применим встроенную процедуру index. При неудачном поиске процедура вернёт значение -1. Если символ является скобкой, будет возвращено неотрицательное значение.

Для организации стека можно использовать возможность, которая напрашивается: массив. Мы же снова пойдём непроторенной дорогой, и организуем стек символов на базе строки. Строку разместим в переменной $charStack, изначально пустой:

my $charStack='';

Добавление символа в стек осуществляется командой

$charStack.=$char;

Для удаления символа из стека годится встроенная процедура chop. Эта процедура возвращает символ, удалённый из конца строки:

$char=chop $charStack;

Поскольку наш стек состоит только лишь из символов, использовать стек на базе массива было бы неоправданной роскошью, поскольку массив — довольно массивная структура.

Представим, что символы проверяемого файла в цикле по очереди попадают в переменную $char. Первым делом определим тип этого символа. Если символ оказался не скобкой, сразу же переходим к следующему:

my $type=index($brackets, $char);
next if $type==-1;

Открывающую скобку (unless($type % 2)) добавляем в стек. Действия в случае закрывающей скобки требуют подробного обсуждения.

Если встретилась закрывающая скобка, стек не должен быть пуст, а на его вершине должная располагаться парная открывающая скобка. Если хотя бы одно из этих условий не выполнено, можно заключить, что баланс скобок нарушен, и тогда программу можно завершать с выдачей сообщения о непарной закрывающей скобке. Стек непуст, если выполнено условие length $charStack. Проверить, находится ли на вершине стека парная скобка, поможет следующий приём. Снимем со стека вершину: chop $charStack. Присоединим к ней проверяемый символ — закрывающую скобку: (chop $charStack).$char. Будем искать полученную двухсимвольную строку в переменной $brackets. Для поиска снова применим процедуру index. Если поиск привёл к успеху, скобки соответствуют друг другу, в этом случае переходим к следующему символу. В противном случае, если, к примеру, выражение (chop $charStack).$char равно [), баланс скобок нарушен, и программа завершается всё с тем же сообщением о непарной закрывающей скобке.

Итак, остаток цикла представляет собой следующую условную конструкцию:

unless($type % 2)
{
	$charStack.=$char;
}
else
{
	die "$0: Баланс нарушен: непарная закрывающая скобка\n"
		unless length $charStack
			and index($brackets, (chop $charStack).$char)>=0
}

Непустой стек по завершении цикла свидетельствует о наличии непарной открывающей скобки:

die "$0: Баланс нарушен: непарная открывающая скобка\n" if length $charStack;

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