Примеры задач
Стеки и очереди
В текстовом файле записана без ошибок формула вида: цифра или S (формула, формула) или Р(формула, формула), где S(a,b)=(a+b) mod 10, P(a,b)=(a*b) mod 10. Вычислить значение данной формулы (например, Р(6, S(8, 4)) = 2). Методика решения
Решение данной задачи происходит следующим образом. Организуем последовательную обработку символов формулы. Если символ является цифрой или буквой “P” или “S”, то помещаем его в стек, иначе, если сивол равен закрывающей скобке, то возьмём из стека три элемента (последний из них будет ‘P’ или ‘S’) и выполним над ними соответствующую операцию. Результат снова поместим в стек. Символы ‘(’ и ‘,’ в формуле игнорируются. В данной программе мы используем стек, а не очередь, так как элементы списка необходимо обрабатывать в обратном порядке, начиная с конца. Для начала в разделе типов описываем ссылку на звено ss=^zveno, а затем само звено в виде записи, состоящей из информационной inf:byte и ссылочной next:ss частей. В разделе констант описываем множество символов m:set of char=[‘0’..’9’,’S’,’P’]
Для реализации данной программы понадобятся следующие переменные: S – ссылка на вершину стека(тип ss); Op – операция ‘S’ или ‘P’(тип char); A,b,c – символы (char); A1,b1 - символы, переведённые в цифры (тип byte); Rez1(тип byte), rez (тип string) – результат в виде числа и в виде строки; Form – формула (string); I – вспомогательная переменная для реализации цикла (integer); F – файловая переменная (f:text). Описываем их в разделе переменных.
В данной программе вставку и извлечение элементов из стека рациональней оформить в виде процедур, так как в алгоритме они будут встречаться несколько раз.
Процедура добавления звена в стек
Эта процедура будет иметь два входных параметра: st – ссылка на вершину стека и x – элемент добавляемый в стек. Вставка элемента в стек выполняется в конце. Создаём новое звено New(g), его информационной части присваиваем x.
![]()
Ссылочную часть нового звена направляем на вершину стека. G^.next:=st;
![]()
Делаем н6овое звено вершиной стека, то есть переводим на него указатель st. St:=g;
![]()
Процедура извлечения элемента из стека
Эта процедура имеет два параметра входной: st – ссылка на вершину стека, и выходной: x – элемент, извлекаемый из стека. Извлечение элемента из стека происходит с конца. Проверяем, является ли стек пустым. If st=nil then…
В этом случае выводим соответствующее сообщение. Если же стек не пуст, то удаляем его вершину, предварительно присвоив параметру х значение информационной части удаляемого элемента. Следующее звено делаем вершиной стека. Графически это выглядит следующим образом:
G:=st;
![]()
St:=st^.next;
![]()
Теперь звено g можно удалить dispose(g);
Основная часть программы
В основной части программы делаем начальную установку стека. S:=nil;
Связываем файловую переменную с файлом с помощью процедуры assign. Открываем файл для чтения и считываем из него формулу. Затем в цикле от 1 до длинны строки form последовательно перебираем символы формулы. For i:=1 to length(form) do…
Если символ принадлежит множеству m, If form[i] in m then…
то добавляем его в стек с помощью процедуры вставки.
Иначе, если символ равен ‘)’, то последовательно извлекаем из стека символы b, a и op (переменная ор будет равна либо ‘S’, либо ‘P’). Символы а и b переводим в цифры а1 и b1 с помощью процедуры val. Val(a,a1,n); val(b,b1,n);
Теперь подсчитываем результат: если op=’S’, то rez1:=(a1+b1) mod 10, если op=’Р’, то rez1:=(a1*b1) mod 10. Результат rez1 переводим в строку rez с помощью процедуры str Str(rez1,rez);
и помещаем первый символ этой строки в стек.
Vst(s,rez1);
После обработки всех символов формулы полученный результат извлекаем из стека и выводим на экран.
uses crt; const m: set of char=['0'..'9','S','P']; type ss=^zveno; {Описание ссылки на звено} zveno=record {Описание звена} inf:char; {информационная часть} next:ss {ссылочная часть} end; var s:ss; op,a,b,c:char; a1,b1,rez1:byte; n,i:integer; form,rez:string[20]; f:text;
procedure vst(var st:ss; x:char); {Процедура вставки звена в стек} var g:ss; begin new(g); g^.inf:=x; g^.next:=st; st:=g end;
procedure izst(var st:ss; var x:char); {Процедура извлечения элемента из стека} var g:ss; begin if st=nil then writeln('stec pust') else begin g:=st; st:=st^.next; x:=g^.inf; dispose(g); end; end;
begin clrscr; s:=nil; assign(f,'file.txt'); reset(f); read(f,form); {Считываем формулу из файла} for i:=1 to length(form) do begin if form[i] in m then vst(s,form[i]) else if form[i]=')' then begin izst(s,b); izst(s,a); izst(s,op); val(a,a1,n); val(b,b1,n); case op of {Выполняем операцию в зависимости от значения переменной ор} 'S':rez1:=(a1+b1) mod 10; 'P':rez1:=(a1*b1) mod 10; end; str(rez1,rez); vst(s,rez[1]); {Помещаем результат операции в стек} end; end; izst(s,rez[1]); writeln(form,' = ',rez[1]); close(f); readkey; end.