Программная инженерия Нижний Новгород 017 Лабораторный

2.2.4. Вычисление арифметического выражения 
Алгоритм вычисления арифметического выражения за один просмотр входной строки 
основан на использовании постфиксной формы записи выражения и работы со стеком. 
Входным данным служит строка символов, полученная в результате работы алгоритма из 
2.2.3, выходным – результат вычисления выражения. 
Выражение просматривается посимвольно слева направо. При обнаружении операнда 
производится перевод его в числовую форму и помещение в стек (если операнд не является 
числом, то вычисление прекращается с выдачей сообщения об ошибке.) При обнаружении 
знака операции происходит извлечение из стека двух значений, которые рассматриваются как 
операнд2 и операнд1 соответственно, и над ними производится обрабатываемая операция. 
Результат этой операции помещается в стек. По окончании просмотра всего выражения из 
стека извлекается окончательный результат. 
3. Разработка программного комплекса 
3.1. Структура 
С учетом сформулированных выше предложений к реализации целесообразной 
представляется следующая модульная структура программы: 

TStack.h, TStack.cpp – модуль с классом, реализующим операции над стеком; 

TFormula.h, TFormula.cpp – модуль с классом, реализующим обработку 
арифметических выражений; 

StackTestkit.cpp – модуль программ тестирования. 
3.2. Спецификации классов 
С учетом предложенных к реализации алгоритмов можно сделать следующие объявления 
классов. 
Класс TStack (файл TStack.h): 
const int MaxMemSize = 25 // максимальный размер памяти для стека 
typedef int TELEM; // тип элемента СД 
typedef TElem *PTElem // тип указателя на СД 
class TStack { 
protected: // поля 
PTElem pMem; // указатель на массив элементов
int MemSize; // размер памяти для СД 
int DataCount; // количество элементов в СД 
int Hi; // индекс вершины стека 
virtual int GetNextIndex (int index); // получить следующий индекс 
public: 
TStack (int Size = MaxMemSize);//конструктор 
~Tstack(); //деструктор 
int IsEmpty ( void ) const ; // контроль пустоты 
int IsFull ( void ) const ; // контроль переполнения 
void Put ( const TElem &Val );// добавить значение 
virtual TElem Get ( void ) ; // извлечь значение 
}; 
Тип TElem описывает тип значений элементов стека. В данном примере для типа 
элементов использован тип int, для обеспечения возможности хранения в стеке значений 
других типов (только стандартных) достаточно изменить определение типа TElem. Память 

---

 
41 
выделяется в динамической области памяти, размер стека можно задавать при инициализации 
объекта типа TStack. Для определения методов данного класса ниже приведен фрагмент файла 
TStack.cpp (модуль реализации). 
#include ”TStack.h” 
TStack :: TStack (int Size = MaxMemSize) {// конструктор 
DataCount = 0; 
if (Size=0) { Size = MaxMemSize; } 
MemSize = Size; 
pMem = new TElem [MemSize]; 
Hi = -1; } 
TStack :: ~Tstack() { //деструктор 
delete []pMem; 
} 
int TStack :: GetNextIndex (int index) { // получить следующий индекс 
return ++index ; 
} 
int TStack :: IsEmpty ( void ) const { return DataCount == 0;} 
int TStack :: IsFull ( void ) const { return DataCount == MemSize;} 
void TStack :: Put ( const TElem &Val ) { // добавить значение 
Hi = GetNextIndex(Tail); 
pMem[Tail] = Val; 
DataCount++;
} 
TElem TStack :: Get ( void ) { // извлечь значение 
DataCount--; 
return pMem[Hi--];
} 
В конструкторе выделяется память в динамически распределяемой области памяти, 
размер области памяти определяется как параметр конструктора (по умолчанию 
устанавливается MaxMemSize) и явно учитывает тип элемента стека (TElem).
Деструктор вызывает освобождение выделенной памяти. 
Метод IsEmpty проверяет наличие запомненных в стеке значений и возвращает не нулевое 
значение в случае, когда в стеке элементов нет. 
Метод IsFull оценивает возможность добавления в стек новых значений и возвращает не 
нулевое значение в случае, когда выделенная для хранения стека память заполнена полностью. 
Метод Put используется для записи в стек значения Val. Перед обращением к этой 
функции необходимо проверять стек на полноту. 
Метод Get обеспечивает получение значения, записанного в стек последним; выполнение 
операции выполняется с удалением возвращаемого значения из стека. Перед обращением к 
этой функции необходимо проверять стек на пустоту. Метод объявлен как виртуальный для 
последующей реализации схемы наследования. 
Метод GetNextIndex используется для получения индекса следующего элемента. Данный 
метод используется для инкапсуляции отношения «Следующий элемент памяти» и необходим 
для последующей реализации схемы наследования. 
Следует отметить следующие важные моменты: 

В приведенных примерах программ в качестве типа элементов стека выбран int 
(для смены типа надо переопределить обозначение TELEM. Может быть 
рекомендована разработка программ поддержки стека как шаблонов. 

---

 
42 

В данных примерах программ отсутствует также проверка возможных ошибочных 
ситуаций (например, выборка значения из пустого стека). Введение таких проверок 
должно быть выполнено в обязательном порядке. При обнаружении ошибочных 
ситуаций может быть организовано завершение программ с выдачей аварийного 
кода завершения или, что более правильно, можно применить обработку 
исключений. 

Разработка конструктора копирования и перегрузку операции присваивания 
следует выполнить самостоятельно. 
Класс TFormula (файл TFormula.h) 
const int MaxLength = 255 // максимальный размер входной строки 
class TFormula { 
private: 
char Formula[MaxLength]; // входная строка 
char PostfixForm[MaxLength]; // постфиксная запись 
public: 
TFTrans (char form[]); 
int FormulaChecker(int Brackets[], int size) ;// проверка правильности
int FormulaConverter(void); // перевод в постфиксную форму 
double FormulaCalculator(void); // вычисление результата 
};