Лекции (1171139), страница 19
Текст из файла (страница 19)
в ячейку с индексом N - 1. Элементыстека занимают непрерывный отрезок массива, начиная с ячейки, индекс которойхранится в указателе стека, и заканчивая последней ячейкой массива. В этом вариантестек растет в сторону уменьшения индексов. Если стек пуст, то указатель стека содержитзначение N (которое на единицу больше, чем индекс последней ячейки массива).Пример реализации стека: реализация включает два файла: "streal.h", в котором описывается интерфейсисполнителя "Стек", и "streal.cpp", реализующий функции работы со стеком. Слово real обозначаетвещественное число. Используется вариант реализации стека на базе массива, описанный ранее: стек растетв сторону увеличения индексов массива.
Пространство под массив элементов стека захватывается вдинамической памяти в момент инициализации стека. Функции инициализации st_init передается размермассива, т.е. максимально возможное число элементов в стеке. Для завершения работы стека нужно вызватьфункцию st_terminate, которая освобождает захваченную в st_init память.
Ниже приведено содержимоефайла "streal.h", описывающего интерфейс стека.// Файл "streal.h"// Стек вещественных чисел, интерфейс//#ifndef ST_REAL_H#define ST_REAL_H// Прототипы функций, реализующих предписания стека:void st_init(int maxSize); // Начать работу (вх: цел//макс. размер стека)void st_terminate();// Закончить работуvoid st_push(double x); // Добавить эл-т (вх: вещ x)double st_pop();// Взять элемент: вещdouble st_top();// Вершина стека: вещint st_size();// Текущий размер стека: цел68bool st_empty();int st_maxSize();bool st_freeSpace();void st_clear();double st_elementAt(int// Стек пуст? : лог// Макс.
размер стека: цел// Есть свободное место? : лог// Удалить все элементыi); // Элемент стека на//глубине (вх: i): вещ#endif// Конец файла "streal.h"Отметим, что директивы условной трансляции#ifndef ST_REAL_H#define ST_REAL_H. . .#endifиспользуются для предотвращения повторного включения h-файла: при первомвключении файла определяется переменная препроцессора ST_REAL_H, а директива"#ifndef ST_REAL_H" подключает текст, только если эта переменная не определена.Такой трюк используется практически во всех h-файлах.
Нужен он потому, что одни hфайлы могут подключать другие, и без этого механизма избежать повторного включенияодного и того же файла трудно. Файл "streal.cpp" описывает общие статическиепеременные, над которыми работают функции, соответствующие предписаниям стека, иреализует эти функции.// Файл "streal.cpp"// Стек вещественных чисел, реализация//#include <stdlib.h>#include <assert.h>#include "streal.h" // Подключить описания функций стека// Общие переменные для функций, реализующих// предписания стека:static double *elements = 0; // Указатель на массив эл-тов//стека в дин. памятиstatic int max_size = 0;// Размер массиваstatic int sp = (-1);// Индекс вершины стека// Предписания стека:void st_init(int maxSize) { // Начать работу (вх://макс.
размер стека)assert(elements == 0);max_size = maxSize;elements = (double *) malloc(max_size * sizeof(double));sp = (-1);}void st_terminate() { // Закончить работуif (elements != 0) {free(elements);}}void st_push(double x) {assert(elements != 0 &&sp < max_size-1// Добавить эл-т (вх: вещ x)// утв://стек начал работу и//есть своб. место69);++sp;elements[sp] = x;}double st_pop() { // Взять элемент: вещassert(sp >= 0); // утв: стек не пуст--sp;// элемент удаляется из стекаreturn elements[sp + 1];}double st_top() { // Вершина стека: вещassert(sp >= 0); // утв: стек не пустreturn elements[sp];}int st_size() { // Текущий размер стека: целreturn (sp + 1);}bool st_empty() { // Стек пуст? : логreturn (sp < 0);}int st_maxSize() { // Макс. размер стека: целreturn max_size;}bool st_freeSpace() { // Есть своб.
место? : логreturn (sp < max_size - 1);}void st_clear() { // Удалить все элементыsp = (-1);}double st_elementAt(int i) { ////assert(elements != 0 &&0 <= i && i < st_size());return elements[sp - i];}// Конец файла "streal.cpp"Элемент стека наглубине (вх: i): вещ// утв:// стек начал работу и// 0 <= i < размер стекаВ реализации стека неоднократно использовалась функция assert. Фактическим аргументом функцииявляется логическое выражение. Если оно истинно, то ничего не происходит; если ложно, то программазавершается аварийно, выдавая диагностику ошибки.Стековый калькулятор и обратная польская запись формулы.В 1920 г. польский математик Ян Лукашевич предложил способ записиарифметических формул, не использующий скобок.
В привычной нам записи знакоперации записывается между аргументами, например, сумма чисел 2 и 3 записываетсякак 2 + 3. Ян Лукашевич предложил две другие формы записи: префиксная форма, вкоторой знак операции записывается перед аргументами, и постфиксная форма, в которойзнак операции записывается после аргументов. В префиксной форме сумма чисел 2 и 3записывается как + 2 3, в постфиксной — как 2 3 +. В честь Яна Лукашевича эти формызаписи называют прямой и обратной польской записью.В польской записи скобки не нужны. Например, выражение(2+3)*(15-7)записывается в прямой польской записи как70* + 2 3 - 15 7,в обратной польской записи — как2 3 + 15 7 - *.Если прямая польская запись не получила большого распространения, то обратнаяоказалась чрезвычайно полезной. Неформально преимущество обратной записи передпрямой польской записью или обычной записью можно объяснить тем, что гораздоудобнее выполнять некоторое действие, когда объекты, над которыми оно должно бытьсовершено, уже даны.Обратная польская запись формулы позволяет вычислять выражение любой сложности,используя стек как запоминающее устройство для хранения промежуточных результатов.Для вычисления выражения надо сначала преобразовать его в обратную польскую запись(при некотором навыке это легко сделать в уме).
В приведенном выше примеревыражение (2+3)*(15-7) преобразуется к2 3 + 15 7 - *Затем обратная польская запись просматривается последовательно слева направо. Еслимы видим число, то просто вводим его в калькулятор, т.е. добавляем его в стек. Если мывидим знак операции, то нажимаем соответствующую клавишу калькулятора, выполняятаким образом операцию с числами на вершине стека.Изобразим последовательные состояния стека калькулятора при вычислении поприведенной формуле.
Сканируем слева направо ее обратную польскую запись:2 3 + 15 7 - *Стек вначале пуст. Последовательно добавляем числа 2 и 3 в стек.|| вводим число 2| 2 | вводим число 3| 3 || 2 |Далее читаем символ + и нажимаем на клавишу + калькулятора. Числа 2 и 3 извлекаютсяиз стека, складываются, и результат помещается обратно в стек.| 3 | выполняем сложение| 2 || 5 |Далее, в стек добавляются числа 15 и 7.| 5 | вводим число 15| 15 | вводим число 7 | 7 || 5 || 15 || 5 |Читаем символ - и нажимаем на клавишу - калькулятора.
Со стека при этом снимаютсядва верхних числа 7 и 15 и выполняется операция вычитания. Причем уменьшаемымявляется то число, которое было введено раньше, а вычитаемым — число, введенноепозже. Иначе говоря, при выполнении некоммутативных операций, таких как вычитаниеили деление, правым аргументом является число на вершине стека, левым — число,находящееся под вершиной стека.| 7 | выполняем вычитание| 15 || 5 || 8 || 5 |Наконец, читаем символ * и нажимаем на клавишу * калькулятора.
Калькуляторвыполняет умножение, со стека снимаются два числа, перемножаются, результатпомещается обратно в стек.| 8 | выполняем умножение| 5 || 40 |Число 40 является результатом вычисления выражения. Оно находится на вершине стекаи высвечивается на дисплее стекового калькулятора.ЗАДАНИЕ НА ДОМНаписать программу, реализующую калькулятор. В проект должны входить три файла:"streal.h", "streal.cpp" и "stcalc.cpp". Первые два файла реализуют стек вещественныхчисел, эта реализация уже рассматривалась выше. Файл "stcalc.cpp" реализует стековый71калькулятор на базе стека, его и нужно добавить к проекту.
Пользователь вводит строкуиз чисел и арифметических операций – программа должна распарсить строку, записатьчисла в стек, а при наличии арифметической операции выполнить ее и поместитьрезультат обратно в стек. Пользователь может ввести число с клавиатуры, это числопросто добавляется в стек. При вводе одного из четырех знаков арифметических операций+, -, *, / программа извлекает из стека два числа, выполняет указанное арифметическоедействие над ними и помещает результат обратно в стек. Значение результатаотображается также на дисплее.
Кроме арифметических операций, пользователь можетввести название одной из стандартных функций: sin, cos, exp, log (натуральныйлогарифм). При этом программа извлекает из стека аргумент функции, вычисляетзначение функции и помещает его обратно в стек. При желании список стандартныхфункций и возможных операций можно расширить. Каждую команду стековогокалькулятора нужно реализовать в виде отдельной функции. Например, вычитаниереализуется с помощью функции onSub():static void onSub() {double y, x;if (st_size() < 2) {printf("Stack depth < 2.\n");return;}y = st_pop();x = st_pop();st_push(x - y);display();}Двоичные файлы.
Формат BMP.Так сложилось, что файлы делятся на текстовые и нетекстовые (последние иногданазывают двоичными, или бинарными), файл, содержащий программу на Си, —текстовый; файл, который вы можете создать, используя, например, любой текстовыйредактор (FAR или кому что нравится), — тоже текстовый. А вот файл, содержащий,например, рисунок в формате bmp, JPEG, да и в любом другом графическом формате —двоичный. Текстовые файлы отличаются от двоичных двумя особенностями: во-первых,они делятся на строки, каждая из которых заканчивается "переводом строки", состоящимиз двух символов с кодами 0x0D 0x0A; во-вторых, текстовые файлы заканчиваются"признаком конца файла" — символом с кодом 0х1А (точнее, должны заканчиваться, этоусловие соблюдается не всегда).При чтении текстового файла (потока) функции Си преобразуют "признак концастроки", т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
