Динамическая реализация стека
Стеки Понятие стекачасто встречается в повседневной жизни, например, грузовой отсек транспортного самолета, куда заезжают автомобили один за другим, а по приземлении первым (причем задом!) выезжает тот автомобиль, который заехал последним. Аналогичные примеры: тупиковый железнодорожный разъезд для сортировки вагонов, винтовочный патронный магазин. Последний пример иллюстрирует тот факт, что стек иногда называют магазином. Таким образом, стек — это структура, работа с которой происходит по принципу 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. Значение, возвращаемое функцией, позволит отметить позицию ошибки, например, другим цветом.
Популярное: Почему стероиды повышают давление?: Основных причин три... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (734)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |