Учебно-демонстрационная программа работы со стеком

Размещено на http://www.allbest.ru/

Институт Информационных технологий и коммуникаций

Кафедра Автоматизированных систем обработки информации и управления

Курсовая работа по дисциплине

«Языки программирования высокого уровня»

“Учебно-демонстрационная программа работы со стеком”

Выполнил: студент группы

Иванов А.Ф.

Учебный шифр

Курсовая работа допущена к защите

Руководитель: ст. пр. Быков. Д.И.

Урюпинск - 2011 г.

СОДЕРЖАНИЕ

1. Введение

1.1 Определение и назначение проектируемой системы

1.2 Актуальность проблемы

2. Рабочий проект

2.1 Общие сведения о работе системы

2.2 Функциональное назначение

2.3 Общий алгоритм программного продукта

2.3.1 Состав и взаимодействие модулей программы

2.3.2 Описание важнейших переменных и структур

2.3.3 Пошаговые алгоритмы наиболее важных функций

2.3.3.1 Контроль ввода

2.3.2.2 Вычисление выражения содержащего вложенные скобки

2.3.2.3 Раскрытие скобок

2.3.2.4 Постфиксная инверсия

2.3.2.5 Вычисление выражения, не содержащего скобок

2.3.2.6 Вывод отчёта

2.3.2.7 Ввод примеров выражений из текстового файла

2.3.3 Интерфейс приложения

3. Программа и методика испытаний

4. Заключение

Литература

1. Введение

1.1 Определение и назначение проектируемой программы

Стек является простейшей динамической структурой данных. Его можно рассматривать как частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются только с одного конца, называемого вершиной стека.

Целью проекта является разработка программного обеспечения, демонстрирующего использование стека при преобразовании и вычислении арифметических выражений, заданных в виде символьной строки.

1.2 Актуальность проблемы

В учебной литературе при рассмотрении стеков (и динамических структур данных вообще) основное внимание уделяется, как правило, реализации динамических структур и операций над элементами структур.

Что касается практического использования стеков, обычно указывается область их применения (системное программное обеспечение, компиляторы), без конкретных примеров.

Разрабатываемое программное обеспечение имеет цель наглядно продемонстрировать применение стека для вычисления арифметических выражений.

2. Рабочий проект

2.1 Общие сведения о работе системы.

Название главного модуля: DemoStack.exe.

Программное обеспечение необходимое для работы системы:

Операционная система Windows 98/2000/XP. Динамически связываемые библиотеки VCL60.BPL, RTL60.BPL, BORLNDMM.DLL, CC3260MT.DLL, STLPMT45.DLL среды Borland C++6.0.

Используемые технические средства:

Компьютер Intel(R) Celeron 1.7 ГГц, 96,0 Мб ОЗУ.

Используемые средства разработки программного обеспечения:

Borland C++ Builder 6;

InnoSetup Compiler;

2.2 Функциональное назначение

Программа должна обеспечивать следующие функциональные возможности:

-Вычисление арифметических выражений включающих операции + - * / , содержащих

произвольное количество вложенных выражений в скобках.

-Вывод пошагового отчёта об использовании стеков при вычислении выражения.

-Контроль правильности ввода выражений.

-Ввод из файла примеров выражений.

2.3 Общий алгоритм программного продукта

Проверить введённое выражение на правильность взаимного расположения знаков операций и операндов.

Вычислить выражение, сохраняя информацию о каждом использовании стека в узле связного списка.

* Просмотреть выражение слева направо

- если в выражении есть скобки, заменить выражение в скобках на «дежурный» символ (Q), вставить выражение в стек строк, заменить исходное выражение на выражение из скобок.

-если скобок в выражении нет, а стек строк не пуст

-инвертировать и вычислить выражение используя для вычисления стек значений с плавающей точкой.

-извлечь из стека строк выражение, заменить Q на результат вычисления.

-повторять предыдущие подпункты до тех пор пока стек строк не опустеет, и в выражении не останется скобок.

3. Вывести пошаговый отчёт об использовании стека строк и стека значений.

* При каждом использовании стека в подпункте 2, а также при инверсии выражения и замене многочлена в скобках на дежурный символ, в связный список добавляется узел содержащий информацию о выполненном действии. В режиме вывода отчёта программа предоставляет информацию из первого узла списка пользователю, удаляя затем не нужный более узел.

2.3.1 Состав и взаимодействие модулей программы

Исходный код программы распределён в четырёх модулях в зависимости от назначения функций. Функции, предназначенные для работы со стеком, помещены в модуль Stack.cpp, реализация постфиксной инверсии размещена в модуле Invert.cpp, функции реализующие вычисление выражения и вывод отчёта об использовании стека находятся в файле function.cpp. Обработчики событий элементов интерфейса описаны в модуле main.cpp. Схема взаимодействия модулей приведена на Рис. 2.1.

Рис. 2.1 Схема взаимодействия модулей программы

Размещено на http://www.allbest.ru/

Состав модулей и назначение описанных в них функций приведены в табл. 2.1

Таблица 2.1 Состав и назначение модулей программы

Имя файла	Состав	Назначение
main.cpp	const String operation= "+-*/"; const String figure = "1234567890"; const String special = "(),"; const String simbols = operation + figure + special; fstream f; void __fastcall TForm1::FormCreate() void __fastcall TForm1::Button1Click() void __fastcall TForm1::Button2Click() void __fastcall TForm1::Button3Click()	Инициализация строковых констант - множество допустимых для ввода символов. Создание файлового потока для работы с текстовым файлом, содержащим примеры выражений. Подготовка элементов пользовательского интерфейса. Контроль правильности ввода выражения, вычисление выражения. Вывод пошагового отчёта. Ввод из файла в элемент пользовательского интерфейса SourceStr класса TEdit примеров выражений.
function.h	Объявление функций, структур, констант, переменных, используемых модулями программы. void Calculation() void simpleCalculation () bool belong() void insertReport()	Вычисление выражения, содержащего скобки. Вычисление инвертированного выражения, не содержащего скобки. Проверка на принадлежность символа строке. Вставка узла в список - отчёт.

Таблица 2.1 Состав и назначение модулей программы

Имя файла	Состав	Назначение
function.h	Объявление функций, структур, констант, переменных, используемых модулями программы. bool DeleteFirst() const kol = 10 struct report struct ItemList typedef * ItemList link link head bool EmptyList report T struct StringItemStack struct DoubleItemStack StringItemStack* top DoubleItemStack* topV StringItemStack* first() DoubleItemStack * first() void push() String pop()	Удаление первого узла списка -отчёта. Число строк в строковых массивах, символизирующих стеки. Структура - отчёт. Элемент списка - отчёта. Указатель на ItemList. Первый элемент списка. Переменная -признак пустого списка. Элемент стека строк. Элемент стека значений. Указатель на вершину стека строк. Указатель на вершину стека значений. Помещение первого элемента в стек строк. Помещение первого элемента в стек значений. Добавление элемента в стек (чисел или строк -функция перегружена). Извлечение из стека строк.

Таблица 2.1 Состав и назначение модулей программы

Имя файла	Состав	Назначение
function.h	Объявление функций, структур, констант, переменных, используемых модулями программы. double pop() void Inv()	Извлечение из стека чисел. Постфиксная инверсия
function.cpp	Реализация функций AppString() AppVal() TakeString() TakeVal() InsertReport() DeleteFirst() CopyBrackets() Calculation () simple Calculation () belong ()	Добавление строки в массив строк, символизирующий стек. Удаление строки из массива строк, символизирующего стек. Вставка узла в список - отчёт. Удаление первого узла в списке -отчёте. Копирование в стек строк выражения в скобках. Вычисление выражения, содержащего скобки. Вычисление инвертированного выражения, не содержащего скобки. Проверка на принадлежность символа строке.
Stack.cpp	Реализация функций работы со стеком. StringItemStack * first() DoubleItemStack * first()	Помещение первого элемента в стек строк. Помещение первого элемента в стек строк.

Таблица 2.1 Состав и назначение модулей программы

Имя файла	Состав	Назначение
Stack.cpp	Реализация функций работы со стеком. void push() String pop() double pop()	Добавление элемента в стек (чисел или строк -функция перегружена). Извлечение из стека строк. Извлечение из стека чисел.
Invert.cpp	Функции реализации постфиксной инверсии. void exchange() int skip() void Inv()	Обмен позиций двух символов в строке. Перенос знака операции за операнд вправо. Постфиксная инверсия

2.3.2 Описание важнейших переменных и структур

struct StringItemStack //Элемент стека строк.

{

String S;//Строка

StringItemStack *p; // Указатель на следующий элемент.

};

StringItemStack *top;// Указатель на вершину стека строк.

struct DoubleItemStack //Элемент стека значений.

{

double S;//Значение

DoubleItemStack *p; // Указатель на следующий элемент.

};

DoubleItemStack *top;// Указатель на вершину стека значений..

const kol =10;//Количество элементов в строковом массиве, символизирующим стек

//Структура - отчёт

struct report

{ShortString StkS[kol];//Стек строк

ShortString StkV[kol];//Стек чисел

ShortString act; //Действие

ShortString res; //Результат инверсии

void AppString(int Pos, ShortString t);//Добавление строки

void TakeString(int Pos); //Выборка строки

void AppVal(int Pos, ShortString t);

void TakeVal(int Pos);

};

//Элемент связного списка, используемого для вывода пошагового отчёта

struct ItemList

{ report item; //Информация о действии

ItemList* next; //Указатель на следующий элемент списка.

ItemList(report x, ItemList* t)// Конструктор

{ item = x;

next = t;

}

};

typedef ItemList* link;

extern link head ; //Первый элемент списка

extern bool EmptyList; //Признак пустого списка

extern report T; //Текущее значение поля item узла списка.

2.3.3 Пошаговые алгоритмы наиболее важных функций

2.3.3.1 Контроль ввода

При обработке события

void __fastcall TForm1::Button1Click(TObject *Sender)

происходит решение следующих задач:

-удаление из введенного выражения недопустимых символов;

-контроль количества скобок в введенном выражении (количество открывающих скобок

должно быть равно количеству закрывающих);

-соответствие взаимного расположения знаков операции и операндов;

-подготовка выражения к вычислению:

замена операции вычитания на сложение с отрицательным числом.

вставка пробелов до и после каждого знака операции (пробел служит признаком

окончания символьного представления числа).

-вычисление выражения.

void __fastcall TForm1::Button1Click(TObject *Sender)

{

String S1 ="", S = SourceStr -> Text;

//Определяются две строки. Избавление от недопустимых символов осуществляется путём //копирования в строку S1 из строки S допустимых для вычисления. Символы допустимые //для вычисления определены ранее как константные строки в том же модуле (main.cpp).

//const String operation= "+-*/";

//const String figure = "1234567890";

//const String special = "(),";

//const String simbols = operation + figure + special;

bool ErInput = false;//Ошибка ввода.

//Удаление символов (если символ не принадлежит множеству допустимых он не добавляется в S1)

for (int i = 1; i < S.Length()+ 1; i++)

if ( belong(simbols,S[i] )) S1 = S1 + S[i];

//Для проверки на принадлежность символа строке используется функция

// belong(String S, char ch); определённая в файле function.cpp

//Проверка ввода

//Если введена пустая строка

if (S1 == "")

{MessageBox(0,"Введите выражение!","Ошибка!",0);

ErInput = true;

SourceStr->Text = "";

return;

}

//Проверка на соответствие операндов и операторов

//Если выражение начинается или заканчивается со знака операции

if (( belong(operation, S1[1]) ) || ( belong(operation,S1[S1.Length() ])))

{MessageBox(0,"Недопустимое выражение!","Ошибка!",0);

ErInput = true;}

for (int i = 1; i < S1.Length(); i++)

{ //Если два знака операции следуют подряд

if (( belong(operation,S1[i]) ) && ( belong(operation,S1[i+1])))

{MessageBox(0,"В выражении пропущено число!","Ошибка!",0);

ErInput = true;}

//Если скобки не содержат чисел

if (( belong(operation,S1[i]) ) && ( S1[i+1] == ')'))

{MessageBox(0,"В выражении пропущено число!","Ошибка!",0);

ErInput = true;}

if (( belong(operation,S1[i]) ) && (S1[i-1] == '('))

{MessageBox(0,"В выражении пропущено число!","Ошибка!",0);

ErInput = true;}

//Если пропущен знак операции за скобкой

if (( S1[i] == ')' )&&( !belong(operation,S1[i+1]))&&(S1[i+1] != ')') )

{MessageBox(0,"В выражении пропущен знак операции за скобкой!","Ошибка!",0);

ErInput = true;}

//Если пропущен знак операции перед скобкой

if (( !belong(operation,S1[i]))&&( S1[i+1] == '(' )&&(S1[i] != '(') )

{MessageBox(0,"В выражении пропущен знак операции перед скобкой!","Ошибка!",0);

ErInput = true;}

}

//Если выражение не содержит знаков операции

if ( ( !belong(S1,'/'))

&&( !belong(S1,'*'))

&&( !belong(S1,'-'))

&&( !belong(S1,'+')) )

{MessageBox(0,"В выражении нет знаков операции!","Ошибка!",0);

ErInput = true; }

//Подсчёт количества скобок

int a = 0;

for(int i = 1;i <= S1.Length(); ++i)

{

if (S1.Pos("()") != 0)

{

MessageBox(0,"В выражении пропущено число!","Ошибка!",0);

ErInput = true;

break;

}

if (S1[i] == '(') a++;

if (S1[i] == ')') a--;}

if (a != 0){MessageBox(0,"Лишняя скобка.","Ошибка!",0);

ErInput = true;

}

//ЕСЛИ ОШИБКИ ВВОДА НЕ БЫЛО...

if (!ErInput)

{

SourceStr -> Text = S1;

int kolOp = 0;

//Счёт знаков операций

for(int i = 1; i <= S1.Length(); ++i)

if((S1[i] == '+')

||(S1[i] == '*')

||(S1[i]== '/')) kolOp++;

//замена операции вычитания на сложение с отрицательным числом

int EndStr = S1.Length();

for (int k = 1;k <= EndStr; k++)

{

if (S1[k] == '-') {S1.Insert('+',k);k++;}

}

//добавление пробелов между знаками операций

//для разграничения чисел после инверсии

int a = kolOp, b = 0, k = 1;

while (b != a)

{ k++;

if((S1[k] == '+')

||(S1[k] == '*')

||(S1[k]== '/'))

{S1.Insert(' ',(k));

S1.Insert(' ',(k+2));

b =b+3;

a = a+2;

k++;}

}//while

Calculation ( S1);//Вычисление выражения. Функция Calculation (String& s) определена в

// файле function.cpp

Result -> Caption = S1; //Вывод результата

Button2->Enabled = true;//Сделать доступной кнопку вывода отчёта

Button1->Enabled = false;

Button3->Enabled = false;

Button2->SetFocus();

} //if(!ErInput)

}

2.3.2.2 Вычисление выражения содержащего вложенные скобки

Основную «работу» по вычислению выражения выполняет функция Calculation ().

Алгоритм работы функции:

1. Просмотреть выражение слева направо,

- если в выражении есть скобки, заменить выражение в скобках на дежурный символ (Q),

и вставить выражение в стек строк.

-если скобок нет, а стек строк не пуст

-инвертировать и вычислить выражение используя для вычисления стек

значений с плавающей точкой.

-Извлечь из стека строк выражение, заменить Q на результат вычисления.

-Повторять предыдущие подпункты до тех пор пока стек строк не опустеет, и

в выражении не останется скобок.

2.По выходе из цикла (или если скобок не было) инвертировать и вычислить выражение.

Рис. 2.2 Схема работы функции Calculation (String& s)

Размещено на http://www.allbest.ru/

void Calculation (String& s) //Раскрытие скобок

{

int count = 0; // число скобок в выражении

int coEl = 0; // число элементов в стеке строк

for (int I = 1; I <= s.Length(); ++i) //счёт скобок

if( (s[i] == `(`) || (s[i] == `)') ) count++;

//Пока в выражении есть скобки или стек строк не пуст

while ((count != 0)||(coEl != 0))

{

//-------------------------------------------------------------------------------------------------------------------

//функция CopyBrackets(String& s, int& kolEl) производит замену многочлена в скобках в

//выражении s на дежурный символ Q и помещает изменённое выражение в стек строк.

//строке s присваивается многочлен, бывший в скобках. Внешние скобки при этом //отбрасываются. Определение функции в том же файле (function.cpp)

//-------------------------------------------------------------------------------------------------------------------

//если скобки есть копирование инвертирова выражения в стек строк

if (count != 0) CopyBrackets(s,coEl);

//если их нет, а стек строк не пуст

else if (coEl != 0)

{if ((s.Pos('+')!=0)||(s.Pos('/')!=0)||(s.Pos('*')!=0))//Если в выражении присутствует знак(и)

//операции

{

Inv(s); //Инверсия выражения. Функция определена в файле Invert.cpp

simpleCalculation (s);//Вычисление `нвертированного выражения (функция определена ниже).

}

String el = pop(&top);//Из стека строк извлекается выражение el

//Этот факт фиксируется в списке -отчёте.

T.act = «Извлечение из стека строк выражения « + el;

T.TakeString(coEl);

insertReport(T);

coEl--;

//Вместо Q вносим результат вычисления

int I = el.Pos(`Q');

T.act = «Замена в выражении « + el + « «»дежурного»» символа Q на «+ s;

insertReport(T); //Фиксация замены для отчёта.

El.Insert( s,(i+1)); //Вставка результата вычисления многочлена Q.

El.Delete(i,1); //Удаление «дежурного» символа.

S = el;} //

}//end если скобок нет

count = 0;

for (int I = 1; I <= s.Length(); ++i) //счёт скобок

if( (s[i] == `(`) || (s[i] == `)') ) count++;

} //endWhile

//Программное обеспечение выходе из while или если скобок не было

if ((s.Pos('+')!=0)||(s.Pos('/')!=0)||(s.Pos('*')!=0)){

Inv(s);//Инверсия выражения

simpleCalculation (s);}//Вычисление инвертированного выражения }

}//end Calculation

2.3.2.3 Раскрытие скобок

Как видно из Рис. 2.2, функция Calculation использует функции CopyBrackets, Invert, и simpleCalculation.

Функция CopyBrackets(String& s) выполняет действия:

Замена выражения в скобках на «дежурный» символ Q;

Сохранение содержимого скобок.

Вставка изменённого выражения в стек строк.

Присваивание исходному выражению содержимого скобок.

Рис. 2.3 Схема работы функции CopyBrackets(String& s).

Выражение1_операция_(Выражение2)

Выражение2

Выражение1_операция_Q

Стек строк

void CopyBrackets(String& s, int& kolEl)

{

int j = 0;

bool Open = false;//Признак открытия скобок

String Bufstr, expr;

int PosClose = 0, PosOpen = 0;

for(int i = 1;i <= s.Length(); ++i){

if (s[i] == '(') { j++; if (!Open) {PosOpen = i; Open = true;}};

//Если j == 0 число скобок '(' равно числу скобок ')' .

if (s[i] == ')') { j--; if (j == 0) { PosClose = i;

Open = false;

Bufstr = s;

Bufstr.Delete(1,(PosOpen));

Bufstr.Delete((PosClose - PosOpen ),(s.Length() - PosClose +2) );

expr = Bufstr;//Запомнить то что в скобках

//В отчёте фиксируется факт замены в выражении s многочлена ex на Q

T.act = "Замена в выражении " + s + " многочлена " + expr + " на Q." ;

insertReport(T);

//В выражении заменить скобки на Q

Bufstr = s;

Bufstr.Delete((PosOpen), (PosClose - PosOpen +1));

Bufstr.Insert("Q",PosOpen);

//В стек строк вносится очередной элемент

if (kolEl == 0) {top = first(Bufstr);//Создание стека строк

kolEl++; //Количество элементов в стеке увеличилось.

//Изменение стека отражается в отчёте.

T.act = "Создание стека строк. Помещение строки " + Bufstr ;

T.AppString(kolEl,Bufstr);

insertReport(T);

}//

else {push(&top,Bufstr);//Вставка в стек строк.

kolEl++; //Количество элементов в стеке увеличилось.

T.act = "Добавление в стек строк строки " + Bufstr ;

T.AppString(kolEl,Bufstr);

insertReport(T);

}

s = expr;// Далее вычисляется/преобразовывается выражение в скобках

break;// Прочие скобки остаются пока без изменений

}// if (j == 0)

}

}//for

}//CopyBrackets

Функция CopyBrackets использует функции для работы со стеком строк push и first. Переменная top -указатель на вершину стека строк объявлена в файле function.h.

Функции push, pop и first определены в модуле stack.cpp.

struct StringItemStack{String S; StringItemStack *p;};//Элемент стека строк.

StringItemStack * first(String a)//Добавление первого элемента в стек строк

{

StringItemStack *pv = new StringItemStack;// Первый элемент.

pv-> S = a; // Значение

pv-> p = 0; // Он же послдний

return pv; //Возвращает свой адрес

}

void push (StringItemStack **top, String a)//Добавление нового элемента в стек строк

{

StringItemStack *pv = new StringItemStack;// Новый элемент.

pv->S = a;//Значениe

pv->p = *top;//Указывает на бывшую вершину

*top = pv; //Новая вершина стека.

}

String pop(StringItemStack **top)//Извлечение верхнего элемента

{

String Buf = (*top)->S;//Запомнить значение вершины

StringItemStack *pv = *top; //Указать на вершину

*top = (*top)->p; //Указатель вершины указывает на следующий элемент

delete pv; //Освобождение памяти

return Buf; //Его значение

}

2.3.2.4 Постфиксная инверсия

Функция Inv осуществляет инверсию выражения, не содержащего скобок по следующему алгоритму:

Строка просматривается справа налево

Если встретился знак операции `/' или `*', то он переносится за операнд вправо, причём если это первый встреченный знак операции с большим приоритетом, его позиция после переноса запоминается;

Если встретился знак операции `+', то

-если ранее встречался знак операции с большим приоритетом переносится за него;

- иначе переносится за операнд;

(В функции Button1Click все операции вычитания изменены на сложение с отрицательным числом).

Например, выражение

5+6*4-8+2

после инверсии примет вид

5 6 4*+ -8+2+

а выражение

5+6*4-8/2

5 6 4* -8 2/++

Функция Inv определена в файле Invert.cpp.

void Inv (String& stro)

{int kolOp = 0;

String Temp = stro;//Выражение до инверсии сохраняется для отчёта.

//Счёт знаков операций

for(int i = 1; i <= stro.Length(); ++i)

if((stro[i] == '+')

||(stro[i] == '*')

||(stro[i]== '/')) kolOp++;

//В конец добавляется столько же пробелов, сколько знаков операций

for (int i = 0; i < kolOp; i++) stro.Insert(' ',stro.Length()+1);

int Pos = 0;//Позиция символа операции с большим приоритетом

for (int i = stro.Length(); i >= 1; --i )

{

//Если встретился знак операции * или / он переносится за операнд,

//причём его позиция после переноса запоминается, если она не равна 0.

if(( (stro[i] == '*') || (stro[i] == '/'))&&(Pos ==0))

Pos = skip(i,stro);

else if(( (stro[i] == '*') || (stro[i] == '/'))&&(Pos !=0))

int temp = skip(i,stro);

//Если встретился + и в конце выражения находится знак

//операции * или / он переносится за него.

if( (stro[i] == '+')&&(Pos != 0))

{exchange( i,(Pos +1),stro);Pos++;}

//Если операций / или * ещё пока не встречалось, + просто переносится

// за операнд.

if( (stro[i] == '+')&&(Pos == 0))

int temp = skip(i,stro);

}//for

//Фиксация факта инверсии в отчёте

T.act = "Инверсия выражения " + Temp + " . Результат инверсии " + stro;

T.res = stro;

insertReport(T);

}//endInv

2.3.2.5 Вычисление выражения, не содержащего скобок

Инвертированное выражение вычисляет функция simpleCalculation(String& s).

Алгоритм работы функции:

Инвертированное выражение просматривается слева направо.

Если символ является цифрой, он добавляется в буферную строковую переменную val.

-если символ является знаком операции или пробелом, происходит преобразование

StrToFloat(val) и полученное значение добавляется в стек чисел с плавающей точкой.

-если символ является знаком операции, из стека извлекаются два верхних значения,

после чего результат вычисления Значение2_операция_Значение1 помещается в стек чисел.

После завершения просмотра строки, из стека извлекается результат вычисления.

void simpleCalculation(String& s)//Вычисление инвертированого выражения

{

String val = "";

int coEl =0;

double a,b;

//Выборка из строки цифровых символов

for (int i = 1; i <= s.Length(); i++)

{

if ( (s[i] != '+')

&(s[i] != '*')

&(s[i] != '/')

&(s[i] != ' ') ) val = val + s[i];

else//Как только встретился знак операции или пробел...

{if (val !="")

{

//Помещение в стек значений первого числа

if (coEl ==0) {topV = first(StrToFloat(val));coEl++;

//Фиксация факта создания стека чисел

T.act = "Создание стека чисел. Помещение числа " + val ;

T.AppVal(coEl,val);

insertReport(T);

}

else {push(&topV,StrToFloat(val));//Добавление в стек чисел

coEl++;

T.act = "Помещение числа " + val +" в стек чисел.";

T.AppVal(coEl,val);

insertReport(T);

}

val = "";

}

if(s[i]=='/') //Если встретился знак операции

{b = pop(&topV);//Извлечеие из стека первого операнда.

//Фиксация факта извлечения в отчёте.

T.act = "Извлечение из стека чисел числа " + FloatToStr(b);//Действие.

T.TakeVal(coEl);//Фиксация факта извлечения

coEl--; //Число элементов в стеке чисел уменьшилось

insertReport(T);

a = pop(&topV); //Извлечеие из стека второго операнда.

T.act = "Извлечение из стека чисел числа " + FloatToStr(a);

T.TakeVal(coEl);//Фиксация факта извлечения

coEl--; //Число элементов в стеке чисел уменьшилось

insertReport(T);

//Фиксация факта вычисления.

T.act = "Вычисление " + FloatToStr(a) + " / " + FloatToStr(b);

insertReport(T);

a = a/b; //Вычисление.

push(&topV,a); //Помещение результата в стек чисел.

coEl++; //Число элементов в стеке чисел увеличилось

//Фиксация факта изменения стека чисел..

T.act = "Помещение результата вычисления " + FloatToStr(a) +" в стек чисел.";

T.AppVal(coEl,FloatToStr(a));

insertReport(T);

}//'/'

else if (s[i]=='*'){ // Аналогично операции деления

……………………………

}//'*'

else if (s[i]=='+'){ // Аналогично операции деления

……………………………

}//'+'

}//(завершение ветви else «как только встретился знак операции…»

}//for

a = pop(&topV);// Извлечение из стека результата вычисления

T.act = "Извлечение из стека результата вычисления " + FloatToStr(a);

T.TakeVal(coEl);//Фиксация факта извлечения

coEl--; //Число элементов в стеке чисел уменьшилось

insertReport(T);

s = FloatToStr(a);//Исходному выражению присваивается результат его вычисления.

}//simpleCalculation

Функции push, pop, first, используемые функцией simple Calculation перегружены для работы со стеком значений с плавающей точкой в файле stack.cpp.

2.3.2.6 Вывод отчёта

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

инверсии выражения, выполняемой арифметической операции.

Для решения этой задачи в файле function.h определены две структуры:

const kol =10;//Количество элементов в строковом массиве, символизирующим стек

//Структура - отчёт

struct report

{ShortString StkS[kol]; //Стек строк

ShortString StkV[kol]; //Стек чисел

ShortString act; //Действие

ShortString res; //Результат инверсии

void AppString(int Pos, ShortString t); //Добавление строки

void TakeString(int Pos); //Выборка строки

void AppVal(int Pos, ShortString t); //Добавление числа

void TakeVal(int Pos); //Выборка числа

};

//Элемент связного списка, используемого для вывода пошагового отчёта

struct ItemList

{ report item; //Информация о действии

ItemList* next; //Указатель на следующий элемент списка.

ItemList(report x, ItemList* t)// Конструктор

{ item = x;

next = t;

}

};

typedef ItemList* link;

extern link head ; //Указатель на первый элемент списка

extern bool EmptyList; //Признак пустого списка

extern report T; //Текущее значение поля item узла списка.

При каждом вызове функций push, pop, first, Inv, а также при замене выражения в скобках на «дежурный» символ Q, замене Q на результат вычисления выражения в скобках и арифметических операциях +, *, / формируется информационное поле узла списка, затем в список добавляется новый узел.

Поля - строковые массивы StkS и StkV переменной T хранят текущие (на момент добавления в список нового узла) состояния стека строк и стека чисел соответственно.

Для изменения этих полей используются методы AppString, AppVal, TakeString, TakeVal,

определённые в файле function.cpp. Методы помещают в позицию строкового массива, (равную количеству элементов в стеке), копию строки, помещаемой в стек. Для стека значений с плавающей точкой в массив помещается строковое значение числа. При выборке элемента из стека соответствующая строка в массиве стирается.

//Функция добавления строки в массив строк символизирующий стек строк

void report :: AppString (int Pos, ShortString t)

{ StkS[Pos] = t; }

//Функция удаления строки из массива строк символизирующий стек строк

void report :: TakeString(int Pos)

{ StkS[Pos] ="";}

Вставка в список узла осуществляется функцией void insertReport(report x).

link head = 0;

//Вставка узла в список для последующего пошагового отчёта

void insertReport(report x)

{

link t;

//Если список не содержит элементов, создаётся первый элемент.

if(EmptyList){head = new ItemList(x,head);

EmptyList = false; }

else //Иначе вставка происходит в конец списка

{ t = head;

while (t -> next != 0) t = t-> next;

link a = t -> next;

t->next = new ItemList(x,a);

}//else

}//insertReport

Вывод пошагового отчёта происходит при обработке события

void __fastcall TForm1::Button2Click(TObject *Sender).

При каждом клике на графической кнопке «Отчёт» из созданного ранее связного списка извлекается элемент, информация поля item присваивается переменной С типа report, после чего элемент удаляется из списка. Поля переменной С выводятся в элементы пользовательского интерфейса. Таким образом, при каждом клике кнопки «Отчёт» пользователь наблюдает очередное действие процесса вычисления выражения. Когда удаляется последний элемент списка, становится доступна кнопка «Вычислить».

void __fastcall TForm1::Button2Click(TObject *Sender)

{

report C = head->item; //Первый элемент списка

Action->Caption = C.act;//Вывод первого (или очередного) действия программы при вычислении

Change->Text = C.res;//Вывод инвертированого выражения

for (int i = 0; i <= kol;++i) //Вывод "текущего" состояния стека строк

StackString->Lines->Strings[i] = C.StkS[i+1];

for (int i = 0; i <= kol;++i) //Вывод "текущего" состояния стека чисел

StackValue->Lines->Strings[i] = C.StkV[i+1];

bool Last = DeleteFirst();//Удаление первого элемента списка

//Если элемент был последний

if (!Last)

{

Button1->Enabled = true;//Кнопка "Вычисли" доступна

Button2->Enabled = false;

InvertExpr->Text ="";

//Список пуст.

head = 0;

EmptyList = true; }

}

программа стек алгоритм переменная интерфейс

2.3.2.7 Ввод примеров выражений из текстового файла

При событии OnClick компонента Button3 происходит ввод из текстового файла примеров выражений. В модуле main.cpp объявлен файловый поток для вода ifstream f связанный с файлом example.txt, размещённым в директории приложения. При событии OnClick компонента Button3, происходит ввод из файла строки. По вопросам приобретения исходных кодов обращаться strangera дог mейл тошка россия.

Файл при этом остаётся открытым.

Строка выводится в элемент пользовательского интерфейса SourceStr класса TEdit. При достижении конца файла поток очищается, указатель позиционируется в начало потока.

void __fastcall TForm1::Button3Click(TObject *Sender)

{

char input[100];

f.getline(input,sizeof(input)) ;

SourceStr->Text = input;

if (f.eof()) {f.clear(0); f.seekg(0);}

}

2.3.3 Интерфейс приложения

Диалоговые элементы пользовательского интерфейса представлены в таблице 2.

Таблица 2. Диалоговые элементы пользовательского интерфейса

Элемент интерфейса	Имя	Компонент VCL	Назначение
Графическая кнопка «Выражение»	Button3	TButton	Ввод из файла example.txt примера выражения.
Графическая кнопка «Вычислить»	Button1	TButton	Вычисление выражения.
Графическая кнопка «Отчёт»	Button2	TButton	Вывод отчёта об использовании стеков в процессе вычисления выражения.
Однострочный редактор.	SourceStr	TEdit	Ввод арифметического выражения.
Однострочный редактор.	InvertExpr	TEdit	Вывод инвертированного выражения.
Многострочный редактор.	StackString	TMemo	Вывод содержимого стека строк.
Многострочный редактор.	StackValue	TMemo	Вывод содержимого стека чисел.
Надпись.	Action	TLabel	Вывод текущего действия при вычислении выражения.
Надпись.	Result	TLabel	Вывод результата вычисления.

3. Программа и методика испытаний

Программа выполняет две основные задачи: вычисление арифметических выражений с контролем введенных выражений и вывод отчёта о использовании стека при вычислении.

Тест 1. Проверка реакции системы на ошибки в введённом выражении.

В поле «Выражение» вводились следующие примеры:

(2*2абв-7*2+10)/(2*2-\8*2+13)

1+()

(0)

(+)

((1+2)

((1+2)(

1+/7

[пустая строка]

8)(7

8+)(-7

8+()*()-7

Тест 2. Проверка точности вычисления выражений.

Для проверки использовался компилятор Microsoft Visual C++.

(2*2 - 7*2 + 10)/(2*2 - 8*2 +13) = 0

(1+7-2+9+8/4 + 78+(1+1)) = 97

(1-2*5+2*9)/(1+2*8+2*7) = 0,290322580645161

( (5*3 - 10*8)/(2*5) )/( (6*7-9*8)/(8*9*9) ) = 140,4

(5*4-10)/(4-4*4-4*4)= -0,357142857142857.

5 - (5*5*5)/3 + (5*5*5*5*5)/6 = 484,166666666667

(2*2 - 2*3)/(9*2*2 -18*2*3 + 9*3*3) + (2*2*2*2 - 2)/(3*2*2 + 3*2 +3) =0,44(4)

(2*3- 2*3*3)/(4*2*2 - 12*8 +9) = 0,169014084507042

(2*2 -3*3)/((6*8 -6*7)*(6*8 -6*7)) = -0,138888888888889.

(9-(4+2)*(4+2))/(4*4 + 10*4 +25*25*25) = -0,00172182896498948

(4*(5-9)+ 9*(5-4))/(5*8+45*23) = - 0.00651162790697664

(50+50)/(50+1) - (50*45-12)/(34+8) = -51.32492997198888

(9*26-180-12-14*3) = 0

(1+7-2+9+8/4 + 78- 31+(1+1+(1+1+(1+1)+(1+1)))) = 72

10-(5+2) = 7

((4+8)/((5*2)-(12/3)))+(12/(6/2)) = 6

8+12/6/2 =9

(5*1)+((5+1)*(5+5)-(21+1)/11) = 63

(12/(10-4))+(12/(6/2)) = 6

(12/(10-4))+((12/6)/2) = 3

(1+1+(1+1+(1+1+(1+1)+(1+1)))) = 10

(5*1)+((5+1)*(5+5)-(21+1)/11)=63

(5*1)+((5+1)*(5+5)-(21+1)/11)-22+(9/3)-99+(1+(45-9)) = -18

Во всех тестовых примерах результат вычисления полностью совпал с расчетным.

Пример выполнения теста.

Введено выражение (1+7-2+9+8/4 + 78+(1+1)).

Результат вычисления 97.

Выводимый программой отчёт представлен в таблице 3.

Таблица 3. Отчёт об использовании стека

№	Действие.	Состояние стека строк.	Состояние стека значений.	Инвертированное выражение.
1	Замена в выражении (1 + 7 + -2 + 9 + 8 / 4 + 78 + (1+1)) многочлена 1 + 7 + -2 + 9 + 8 / 4 + 78 + (1+1) на Q.
2	Создание стека строк. Помещение в него строки Q	Q
3	Замена в выражении 1 + 7 + -2 + 9 + 8 / 4 + 78 + (1+1) многочлена 1+1 на Q.	Q
4	Добавление в стек строк строки 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q
5	Инверсия выражения 1+1. Результата инверсии 1 1+	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q		1 1 +
6	Создание стека чисел. Помещение числа 1.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	1	1 1 +
7	Помещение числа 1 в стек чисел.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	1 1	1 1 +
8	Извлечение из стека числа 1.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	1	1 1 +
9	Вычисление 1+1.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q		1 1 +
10	Помещение результата вычисления 2 в стек чисел.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	2	1 1 +
11	Извлечение из стека результата вычисления 2.	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q		1 1 +
12	Извлечение из стека строк выражения 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q	Q 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q		1 1 +
13	Замена в выражении 1 + 7 + -2 + 9 + 8 / 4 + 78 + Q дежурного символа Q на 2	Q		1 1 +
14	Инверсия выражения 1 + 7 + -2 + 9 + 8 / 4 + 78 + 2 . Результат инверсии 1 7 -2 9 8 4/++++78+ 2+	Q		1 1 +
15	Создание стека чисел. Помещение числа 1	Q	1	1 7 -2 9 8 4/++++78+ 2+
16	Помещение числа 7 в стек чисел.	Q	1 7	1 7 -2 9 8 4/++++78+ 2+
17	Помещение числа - 2 в стек чисел.	Q	1 7 -2	1 7 -2 9 8 4/++++78+ 2+
18	Помещение числа 9 в стек чисел.	Q	1 7 -2 9	1 7 -2 9 8 4/++++78+ 2+
19	Помещение числа 8 в стек чисел.	Q	1 7 -2 9 8	1 7 -2 9 8 4/++++78+ 2+
20	Помещение числа 4 в стек чисел.	Q	1 7 -2 9 8 4	1 7 -2 9 8 4/++++78+ 2+
21	Извлечение из стека числа 4.	Q	1 7 -2 9 8	1 7 -2 9 8 4/++++78+ 2+
22	Извлечение из стека числа 8.	Q	1 7 -2 9	1 7 -2 9 8 4/++++78+ 2+
23	Вычисление 8/4.	Q	1 7 -2 9	1 7 -2 9 8 4/++++78+ 2+
24	Помещение результата вычисления 2 в стек чисел	Q	1 7 -2 9 2	1 7 -2 9 8 4/++++78+ 2+
25	Извлечение из стека числа 2.	Q	1 7 -2 9	1 7 -2 9 8 4/++++78+ 2+
26	Извлечение из стека числа 9.	Q	1 7 -2	1 7 -2 9 8 4/++++78+ 2+
27	Вычисление 9 +2.	Q	1 7 -2	1 7 -2 9 8 4/++++78+ 2+
28	Помещение результата вычисления 11 в стек чисел.	Q	1 7 -2 11	1 7 -2 9 8 4/++++78+ 2+
29	Извлечение из стека числа 11.	Q	1 7 -2	1 7 -2 9 8 4/++++78+ 2+
30	Извлечение из стека числа -2.	Q	1 7	1 7 -2 9 8 4/++++78+ 2+
31	Вычисление -2 + 11.	Q	1 7	1 7 -2 9 8 4/++++78+ 2+
32	Помещение результата вычисления 9 в стек чисел.	Q	1 7 -2 9	1 7 -2 9 8 4/++++78+ 2+
33	Извлечение из стека числа 9.	Q	1 7 -2	1 7 -2 9 8 4/++++78+ 2+
34	Извлечение из стека числа 7.	Q	1	1 7 -2 9 8 4/++++78+ 2+
35	Вычисление 9 + 7.	Q	1	1 7 -2 9 8 4/++++78+ 2+
36	Помещение результата вычисления 16 в стек чисел.	Q	1 16	1 7 -2 9 8 4/++++78+ 2+
37	Извлечение из стека числа 16.	Q	1	1 7 -2 9 8 4/++++78+ 2+
38	Извлечение из стека числа 1.	Q		1 7 -2 9 8 4/++++78+ 2+
39	Вычисление 1 + 16.	Q		1 7 -2 9 8 4/++++78+ 2+
40	Помещение результата вычисления 17 в стек чисел.	Q	17	1 7 -2 9 8 4/++++78+ 2+
41	Помещение результата вычисления 78 в стек чисел.	Q	17 78	1 7 -2 9 8 4/++++78+ 2+
42	Извлечение из стека числа 78.	Q	17	1 7 -2 9 8 4/++++78+ 2+
43	Извлечение из стека числа 17.	Q		1 7 -2 9 8 4/++++78+ 2+
44	Вычисление 17 + 78.	Q		1 7 -2 9 8 4/++++78+ 2+
45	Помещение результата вычисления 95 в стек чисел.	Q	95	1 7 -2 9 8 4/++++78+ 2+
46	Помещение числа 2 в стек чисел.	Q	95 2	1 7 -2 9 8 4/++++78+ 2+
47	Извлечение из стека числа 2.	Q	95	1 7 -2 9 8 4/++++78+ 2+
48	Извлечение из стека числа 95.	Q		1 7 -2 9 8 4/++++78+ 2+
49	Вычисление 95 + 2.	Q		1 7 -2 9 8 4/++++78+ 2+
50	Помещение результата вычисления 97 в стек чисел.	Q	97	1 7 -2 9 8 4/++++78+ 2+
51	Извлечение из стека результата вычисления 97.	Q		1 7 -2 9 8 4/++++78+ 2+
52	Извлечение из стека строк выражения Q.	Q		1 7 -2 9 8 4/++++78+ 2+
53	Замена в выражении Q дежурного символа Q на 97.			1 7 -2 9 8 4/++++78+ 2+

4. Заключение

В результате курсовой работы изучены и закреплены на практике:

- способы создания стека и операции над ним,

-работа с однонаправленным связным списком,

-работа с текстовым файлом (чтение данных),

-основы работы в интегрированной среде C++ Builder.

Тема курсовой работы предполагает создание программного обеспечения, демонстрирующего работу со стеком. Для стека определены операции помещения в стек и извлечения из стека. Созданное программное обеспечение позволяет наблюдать за изменением двух стеков - строк и значений в процессе вычисления арифметического выражения.

К недостаткам решения поставленной задачи можно отнести реализацию механизма постфиксной инверсии. В реальных компиляторах при преобразовании выражения в постфиксную форму используется стек, что позволяет преобразовать выражение за один просмотр, при этом выражение может содержать вложенные скобки. Предложенная реализация также инвертирует выражение за один просмотр, но стек для этого не используется, и выражение не может содержать скобок. Это влечёт за собой необходимость разработки механизма избавления от вложенных скобок, при этом используется стек, элемент которого содержит строку типа AnsiString. Потребляемый программой объём памяти может заметно возрасти при вычислении выражения с большим количеством длинных выражений в скобках.

Программа может быть расширена для вычисления выражений, содержащих иные операции чем +, -, /, *. Для этого достаточно определить символы соответствующие требуемым операциям и внести изменения в функцию simpleCalculation.

Литература:

Дейтел Х, Дейтел П. Как программировать на С++.

Павловская Т.А. С/С++ Программирование на языке высокого уровня.

Рейсфорд К, Хендерсон К. BORLAND C++ BUILDER. Освой самостоятельно.

Размещено на Allbest.ru