Динамическая реализация стека
Стеки
Понятие стекачасто встречается в повседневной жизни, например, грузовой отсек транспортного самолета, куда заезжают автомобили один за другим, а по приземлении первым (причем задом!) выезжает тот автомобиль, который заехал последним. Аналогичные примеры: тупиковый железнодорожный разъезд для сортировки вагонов, винтовочный патронный магазин. Последний пример иллюстрирует тот факт, что стек иногда называют магазином. Таким образом, стек — это структура, работа с которой происходит по принципу LIFO: последним пришел — первым ушел (от англ. Last — In — First— Out). Включение элемента в стек и исключение элемента из стека выполняются только с одной стороны, которая называется вершиной стека.
В программировании стеки используются не менее часто, чем в жизни. Любая операционная система содержит так называемый системный стек, куда помещаются адреса возврата и ряд других значений при вложенном вызове процедур и функций. Когда процедура (или функция), вызванная последней, завершит работу, из системного стека выбираются данные, необходимые для продолжения работы программы. Еще примеры: компилятор на этапе синтаксического разбора текста программы использует стек, интерпретатору стек необходим для вычисления выражений. Простейшая задача: определение правильности скобок в выражении — не может быть в принципе решена без использования стека.
Для работы со стеком необходимы следующие операции:
q инициализация стека, то есть подготовка структуры;
q включение нового элемента в стек (англ. push – заталкивать);
q проверка стека на пустоту;
q исключение элемента из стека (англ. pop – выталкивать).
При решении задач, использующих стек, совершенно неважно, каким образом организован сам стек. Мы рассмотрим сейчас два способа реализации стека.
Динамическая реализация стека
Динамический стек— это линейный односвязный список. Работа с этим списком осуществляется по соответствующему принципу: новый элемент кладется на вершину стека, то есть вставляется перед первым элементом списка, и при необходимости взять элемент из стека выбирается значение первого элемента, указатель стека смещается на следующий элемент, а "использованный" элемент удаляется.
Описание стека и операции с ним приведены в листинге 9.10.
Листинг 9.1. Стек, реализованный динамически
type TElem = char;
PNode = ^TNode;
TNode = record
Info: TElem;
Next: PNode;
end;
procedure InitStack(var s: PNode); // инициализация стека
begin
s:=Nil;
end;
function StackIsEmpty(s: PNode): Boolean; // проверка стека на пустоту
begin
StackIsEmpty:=s=Nil;
end;
function PopStack(var s: PNode): TElem; // взять из стека
var p:PNode;
begin
Result:=s^.Info;
p:=s; s:=s^.Next;
dispose(p);
end;
procedure PushStack(var s: PNode; x:TElem); // положить в стек
var p:PNode;
begin
new(p);
with p^ do begin
Info:=x;
Next:=s;
end;
s:=p;
end;
Следует обратить внимание на то, что функция PopStack — извлечения элемента из стека — внутри себя не делает проверки на пустоту стека. Дело в том, что эта функция должна вызываться только в том случае, когда заранее известно, что стек не пуст. В том случае, когда проверкой (функция StackIsEmpty) установлено, что стек пуст, решение о дальнейших действиях должно приниматься в вызывающем контексте.
Для иллюстрации вышесказанного решим следующую задачу: проверить правильность расстановки скобок в арифметическом выражении.
По правилам записи арифметических выражений первой должна закрываться последняя открывающая скобка, и число открывающих и закрывающих скобок должно совпадать. Будем считать, что в выражении используются три вида скобок: круглые, квадратные и фигурные.
Примечание
Не составит труда, изменив тип информационного поля на string, добавить еще несколько видов скобок, например, операторные скобки begin и end.
Ошибки, которые могут встретиться при расстановке скобок:
q несоответствие открывающей и закрывающей скобок, например: {a×[b+c)};
q непарные скобки, то есть открывающих скобок больше, чем закрывающих (или наоборот).
Поэтому алгоритм проверки должен быть следующим. Выражение просматривается посимвольно, и если встретилась любая открывающая скобка, то она помещается в стек. Если встретилась закрывающая скобка, то из стека берется последняя открывающая и проверяется, соответствует ли она закрывающей. Просмотр выражения заканчивается либо когда обнаружится ошибка, либо когда строка закончится. Если строка закончилась, то необходимо еще проверить стек — не остались ли там непарные открывающие скобки.
Функция BracketTest, приведенная в листинге 9.11, реализует этот алгоритм и возвращает значения:
q –1, если скобки расставлены правильно;
q 0, если не хватает закрывающих скобок;
q номер позиции в строке, на которой стоит "неправильная" скобка.
Листинг 9.11. Проверка скобок в арифметическом выражении
function BracketTest(a:string):integer;
var LenA, // длина строки
i : integer;
error: Boolean;
st : PNode;
begin
InitStack(st); // инициализация стека
LenA:=length(a); // длина строки-выражения
error:=false; // предполагаем, что ошибок нет
Result:=-1; // результат правильного выражения,
// а найдем ошибку — изменим
i:=0;
repeat
inc(i);
if a[i] in ['(','[','{'] then
PushStack(st,a[i]) // открывающую скобку
// безусловно кладем в стек
else begin
if a[i] in [')',']','}'] then begin
if not StackIsEmpty(st) then begin
// закрывающую скобку проверяем
// на соответствие открывающей
e:=PopStack(st);
case e of
'(': if a[i]<>')' then
begin Result:=i; error:=True; end;
'[': if a[i]<>']' then
begin Result:=i; error:=True; end;
'{': if a[i]<>'}' then
begin Result:=i; error:=True; end;
end;
end else begin // стек пуст: не было открывающей скобки
error:=True;
Result:=i;
end
end
end
until error or (i=LenA);
if not error then // дошли до конца выражения, не найдя ошибки
if not StackIsEmpty(st) then
// в стеке остались непарные открывающие
Result:=0; // скобки
end;
Читателю предлагается самостоятельно создать приложение, которое анализировало бы арифметическое выражение на предмет правильности расстановки скобок с помощью функции BracketTest. Значение, возвращаемое функцией, позволит отметить позицию ошибки, например, другим цветом.