Стэк
Стэк - это на самом деле такая структура, которую все умные люди
реализовывают при помощи связанных списков. Нам же предстоит написать
программу, которая работает с прообразом стека, реализованного не
списками, а массивом и целочисленной переменной.
Главной особенностью структуры под названием "стэк" является то, что
работа с этой структурой осуществляется при помощи пяти стандартных
стековых функций, которые называются push(), pop(), top(), empty() и
makefree(). Функция push() помещает в вершину стэка значение, которое мы
указываем в скобках. Функция pop() совершает обратное действие, то есть
удаляет из стэка то значение, которое находится в вершине. Функция top()
никак не изменяет стэк, а только возвращает копию того значения, которое
находится в вершине стэка. Empty() возвращает ложь, то есть 0, если стэк
не пустой, и истину (то есть не ноль), если стэк пуст, естественно, никак
не изменяя сам стэк. Процедура makefree() очищает стэк, делая его пустым,
и освобождает занятую им память.
При нормальной реализации стэка, то есть при реализации списками, все
эти функции вызывались бы с одним параметром, коим являлся бы указатель
на голову связанного списка (не считая push(), у которой было бы два
параметра - указатель на голову и значение, которое нужно занести).
Очевидно, что голова этого списка и была бы вершиной стэка. В нашем случае
всё сложнее. Но об этом чуть позже.
Сама суть требуемой от нас программы заключается в следующем: пользователь
вводит с клавиатуры строку, содержащую символы +, -, *, /, (, ), [, ], {, }
и маленькие буквы латинского алфавита. Эта введённая строка - выражение,
значение которого в результате нужно будет найти.
Первое, что делает программа - создаёт вторую строку (назовём первую
строку ВХОДНОЙ, а вторую - ВЫХОДНОЙ). Эта выходная строка должна содержать
так называемую "польскую запись" того же самого выражения, которое
находится во входной строке. О том, что из себя представляет "польская
запись", поговорим чуть позже. Для перевода входной строки в выходную
нам как раз и понадобиться стэк. Это должен быть стэк значений типа char.
Второе, что делает программа - считает значение выражения, хранящегося
в выходной строке. Для этого тоже нужно будет использовать стэк, но на этот
раз уже другой - с числовыми значениями. В нашем случае это должен быть
стэк значений типа float. Кроме того для подсчёта выражения нам понадобятся
два массива - в одном будут храниться имена всех переменных, имеющихся в
выражении, во втором - их значения, которые пользователь будет вводить в
тот момент, когда программа будет считать значение выражения.
Итого нам в программе понадобиться: массив для хранения входной строки,
массив для хранения символьного стэка, массив для хранения выходной строки,
массив для хранения вещественного стэка, массив для хранения названий
переменных и массив для хранения значений переменных. То есть 4 массива
типа char и 2 массива типа float.
Теперь поговорим о том, как же при помощи одного массива и одной
целочисленной переменной можно реализовать один стэк.
Самый простой способ - использовать в качестве стека статический массив
размером 256 символов, то есть описать в программе переменную Stack[255];
чуть более сложный, но и более правильный - создать динамический массив,
размер которого определится в зависимости от длины введённой пользователем
строки. Целочисленная переменная, которая понадобится для того, чтобы
отмечать, где на данный момент у стека находится вершина, должна быть
в любом случае определена типом short int, принимающим значения от 0 до 255.
Первое, что сделаем - реализуем стандартные функции работы со стэком.
Начнём с самой простой - empty(). Она, напомню, определяет, пустой ли стэк.
Так как пустым является тот стэк, вершина которого находится на нулевом
символе массива, нам достаточно знать значение целочисленной переменной,
в которой хранится позиция вершины. Назовём эту переменную position. Она
должна быть определена во внешней части программы, то есть, по идее, в
void main(). Вот как должны выглядеть инициализация переменной и вызов
функции empty():
void main()
{
short int position;
if ( empty(position) ) { ... }
}
А функция empty() должна возвращать 0, если переменная position неравна
нулю, и наоборот. Поэтому вся её реализация выглядит следующим образом:
int empty(short int position)
{
int tmp;
if (position!=0) tmp=0;
else tmp=1;
return tmp;
}
Хотя я написал бы проще - вот так:
int empty(short int position)
{
return !position;
}
Результат будет практически тот же.
Теперь процедура makefree(). Всё, что она должна сделать в нашем случае -
изменить значение переменной position на 0. Но для того, чтобы изменить
значение переменной в процедуре и сохранить его после выхода из неё, нам
придётся передать переменную не по значению, как мы делали в empty(), а
по указателю. Для этого нам придётся послать в makefree() адрес переменной
position. То есть вызов из void main() должен быть таким:
void main()
{
short int position;
makefree(&position);
}
А сама процедура должна быть такой:
void makefree(short int *adr_pos)
{
(*adr_pos)=0;
}
В процедуру приходит адрес переменной position, то есть фактически
adr_pos=&position. Ну а указатель на адрес допустит нас к самому значению,
то есть, фактически, (*adr_pos)=position. Поэтому чтобы изменить значение
переменной position в процедуре makefree(), мы и должны писать (*adr_pos)=0.
При реализации функции top() нам уже придётся отсылать подпрограмме не
только значение переменной position, но и указатель на массив, в котором
хранится стэк. Этот массив, как и переменная position, должен быть описан
в void main(). В частности, первый стэк - символьный, можно описать так:
void main()
{
char Stack[255];
short int position;
}
Как уже говорилось, это более простой способ, когда используется
статический массив из 256 символов. Адресом первого элемента массива
будет &(Stack[0]), что аналогично просто записи Stack. Таким образом
вызов функции top() и запись возвращаемого ею значению в какую-то
переменную будет выглядеть примерно так:
void main()
{
char Stack[255];
short int position;
char symbol;
symbol=top(Stack,position);
}
А сама функция top() описывается примерно так:
char top(char *Stack; short int position)
{
char tmp;
if (position>0)
tmp=Stack[position-1];
else tmp='\0';
return tmp;
}
Понятно, что если у нас стэк пустой, то position равен 0, а если в стэке,
например, есть одно значение, то position равен 1, а единственное значение
хранится в нулевой ячейке массива, то есть в Stack[position-1]. Если стэк
пустой, функция будет возвращать символ '\0', что нам пригодится при
определении приоритета операции, лежащей в вершине стэка (об этом будет
рассказано дальше).
Теперь рассмотрим функцию push(). В неё нам придётся отсылать целых три
параметра - указатель на массив, адрес переменной position и значение,
которое мы хотим поместить в стэк. Переменная position, как и в случае
процедуры makefree(), должна отсылаться по указателю, а не по значению,
так как в результате действия функции push() её значение будет изменено.
Вызов выглядит примерно так:
void main()
{
char Stack[255];
short int position;
char symbol='+';
push(Stack,&position,symbol);
}
Обратите внимание, что перед переменной position мы пишем значок адреса
(амперсант), а перед переменной symbol нет, потому что первую переменную
мы будем изменять, а вторую нет. А вот сама функция push():
void push_char(char *Stack, int *adr_pos, char symbol)
{
Stack[*adr_pos]=symbol;
(*adr_pos)++;
Stack[*adr_pos]='\0';
}
Первая строчка запишет в вершину значение symbol, вторая передвинет
позицию вершины вперёд. Третья строчка необязательна, её можно и не писать,
но если её написать, то при отладке программы в Watch значение массива
Stack будет отображаться значительно красивее и понятнее.
Оставшаяся функция - pop(). Она, как уже говорилось, совершает действие,
обратное push(). В то же время она, как и top(), возвращает значение
вершины стэка. Внешне её вызов выглядит так же, как и у top(), но только
переменную position мы отправляем по указателю:
void main()
{
char Stack[255];
short int position;
char symbol;
symbol=pop(Stack,&position);
}
А сама функция top() описывается примерно так:
char pop(char *Stack; short int *adr_pos)
{
char tmp;
if ((*adr_pos)>0)
{
(*adr_pos)--;
tmp=Stack[*adr_pos];
Stack[*adr_pos]='\0';
}
else tmp='\0';
return(tmp);
}
Если у нас стэк не пустой, то есть (*adr_pos)>0, то мы, во-первых,
уменьшаем на единицу позицию вершины, и оказываемся на верхнем элементе
стэка, во-вторых, записываем значение этого верхнего элемента во временную
переменную tmp, в-третьих, очищаем позицию, то есть удаляем из стэка этот
элемент. Если стэк пустой, возвращаем '\0'.
Продолжение следует...
