Уроки 74 - 76
Стек, очередь, дек
(§42. Стек, очередь, дек)

Содержание урока

Что такое стек?

Использование динамического массива

Вычисление арифметических выражений

Скобочные выражения

Очереди, деки

Вопросы и задания

Задачи

Скобочные выражения

Задача 2. Вводится символьная строка, в которой записано некоторое (арифметическое) выражение, использующее скобки трёх типов: (), [ ] и { }. Проверить, правильно ли расставлены скобки.

Например, выражение ()[{()[]}] — правильное, потому что каждой открывающей скобке соответствует закрывающая, и вложенность скобок не нарушается. Выражения

[() [[[() [()} )( ([)]

неправильные. В первых трёх есть непарные скобки, а в последних двух не соблюдается вложенность скобок.

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

В исходной задаче (с тремя типами скобок) хочется завести три счётчика и работать с каждым отдельно. Однако это решение неверное. Например, для выражения ({[)}] условия правильности выполняются отдельно для каждого вида скобок, но не для выражения в целом.

Задачи, в которых важна вложенность объектов, удобно решать с помощью стека. Нас интересуют только открывающие и закрывающие скобки, на остальные символы можно не обращать внимания.

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

Рис. 6.8

Введём следующие переменные:

type TStack=record
	data: array of char; 
	size: integer; 
end;

Отличие стека S от стека в предыдущей задаче только в том, что он содержит не целые числа, а символы (типа char). Поэтому приводить подпрограммы Push и Pop мы не будем, вы можете их переделать самостоятельно. Для удобства добавим только логическую функцию, которая возвращает значение True (истина), если стек пуст:

function isEmpty(S: TStack): boolean;
begin
	isEmpty:=(S.size=0);
end;

Введём строковые константы L и R, которые содержат все виды открывающих и соответствующих закрывающих скобок:

const L = '([{';
      R = ')]}';

Объявим переменные основной программы:

var S: TStack;
	р, i: integer; 
	str: string; 
	err: boolean; 
	с: char;

Переменная str — это исходная строка. Логическая переменная err будет сигнализировать об ошибке. Сначала ей присваивается значение False («ложь»).

В основном цикле меняется целая переменная i, которая обозначает номер текущего символа, переменная р используется как вспомогательная:

for i:=1 to Length(str) do begin
	p:=Pos(str[i] , L);						(1)
	if p>0 then Push(S,str[i]);				(2)
	p:=Pos(str[i],R);						(3)
	if p>0 then begin						(4)
		if isEmpty(S) then err:=True			(5)
		else begin
			с:=Pop(S);					(6)
			if p<>Pos(c,L) then err:=True	(7)
		end;
		if err then break					(8)
	end
end;

Сначала мы ищем символ sfr[i] в строке L, т. е. среди открывающих скобок (строка 1). Если это действительно открывающая скобка, помещаем её в стек (2). Далее ищем символ среди закрывающих скобок (3). Если нашли, то в первую очередь проверяем, не пуст ли стек. Если стек пуст, выражение неверное и переменная err принимает истинное значение. Если в стеке что-то есть, снимаем символ с вершины стека в символьную переменную с (6).

В строке (7) сравнивается тип (номер) закрывающей скобки р и номер открывающей скобки, найденной на вершине стека. Если они не совпадают, выражение неправильное, и в переменную err записывается значение True. Если при обработке текущего символа обнаружено, что выражение неверное (значение переменной err — True), нужно закончить цикл досрочно с помощью оператора break (8).

В конце программы остаётся вывести результат на экран:

if not err
then writeln('Выражение правильное.')
else writeln('Выражение неправильное.').

Следующая страница Очереди, деки

Cкачать материалы урока