Формулировка. Дана последовательность символов длины n (n >= 1). Проверить баланс круглых скобок в этом выражении. Например, при вводе выражения (())() программа должна сообщить о правильности расстановки скобок, а при вводе выражения ((()) – о неправильности.
Примечание: сбалансированной скобочной записью называется символьное выражение, в котором каждой открывающей скобке соответствует закрывающая скобка правее и наоборот, каждой закрывающей скобке соответствует открывающая скобка левее.
Так как мы вводим последовательность произвольных символов, в которой учитываются только круглые скобки, то между знаками скобок может находиться любая символьная информация, в силу чего корректная программа может проверять баланс скобок в арифметических выражениях, тексте и т. д. Например, выражение (7y + 1)(17 – (x + 3)) – правильное, а (146x + 18(y + 9) – неправильное, что сможет распознать программа.
Решение. Представим себе посимвольный ввод скобочного выражения с клавиатуры (когда уже введено некоторое количество символов) и подумаем, какие выводы можно сделать на данном этапе (для простоты восприятия будем рассматривать выражения, состоящие только из скобок):
1) ((()
Сейчас «как бы» мы видим начало скобочного выражения и не знаем, какие символы следуют далее. Какие выводы можно сделать на этом этапе? Имеющееся выражение содержит лишние открывающие скобки и его можно как сбалансировать, если дописать две закрывающие скобки, так и нарушить, если оставить в том же виде или применить множество других комбинаций. Вывод: если имеются лишние открывающие скобки, то выражение еще может быть сбалансировано.
2) (()))
Это выражение содержит явное нарушение баланса скобок, которое уже не может быть скомпенсировано добавлением любых скобочных комбинаций справа, так как не всем закрывающим скобкам соответствует по одной открывающей скобке левее. Отсюда вывод: если в выражении появилась хотя бы одна лишняя закрывающая скобка, то выражение «неправильное» и дальнейшая проверка бессмысленна.
Приступим к реализации этих рассуждений. Заведем счетчик count для подсчета открывающих и закрывающих скобок: при вводе открывающей скобки будем увеличивать его на 1, а при вводе закрывающей – уменьшать на 1.
Нам нужно создать переменную c символьного типа char, в которую мы будем последовательно вводить все символы нашего выражения. Стоит отметить, что в тип char также входит пробел, что влияет на значение длины вводимой последовательности. Например, длина n вводимого выражения (7y + 1)(17 – (x + 3)) равна 22 (пробелы выделены красным цветом).
После ввода n мы входим в цикл из n повторений, в котором вводим в c очередной символ. Полагаясь на предыдущие рассуждения, мы увеличиваем count на 1, если c = ‘(‘ и уменьшаем на 1, если c = ‘)’:
readln(n);
count := 0;
for i := 1 to n do begin
read(c);
if c = ‘(‘ then inc(count);
if c = ‘)’ then dec(count)
end;
Примечание: функция dec(x) уменьшает значение переменной x числового типа на 1.
Кстати, так как любой любая переменная не может иметь сразу два каких-либо значения, мы можем поместить второй условной оператор цикла в else-блок первого, что будет выглядеть логичнее, но мы не будем этого делать, чтобы повысить читаемость кода.
Отметим, что ввод n осуществляется с помощью readln(), так как он требует ввод enter’а в качестве ограничителя. При вводе n через read() далее следующий пробел или enter будет включен непосредственно во вводимую последовательность, что повлечет ошибку. Кроме того, нельзя разделять лишними пробелами или enter’ами символы последовательности при вводе, так как они не игнорируются при вводе в переменные типа char и должны быть включены в последовательность (при этом каждый пробел добавляет к длине 1, а каждый enter – 2).
Вернемся к разбору. Как же быть, если некоторый начальный фрагмент вводимого выражения станет заведомо неправильным, то есть, если в нем появятся лишние закрывающие скобки? Но тогда при появлении лишней («некомпенсируемой») закрывающей скобки переменная count станет равна –1, что можно оформить как условие выхода из цикла и поместить после первых двух операторов сравнения:
if count = -1 then break;
Какие результаты мы получим по завершении цикла?
1) Цикл прошел по всем символам, но были найдены лишние открывающие скобки (то есть, count > 0), компенсирования которых мы ожидали, однако они так и не были скомпенсированы и скобочная последовательность неправильная;
2) Цикл прошел по всем символам (то есть, не было выхода), причем количество скобок обоих видов равно (то есть,count = 0) и скобочная последовательность, соответственно, правильная;
3) Был осуществлен выход из цикла (то есть, нашли «некомпенсируемую» закрывающую скобку и count = –1) и последовательность неправильная.
Выходит, правильный ответ даст вывод выражения count = 0 (оно истинно во 2-ом случае и ложно в 1-ом и 3-ем):
writeln(count = 0);
Код:
- program BracketSequence;
- var
- count: integer;
- i, n: byte;
- c: char;
- begin
- readln(n);
- count := 0;
- for i := 1 to n do begin
- read(c);
- if c = ‘(‘ then inc(count);
- if c = ‘)’ then dec(count);
- if count = -1 then break
- end;
- writeln(count = 0)
- end.