Семинары (1171138), страница 7
Текст из файла (страница 7)
Если оно истинно, то ничего не происходит; еслиложно, то программа завершается аварийно, выдавая диагностику ошибки.4Задание 1:на базе представленного выше описания основных функция работы со стеком написатьосновную часть программы (содержание функции main), демонстрирующую использованиенаписанных операций, демонстрирующих работу со стеком.Исходный код функции mainТестовые данныеРезультат выполненияОбратная польская запись формулы.В 1920 г. польский математик Ян Лукашевич предложил способ записи арифметических формул, неиспользующий скобок.
В привычной нам записи знак операции записывается между аргументами, например,сумма чисел 2 и 3 записывается как 2 + 3. Ян Лукашевич предложил две другие формы записи: префикснаяформа, в которой знак операции записывается перед аргументами, и постфиксная форма, в которой знакоперации записывается после аргументов. В префиксной форме сумма чисел 2 и 3 записывается как + 2 3, впостфиксной — как 2 3 +. В честь Яна Лукашевича эти формы записи называют прямой и обратной польскойзаписью.В польской записи скобки не нужны. Например, выражение(2+3)*(15-7)записывается в прямой польской записи как* + 2 3 - 15 7,в обратной польской записи — как2 3 + 15 7 - *.Если прямая польская запись не получила большого распространения, то обратная оказалась чрезвычайнополезной.
Неформально преимущество обратной записи перед прямой польской записью или обычной записью5можно объяснить тем, что гораздо удобнее выполнять некоторое действие, когда объекты, над которыми онодолжно быть совершено, уже даны.Обратная польская запись формулы позволяет вычислять выражение любой сложности, используя стек какзапоминающее устройство для хранения промежуточных результатов.Для вычисления выражения надо сначала преобразовать его в обратную польскую запись (при некоторомнавыке это легко сделать в уме). В приведенном выше примере выражение (2+3)*(15-7) преобразуется к2 3 + 15 7 - *Затем обратная польская запись просматривается последовательно слева направо. Если мы видим число, топросто вводим его в калькулятор, т.е.
добавляем его в стек. Если мы видим знак операции, то нажимаемсоответствующую клавишу калькулятора, выполняя таким образом операцию с числами на вершине стека.Изобразим последовательные состояния стека калькулятора при вычислении по приведенной формуле.Сканируем слева направо ее обратную польскую запись:2 3 + 15 7 - *Стек вначале пуст. Последовательно добавляем числа 2 и 3 в стек.| 2 | вводим число 3|3||2|Далее читаем символ + и нажимаем на клавишу + калькулятора. Числа 2 и 3 извлекаются из стека,складываются, и результат помещается обратно в стек.| | вводим число 2|5|| 3 | выполняем сложение|2|Далее, в стек добавляются числа 15 и 7.| 15 | вводим число 7 | 7 || 15 ||5 |Читаем символ - и нажимаем на клавишу - калькулятора.
Со стека при этом снимаются два верхних числа 7 и15 и выполняется операция вычитания. Причем уменьшаемым является то число, которое было введенораньше, а вычитаемым — число, введенное позже. Иначе говоря, при выполнении некоммутативных операций,таких как вычитание или деление, правым аргументом является число на вершине стека, левым — число,находящееся под вершиной стека.| 5 | вводим число 15|5 ||8|| 7 | выполняем вычитание| 15 ||5||5 |Наконец, читаем символ * и нажимаем на клавишу * калькулятора.
Калькулятор выполняет умножение, состека снимаются два числа, перемножаются, результат помещается обратно в стек.| 40 || 8 | выполняем умножение|5|Число 40 является результатом вычисления выражения. Оно находится на вершине стека и высвечивается надисплее стекового калькулятора.Задание 2:Написать программу, реализующую калькулятор. В проект должны входить три файла:"streal.h", "streal.cpp" и "stcalc.cpp". Первые два файла реализуют стек вещественных чисел,эта реализация уже рассматривалась выше.
Файл "stcalc.cpp" реализует стековыйкалькулятор на базе стека, его и нужно добавить к проекту.Пользователь вводит строку из чисел и арифметических операций – программа должнараспарсить строку, записать числа в стек, а при наличии арифметической операциивыполнить ее и поместить результат обратно в стек. Пользователь может ввести число склавиатуры, это число просто добавляется в стек.
При вводе одного из четырех знаковарифметических операций +, -, *, / программа извлекает из стека два числа, выполняетуказанное арифметическое действие над ними и помещает результат обратно в стек.Значение результата отображается также на дисплее. Кроме арифметических операций,пользователь может ввести название одной из стандартных функций: sin, cos, exp, log(натуральный логарифм). При этом программа извлекает из стека аргумент функции,вычисляет значение функции и помещает его обратно в стек. При желании списокстандартных функций и возможных операций можно расширить. Каждую команду стекового6калькулятора нужно реализовать в виде отдельной функции.
Например, вычитаниереализуется с помощью функции 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();}Исходный код файла stcalc.cppТестовые данныеРезультат выполнения7Контрольные вопросы1.2.3.4.5.6.Динамические структуры: стек?Динамические структуры: очередь?Реализация стека на базе массива?Реализация основных функций работы со стеком?Стековый калькулятор и обратная польская запись формулы?Парсер строки ввода калькулятора?СПИСОК ЛИТЕРАТУРЫ1. Браунси К.
Основные концепции структур данных и реализация в С++: Пер. с англ.– М.: Изд-во Вильямс, 2002 г. – 320 с.: ил.2. Топп У., Форд У. Структуры данных в С++: ++: Пер. с англ. – М.: ЗАО«Издательство БИНОМ», 2006 г. – 816 с. :ил.3. Дейтел Х. М. Как программировать на С++: Пер. с англ. – М.: ЗАО «ИздательствоБИНОМ», 2000 г. – 1024 с.: ил.4. Страуструп Б. Язык программирования С++. Специальное издание: ++: Пер. с англ.– М.: ЗАО «Издательство БИНОМ», 2008 г.
– 1104 с. :ил.5. Шилдт Г. Полный справочник по С++: ++: Пер. с англ. – М.: Изд-во Вильямс, 2007г. – 800 с.: ил.6. Шилдт Г. С++: Базовый курс: ++: Пер. с англ. – М.: Изд-во Вильямс, 2008 г. – 624с.: ил.8датаОтчет по лабораторной работе №8«Основы C++, работы с двоичными файлами, RLE енкодер/декодер»ОценкаБонус заподпись(max 5)сложностьЦели работы:Изучение основ работы с двоичными данными, ознакомление с алгоритмом сжатия RLE.Задачи работы:- закрепить знания по работе с файлами в C++-реализовать енкодер и декодер для алгоритма сжатия RLEКраткий конспект теоретической части (ответы на контрольные вопросы)Операции чтения и записи с двоичными файлами_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Первый вариант алгоритма сжатия RLE: енкодер_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Первый вариант алгоритма сжатия RLE: декодер____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Второй вариант алгоритма сжатия RLE: енкодер_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Второй вариант алгоритма сжатия RLE: декодер_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Характеристики алгоритма RLE________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________1Работа с файлами.
Енкодер/декодер RLE.Пример 1: Рассмотрим программу, которая создает двоичный файл для записи с именемc_bin и записывает в него 4*10 порций данных в машинном формате (строки, целые ивещественные числа). После записи данных файл закрывается и вновь открывается длячтения. Для демонстрации прямого доступа к данным информация из файла считывается вобратном порядке – с конца. Контроль записываемой и считываемой информацииобеспечивается дублированием данных на экране дисплея.#include <stdlib.h>#include <math.h>#include <conio.h>int main( ){ FILE *f1;//указатель на блок управления файломint j,k;char s[]="Line";int n;float r;f1=fopen("c_bin","wb");//создание двоичного файла для записиfor(j=1;j<11;j++){ r=sqrt(j);fwrite(s,sizeof(s),1,f1);//запись строки в файлfwrite(&j,sizeof(int),1,f1);//запись целого числа в файлfwrite(&r,sizeof(float),1,f1); //запись вещественного числаprintf("\n%s %d %f",s,j,r);//контрольный вывод}fclose(f1);//закрытие файлаprintf("\n");f1=fopen("c_bin","rb");//открытие двоичного файла для чтенияfor(j=10; j>0; j--){//перемещение указателя файлаfseek(f1,(j-1)*(sizeof(s)+sizeof(int)+sizeof(float)),SEEK_SET);fread(&s,sizeof(s),1,f1);//чтение строкиfread(&n,sizeof(int),1,f1);//чтение целого числаfread(&r,sizeof(float),1,f1);//чтение вещественного числаprintf("\n%s %d %f",s,n,r);//контрольный вывод}getch();return 0;}Результат создания проектаПример 2: Приведенная ниже программа является модификацией предыдущего примера.Единственное ее отличие состоит в использовании структуры (записи) b, состоящей изсимвольного (b.s, 5 байт, включая нулевой байт – признак конца строки), целочисленного(b.n, 2 байта в BC и 4 байта в BCB) и вещественного (b.r, 4 байта) полей.#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>#include <conio.h>main( ){ FILE *f1;int j,k;2struct {char s[5];int n;float r;} b;strcpy(b.s,"Line");f1=fopen("c_rec","wb");for(j=1;j<11;j++){ b.n=j;b.r=sqrt(j);fwrite(&b,sizeof(b),1,f1);printf("\n%s %d %f",b.s,b.n,b.r);}fclose(f1);printf("\n");f1=fopen("c_rec","rb");for(j=10; j>0; j--){ fseek(f1,(j-1)*sizeof(b),SEEK_SET);fread(&b,sizeof(b),1,f1);printf("\n%s %d %f",b.s,b.n,b.r);}getch();}Результат выполненияЗадание 1:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
