Занесение элемента в стек.

Поскольку при решении задачи может использоваться несколько различных стеков, то процедура занесения в стек должна иметь два параметра: один из них задает нужный стек, а другой — заносимое в него значение.

Описание этой процедуры может иметь вид:

procedure ВСТЕК (var st: стек; новэл: типэлем); var q: связь; begin

{создание нового звена} new(q); qT.элем:=новэл;

{созданное звено сделать вершиной стека} qT.след:=st; st:=q

end

Выбор элемента из стека.

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

procedure ИЗСТЕКА (var st: стек; var а: типэлем); begin {а:= значение из вершины стека} а:=stT.элем;

{исключение первого звена из стека} st:=stT.след

end

Правда, из-за стремления к максимальному быстродействию этой процедуры она имеет два недостатка. Во-первых, исключаемое по этой процедуре звено стека не уничтожается, что приводит к менее эффективному использованию памяти машины. Во-вторых, здесь предполагается, что в программе стек используется корректно, т.е. что при обращении к этой процедуре указанный стек заведомо не пуст. В противном случае результат выполнения оператора процедуры оказывается неопределенным, а это может привести к неверным результатам. Таким образом, ответственность за корректное использование стеков мы возложили на программиста, который будет использовать это описание процедуры в своей программе. Для избежания возможности получения неверных результатов (особенно при решении ответственных задач) можно в самом описании процедуры предусмотреть контроль корректности использования заданного стека. Если этот стек оказался пустым, то можно, например, вывести на печать соответствующее сообщение и с помощью оператора перехода осуществить переход на конец программы. В этом случае требуется, чтобы перед заключительным символом end программы находился пустой оператор, помеченный заранее фиксированной меткой. Ради простоты сведем выполнение соответствующего оператора процедуры к печати диагностического сообщения:

procedure ИЗСТЕКАСКОНТР (var st: стек; var а: типэлем);

var q: связь;

begin {проверка, не пуст ли стек} if st=nil then begin writeln;

writeln('ПОПЫТКА_ВЫБОРА_ИЗ_ПУСТОГО_СТЕКА')

end

else

begin {выбор элемента из вершины} а:=stT.элем;

{запоминание ссылки на старую вершину} q:=st;

{исключение и уничтожение использованного звена} st:=stT.след; dispose(q) end

end

Здесь следует обратить внимание на достаточно типичную возможную ошибку: если не ввести в употребление вспомогательную ссылочную переменную q, а для уничтожения звена использовать оператор процедуры dispose(st), то это приведет к большим неприятностям (читателю предлагается проанализировать этот случай и выяснить, что произойдет в результате выполнения такой процедуры).

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

Пример 14.2. Во внешнем текстовом файле input задана строка литер, признаком конца которой является первая по порядку точка. В строке могут содержаться круглые, квадратные и фигурные скобки — как открывающие, так и закрывающие.

Требуется проверить баланс скобок в заданной строке.

Баланс скобок соблюдается, если выполнено каждое из следующих условий:

  • 1) для каждой открывающей скобки справа от нее есть соответствующая закрывающая скобка, и наоборот, для каждой закрывающей скобки слева от нее есть соответствующая открывающая скобка;
  • 2) соответствующие пары скобок (открывающие и закрывающие) разных типов правильно вложены друг в друга. Например, в строке [(x+y)*(x+2)/{3+abs(x)}+d]*e баланс скобок соблюдается, а в строке [{g+h[i]*((x-a)]d)) —нет.

В качестве результата на печать вывести соответствующее сообщение о соблюдении баланса, а также начало строки до первого по порядку нарушения баланса скобок (или всю строку, если баланс соблюдается).

Можно предложить следующую идею алгоритма решения поставленной задачи с использованием стека. Первоначально сформируем пустой стек. Затем будем последовательно просматривать литеры строки. Если очередная литера окажется одной из открывающих скобок, занесем ее в стек. Если очередная литера окажется закрывающей скобкой, выберем последнюю из занесенных в стек открывающих скобок и сравним эти скобки на соответствие друг другу. Если соответствие имеет место, то эффект должен быть такой же, как если бы этой пары скобок в строке вообще не было. Если эти две скобки не соответствуют друг другу (например, очередная обнаруженная в строке закрывающая скобка — круглая, а из вершины стека выбрана квадратная открывающая скобка), то не выполнено второе условие соблюдения баланса скобок. Если же в момент выбора из строки очередной закрывающей скобки стек оказался пуст (для этой закрывающей скобки слева от нее не нашлось соответствующей открывающей скобки) или по завершении просмотра строки стек оказался не пуст (для находящихся в стеке открывающих скобок справа от них не нашлось соответствующих закрывающих скобок), то не выполнено первое условие соблюдения баланса скобок.

Таким образом, баланс скобок соблюдается в том случае, когда для каждой очередной закрывающей скобки в строке из стека будет выбрана соответствующая открывающая скобка, стек не будет пуст к началу обработки очередной закрывающей скобки в строке и по окончании обработки последней из закрывающих скобок в строке стек будет пуст.

Обозначим через sym обрабатываемую литеру строки, а через b — логическую переменную, с помощью которой фиксируется факт соответствия (несоответствия) закрывающей скобки из строки с открывающей скобкой из вершины стека. С использованием этих обозначений запишем схему алгоритма, основанного на идее использования стека:

begin

{сформировать пустой стек);

{sym:=nepBan литера строки};

b:=true;

while (sym ) and b do

begin

{отпечатать литеру sym};

if {sym — открывающая скобка} then {занести sym в стек} else

if {sym — закрывающая скобка} then

begin if {стек пуст} or {скобка sym

не соответствует скобке из стека} then b:=false

end

{sym:=очередная литера строки}

end;

if not b or {стек не пуст} then

{печать 'БАЛАНСА_СКОБОК_НЕТ1}

else

{печать 1БАЛАНС_СКОБОК_ЕСТЬ'}

end.

Читателю рекомендуется проверить правильность предложенного алгоритма на данном уровне его детализации, применив этот алгоритм к различным ситуациям, которые могут иметь место в исходной строке. Для занесения литеры в стек и выбора ее из стека можно использовать описанные ранее процедуры. Поскольку в данной задаче проверка на пустоту стека делается в самой программе, а элементами являются скалярные значения (типа char), требующие мало места в памяти для их хранения, то целесообразно использовать более быстрый вариант процедуры выбора из стека (ИЗСТЕКА).

Дальнейшей детализации требует лишь проверка на соответствие закрывающей скобки, являющейся значением переменной sym, и открывающей скобки в вершине стека. Определенная трудность здесь состоит в том, что в ходе этой проверки приходится выполнять и такое действие, как удаление элемента из стека. Поэтому указанную проверку удобно реализовать с помощью логической функции (дадим ей имя СООТВ), которая в качестве побочного эффекта удаляет открывающую скобку из стека. В данной программе эту функцию можно не снабжать параметрами, поскольку она применяется к одному и тому же стеку, а выбираемый из стека элемент нигде больше не используется, так что выполнение происходит с помощью локальной переменной. Если учесть, что при обращении к этой функции значением sym может быть одна из трех литер ’)', ’]’, ’}’, то для определения значения функции удобен оператор варианта.

Таким образом, описание этой функции может иметь вид (стеку дадим имя s):

function СООТВ: boolean; var г: char; begin

ИЗСТЕКА(s,г); case sym of

')': COOTB:=r='(1;

']': COOTB:=r='[1;

'}': COOTB:=r='{1

end

end

Реализация на паскале остальных частей алгоритма достаточно очевидна, поэтому приведем полный текст программы на паскале.

{Пример 14.2. Костовский А.Н. Львов ГУ 9.5.09 г.

Проверка баланса скобок в задаваемой строке литер}

{Использование стека}

program балансскобок(input,output);

type

типэлем = char;

связь = Тзвеностека;

звеностека = record след: связь;

элем: типэлем end;

стек = связь;

var sym: char; s: стек; b: boolean;

{------------------------------------------------}

procedure встек (var st: стек; новэл: типэлем); var q: связь; begin

{создание нового звена} new(q); qT.элем:=новэл;

{созданное звено сделать вершиной стека} qT.след:=st; st:=q end {процедуры встек};

{------------------------------------------------}

procedure изстека (var st: стек; var а: типэлем); begin {а:= значение из вершины стека} а:=stT.элем;

{исключение первого звена из стека} st:=stT.след end {процедуры изстека};

{------------------------------------------------}

function соотв: boolean; var г: char; begin изстека(s,г); case sym of

')': соотв:=r='(';

']': соотв:=r='[';

'}': соотв:=r='{'

end

end {функции соотв);

{------------------------------------------------}

{раздел операторов программы} begin {формирование пустого стека} s:=nil;

{зуш:=первая литера строки; b:=true} read(sym); b:=true; while (sym .') and b do begin

{печать введенной литеры} write(sym);

if {sym — открывающая скобка} sym in ['(' , '[' , '{'] then {занести sym в стек} встек(s,sym) else

if {sym — закрывающая скобка} sym in [')' , ']' , '}'] then

begin

if {стек пуст или скобки не соответствуют}

(s=nil) or (not соотв) then b:=false

end;

{ввести очередную литеру} read(sym)

end {обработки литер строк} writeln;

if {было несоответствие скобок или стек не пуст}

not b or (s?mil)

then writeln('БАЛАНСА_СКОБОК_НЕТ') else writeln('БАЛАНС_СКОБОК_ЕСТЬ') end. {конец программы}

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >