КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Примеры решения задач. Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.Пример 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;
|