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

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

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

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

Назад