Примеры решения задач.

Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Program MordovskihK;

Type

EXST = ^ST;

ST = record

Data : char;

Next : EXST;

End;

Var

Stack : EXST; {Текущая переменная}

i : integer;

f : text;

Stroka : string;

c : char;

Procedure writeStack(Var u : EXST; Simvol : char);

Var

x : EXST;

Begin

new(x);

x^.Data := Simvol;

x^.Next := u;

u := x;

End;

Procedure Print(Var u : EXST);

Begin

while u <> Nil

Begin

write (u^.Data);

u := u^.Next;

End;

End;

Begin

Stack := Nil;

Assign(f, 'c:\autoexec.bat');

Reset(f);

while Not Eof(f) do

Begin

readln (f, Stroka);

For i := 1 to Length(Stroka) do

writeStack(Stack, Stroka[i]);

End;

close(f);

Print(Stack);

End.

Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов.

Для решения задачи определим стек, элементами которого являются символы:

Type

EXST = ^ST;

ST = record

Data : char;

Next : EXST;

End;

Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из закрывающихся скобок ({, (, [ ), занесем ее в стек. При обнаружении закрывающейся скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.

Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:

while (i<>Length(a)) and f do ...

Осталось выяснить, как определить, соответствует ли очередная закрывающаяся скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):

{ } 123–125

[ ] 91–93

( ) 40–41

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

if (Ord(a[i]–Ord(stack^.Data))<=2

then

. . .

А теперь просмотрите полный текст программы:

Program Skobki;

Type

EXST = ^ST;

ST = record

Data : char;

Next : EXST;

end;

Var

a : string;

f : boolean;

i : integer;

Procedure writeStack(Var x1 : EXST; c : integer);

Var

u : EXST;

Begin

new(u); {создание нового элемента стека}

u^,Data := c;

u^.Next := x1;

x1 := u; {созданный элемент определить как вершину стека}

End;

Procedure DelStack(Var x1 : EXST); {процедура удаления верхнего элемента стека}

Var

u : EXST;

Begin

u := x1;

x1 := x1^.Next;

dispose(u);

End.

Procedure Solve(a : string); {процедура правильности расстановки скобок}

Var

Stack : EXST;

Begin

Stack := Nil;

i := 1;

while (i<=Length(a)) and f do

begin

if (a[i]='(') or (a[i]='{') or (a[i]='[')

then

writeStack(Stack , a[i])

else

if (a[i]=')') or (a[i]='}') or (a[i]=']')

then

if Ord(Stack ^.Data)–Ord(a[i])<=2

then

DelStack(Stack)

else

f := False;

Inc(i);

end;

End.

Begin

writeln('Введите строку');

readln(a);

f := True;

if a<>' '

then

begin

Solve(a);

if f

then

writeln('Все скобки расставлены верно')

else

writeln('Скобка ',a[i-1],' закрыта преждевременно');

end

else

writeln('Строка пуста');

readln;

End.

Задание. Объясните учителю алгоритмы решения предложенных задач.