Примеры задач

Стеки и очереди


В текстовом файле записана без ошибок формула вида: цифра или 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.

Запустить программу










Назад