Значение стека как структуры данных в программировании не исчерпывается лишь стеком отложенных заданий. В этом разделе мы решим с помощью стека задачу о вычислении значения арифметического выражения, заданного своей постфиксной (“польской”) записью. Пусть, например, требуется вычислить значение выражения ((6+7)*3)-(8*(9-5)), тогда его постфиксная запись будет иметь вид 67+3*895-*-. Алгоритм преобразования инфиксной (обычной) записи в постфиксную известен, он также использует стек, но здесь мы не будем его рассматривать. Поскольку числа в выражении могут состоять не только из одной цифры, мы примем постфиксную запись в виде #6#7+#3*#8#9#5-*- , где символ # означает начало очередного числа. Алгоритм решения этой задачи довольно прост и широко известен: будем брать из постфиксной записи по одному элементу (числу или знаку операции): если взято число, просто поместим его в стек, если взят знак операции, то возьмем из стека два числа, выполним над ними эту операцию и поместим результат в стек. Когда все элементы постфиксной записи обработаны, в стеке окажется значение выражения.
Type T_Num_Stack = Array[1..100] Of LongInt;
{В этой программе будем хранить стек в массиве}
Function Value_By_Postfix(Postfix:String):LongInt;
{Функция вычисляет значение выражения, заданного постфиксной записью.}
Function Get_From_Postfix
(Var Postfix:String; Var Op:Char; Var Val:LongInt):Boolean;
{Функция "забирает" из постфиксной записи очередной элемент (число или знак операции) и возвращает True, если это число, и False, если это знак операции. Отработанные символы удаляются из постфиксной записи, так что очередной символ всегда Postfix[1]}
Begin
If Postfix[1]='#' Then Begin {признак числа}
Get_From_Postfix:=True;
Delete(Postfix,1,1);
Val:=0;
While Postfix[1] In ['0'..'9'] Do Begin
{формируем число из цифр по схеме Горнера}
Val:=10*Val+Ord(Postfix[1])-Ord('0');
Delete(Postfix,1,1);
End;
End
Else Begin
Get_From_Postfix:=False;
Op:=Postfix[1];
Delete(Postfix,1,1);
End;
End;
Function Execute(op:Char;x1,x2:LongInt):LongInt;
{Функция выполняет арифметическую операцию, заданную знаком op}
Begin
Case op Of
'+': Execute:=x1+x2;
'-': Execute:=x1-x2;
'*': Execute:=x1*x2;
End;
End;
Var
Stack : T_Num_Stack; {стек для чисел}
Top : Byte; {номер первого элемента стека}
Op : Char;
x1,x2 : LongInt;
Number : Boolean;
Begin
Top:=0; {стек сделали пустым}
While True Do Begin
{условие окончания цикла будет проверено в теле цикла}
Number:=Get_From_Postfix(Postfix,Op,x1);
{взяли из постфиксной записи число или операцию}
If Number Then Begin {взяли число - помещаем его в стек}
Inc(Top);
Stack[Top]:=x1;
End
Else Begin {взяли операцию - извлекаем из стека два числа (обратите внимание, в каком порядке), выполняем над ними операцию и результат помещаем в стек}
x2:=Stack[Top];
Dec(Top);
x1:=Stack[Top];
Dec(Top);
Inc(Top);
Stack[Top]:=Execute(Op,x1,x2);
End;
If Postfix='' Then Begin {постфиксная запись пуста, теперь в стеке находится одно число, которое и есть значение выражения}
Value_By_Postfix:=Stack[Top];
Exit;
End;
End;
End;
Const Postfix : String='#6#7+#3*#8#9#5-*-';
Begin
WriteLn(Postfix,'=',Value_By_Postfix(PostFix));
End.
Еще раз внимательно посмотрим, как организовано хранение стека в массиве. Когда мы держали стек в списке, мы по-настоящему добавляли туда элементы и по настоящему удаляли элементы оттуда. Если стек размещен в массиве, то, конечно, этого делать не надо, достаточно лишь иметь одну дополнительную переменную, равную номеру “верхнего” элемента стека, в данной программе это переменная Top. Если стек пуст, то Top=0; чтобы добавить число в стек, достаточно увеличить Top на единицу и записать число в элемент с индексом Top. Чтобы удалить число из стека, достаточно просто уменьшить Top на единицу.
Еще одна структура данных, также уже известная нам, которая часто используется при решении различных задач, - это очередь, или FIFO-структура. Очередь отличается от стека тем, что элемент, попавший туда первым, и извлекается оттуда первым, а не последним, как в стеке. Очередь так же, как и стек, можно хранить и в списке, и в массиве. Реализация очереди в списке не представляет большой сложности, а вот хранение ее в массиве - не вполне тривиальная задача. Рассмотрим ее более подробно. Элементы очереди добавляются в “хвост” массива, а удаляются из “головы”, поэтому очередь по мере ее использования “ползет” по массиву слева направо и, если размер массива не очень велик, может достигнуть края массива, и тогда добавление нового элемента станет невозможным. Использование очень больших массивов, заведомо превышающих любые потребности очереди, неэкономно, а часто и невозможно. Гораздо лучше использовать “закольцованный” массив, в котором за последним элементом массива непосредственно следует первый его элемент. В этом случае очередь, достигнув конца массива, “переползет” в его начало, которое к этому моменту будет уже свободно. Пусть массив Q содержит N элементов, пронумерованных от 0 до N-1. В переменных Top и Len будем хранить номер “верхнего” элемента очереди и длину (количество элементов) очереди. В начальный момент очередь пуста иTop=Len=0. Чтобы добавить элемент в очередь, нужно записать добавляемый элемент в элемент массива Q[(Top+Len)Mod N],а затем увеличить Len на единицу, значение Top при этом не изменяется. Чтобы удалить элемент из очереди (всегда удаляется только первый элемент), нужно уменьшить Len на единицу и вычислить новое значение Top по формуле Top=(Top+1) Mod N. Решим, используя очереди, такую задачу: напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3 и 5. Будем хранить очереди в массивах. Один из алгоритмов решения этой задачи таков: организуем три очереди Q2,Q3 и Q5. Выведем число 1 и добавим в очередь Q2 число 2, в Q3 число 3 и в Q5 число 5. Затем в цикле от 2 до n:
- найдем элемент m, наименьший из первых элементов очередей;
- удалим этот элемент из всех очередей, где он является первым;
- выведем этот элемент и добавим в Q2 число 2m, в Q3 число 3m и в Q5 число 5m.
Const n=240;
Type Queue = Object {объект - очередь}
Body : Array[0..n-1] Of LongInt;
Top : 0..n-1;
Len : 0..n;
Procedure Clear;
Procedure Add(x:LongInt);
Procedure Get(Var x : LongInt);
Function Upper : LongInt;
End;
Procedure Queue.Clear; {процедура делает очередь пустой}
Begin
Len:=0;
Top:=0;
End;
Procedure Queue.Add(x:LongInt); {процедура добавляет элемент в очередь}
Begin
Body[(Top+Len)Mod n]:=x;
Inc(Len);
End;
Procedure Queue.Get(Var x : LongInt);
{процедура забирает элемент из очереди}
Begin
x:=Body[Top];
Top:=(Top+1) Mod n;
Dec(Len);
End;
Function Queue.Upper:LongInt;
{функция возвращает первый элемент очереди, но не удаляет его}
Begin
Upper:=Body[Top];
End;
Procedure Add_And_Print(t:LongInt; Var Q2,Q3,Q5:Queue);
Begin
Write(t:8);
Q2.Add(2*t);
Q3.Add(3*t);
Q5.Add(5*t);
End;
Var
Q2,Q3,Q5 : Queue;
m,x : LongInt;
k : Word;
Begin
Q2.Clear; {делаем все очереди пустыми}
Q3.Clear;
Q5.Clear;
Add_And_Print(1,Q2,Q3,Q5);
{выводим 1 и добавляем в очереди 2,3,5}
k:=1;
While k<n Do Begin
m:=Q2.Upper; {находим наименьший из первых элементов}
If m>Q3.Upper Then m:=Q3.Upper;
If m>Q5.Upper Then m:=Q5.Upper;
Add_And_Print(m,Q2,Q3,Q5);
{выводим его и добавляем новые элементы в очереди}
If m=Q2.Upper Then Q2.Get(x);
{удаляем первый элемент, если он равен m}
If m=Q3.Upper Then Q3.Get(x);
If m=Q5.Upper Then Q5.Get(x);
Inc(k);
End;
WriteLn;
End.