Отправляет email-рассылки с помощью сервиса Sendsay

Все о Паскале

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "RFpro.ru: Программирование на языке Pascal" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Апрель 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Gescheit

Статистика

1.401 подписчиков
-3 за неделю
←   Все выпуски   →

Все о Паскале


Информационный Канал Subscribe.Ru
Лучшие статьи о паскале!
 Подисчиков:  7
Выпуск номер: 4
Сегодня в выпуске:
1. ) СТЕКИ

1. ) СТЕКИ


Организация стека в определенном смысле противоположна организации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" (такой метод доступа иногда называют методом LIFO). Представим себе стопку тарелок. Нижняя тарел- ка из этой стопки будет использована последней, а верхняя тарелка (которая была установлена в стопку последней) будет использована первой. Стеки широко используются в системном программном обеспечении, включая компиляторы и интерпретаторы.
Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "posh" (затолкнуть), которая помещает элемент в вершину стека, и "pop" (вытолкнуть), которая выбирает из вершины стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно выделить область памяти, используя средство динамического распределения памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет потерян, если его не сохранить гденибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.
const
MAX = 100;
var
stack: array [1..100] of integer;
tos:integer; {помещение объекта в стек}
procedure Push (i:integer);
begin
if tos>=MAX then WriteLn('Стэк пуст')else
begin
stack[tos]:=i;
tos:=tos+1;
end;
end; {конец процедуры помещения объекта в стек}
{ выборка объекта из стека }
function Pop:integer;
begin
tos:=tos-1;
if tos<1 then
begin
WriteLn('Стэк переполнен');
tos:=tos+1;
Pop:=0;
end
else Pop := stack[tos];
end;{конец функции выборки объекта из стека}

Переменная "tos" содержит значение индекса для следующего помещаемого в стек элемента. При реализации этих процедур никогда нельзя забывать о проверке ситуаций переполнения стека и выборки из пустого стека. В приведенных процедурах нулевое значение указателя "tos" означает, что стек пуст, а значение этого указателя, равное или превышающее адрес последней ячейки памяти, где содержится стек, означает заполнение стека. Рис.7 иллюстрирует работу стека.

Операция                   Содержимое стека
Push(A)                    A
Push(B)                    B A
Push(C)                    C B A
Pop, выбирается С          В А
Push(F)                    F B A
Pop, выбирается F          B A
Pop, выбирается В          А
Рор, выбирается А           пусто
              Рис.7. Работа стека.

Хорошим примером применения стека является калькулятор, который может выполнять четыре действия. Большинство калькуляторов используют стандартную форму выражений, которая носит название инфиксной формы. В общем виде ее можно представить в виде "операнд-оператор-операнд". Например, для прибавления 100 к 200 вы должны ввести число 100, набрать символ сложения, ввести число 200 и нажать клавишу со знаком равенства. Однако, некоторые каль- куляторы применяют другую форму выражений, получившую название постфиксной формы. В этом случае оба операнда вводятся перед вводом оператора. Например, для добавления 100 к 200 при использовании постфиксной формы сначала вводится число 100, затем вводится число 200 и после этого нажимается клавиша со знаком плюс. Введенные операнды помещаются в стек. При вводе оператора из стека выбираются два операнда и результат помещается в стек. При использовании постфиксной формы очень сложные выражения могут легко вычисляться на калькуляторе.
Ниже показана программа для такого калькулятора.
{калькулятор с четырьмя операциями, иллюстрирующий работу}
program four_function_calc;
const
MAX = 100;
var
stack: array [1..100] of integer;
tos:integer;{указатель вершины стека}
a, b:integer;
s:string[80];
{поместить объект в стек}
procedure Push(i:integer);
begin
if tos >= MAX then Writeln('Стек полон') else
begin
stack[tos] :=1;
tos := tos+1;
end;
end;{Push}
{выборка объекта из стека}
function Pop:integer;
begin
tos := tos-1;
if tos < 1 then
begin
Writeln('Стек переполнен')
tos := tos+1;
Pop := 0;
end;
else Pop := stack[tos];
end;{Pop}
begin{калькулятор}
tos := 1;
Writeln('For Function Calculator');
repeat
Write(': '); { вывод приглашения }
Readln(s);
Val(s, a, b) { преобразование строки символов в целое число }
{ считается, что при успешном преобразовании пользователь ввел число, а в противном случае пользователь ввел оператор}
if (b=0) and ((Length(s)>1) or (s[1]<>'-')) then
Push(a);
else
case s[1] of
'+' begin
a := Pop;
b := Pop;
Writeln(a+b);
Push(a+b);
end;
'-' begin
a := Pop;
b := Pop;
Writeln(b+a);
Push(b+a);
end;
'*' begin
a := Pop;
b := Pop;
Writeln(a*b);
Push(a*b);
end;
'/' begin
a := Pop;
b := Pop;
if a=0 then Writeln('делим на ноль') else
begin
Writeln(b div a);
Push(b div a);
end;
end;
'.' begin
a := Pop
Writeln(a);
Push(a);
end;
end;
until UpCase(s[1])='G';
end.

Для того, чтобы посмотреть, что находится в вершине стека, достаточно ввести точку. Хотя данная программа выполняет арифметические действия только с целыми числами, ее легко можно приспособить для чисел с плавающей запятой, изменяя тип данных стека и преобразуя оператор "div" в оператор деления для чисел с плавающей запятой (наклонная черта).

Все о паскале, множество доков, исходники, 15(!) компиляторов и многое другое

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное