Теоретические сведения. Рассмотрим выражение x2 + 2x + 4

Рассмотрим выражение x² + 2x + 4. Это выражение может быть изображено в виде древовидной структуры - графа (см. рис. 1 а). Для вычисления выражения, представленного графом, например для x=l, необходимо, начиная с нижнего уровня, вычислять значение в вершинах и постепенно подниматься к корню (см. рис. 1 b-d).

+

+

* + ® 1 +

X X * 4 2 4®+

2 x 1 6

a) b) c)

Рис. 1. Изображение арифметического выражения в виде графа - дерева

Сведем задачу к двум подзадачам:

• построение дерева за заданным выражением;

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

Для реализации первой подзадачи опишем новый тип данных - базовый (родительский) класс „вершина дерева”. Назовем этот тип Telement - тип „элемент дерева”. Такой базовый тип будет обладать общими для всех вершин дерева свойствами, а именно: указателями left и right на левую иправую вершины подчиненного дерева (типа Telement*) и функцией rezult, которая вычисляет результат вэтой вершине:

class Telement {

protected:

// Указатели на левую и правую ветви поддерева

Telement *left, *right;

// Конструктор - создает объект за указателями

Telement (Telement* I,Telement* r ) // на левую и правую вершины

{

left = I;

right = r;

}

public:

~Telement(void) // Деструктор - уничтожает указатели на левую и правую

{delete left; delete right;} // вершины поддерева

virtual float rezult(void) {}

};

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

Рассмотрим деструктор ~Telement. Как известно, деструктор вызовется для уничтожения объекта (например, командой delete). Во время вызова ~Telement() для вершины дерева будет инициировано выполнение этого деструктора для вершин левого и правого поддеревьев. Итак, путем рекурсивного вызова деструктора будет уничтожено целое дерево.

Укажем, что функция результата rezult() должна вычислять и возвращать значение дерева математического выражения. Эта функция будет во всех классах, но ее реализации будут зависеть от конкретного потомка и будут отличаться. Поэтому в предке она есть нереализованной. Кроме этого, вывод о том, функция какого из производных классов должна быть вызвана, принимается лишь на этапе выполнения программы после построения дерева конкретного математического выражения (это и есть позднее, или динамическое связывание). Напомним, что такие функции называются виртуальными и обозначаются ключевым словом virtual.

Вершиной (элементом) построенного дерева может быть операция „+", „*" или число. Поэтому унаследуем от класса Telement (см. рис. 2 ) три класса-потомка: два для арифметических действий („+” - Plus, „*” - Mult) и для числа (Number).

Telement

Number Plus Mult

Рис.2.Иерархическое дерево классов.

Рассматривая дерево математического выражения на рис. 1 а, и делая обобщение, сформулируем:

Правило 1. Вершины „число” и „переменная" (класс Number) всегда находятся на последнему уровне и не имеют поддеревьев. Поэтому в этом классе указатели на левую и правую подчиненные вершины будут нулевыми (NULL), a функция результата rezult() возвращает константу или значение переменной.

Правило 2. Объекты классов арифметических действий („+” и „*”) всегда имеют как левую, так и праву ветви. Для классов Plus и Mult двумя ветвями поддерева будут указатели на объекты класса Telement. Функция результата этих классов может выполнить функции rezult() для левой и правой подчиненных вершин, а также операции сложения или умножения. Поэтому вызов функций rezult() для подчиненных вершин создадут рекурсивные вызовы функций результата к низу дерева.

Важно отметить, что поскольку подчиненные вершины объекта класса Plus или Mult являются однотипными (базового типа Telement), становятся правомерными вызовы функций rezult() этих вершин независимо от их конкретного типа. Учитывая то, что в базовом классе функция результата описана как виртуальная, механизм позднего (динамического) связывания обеспечивает вызов унаследованной функции rezult() вершины нужного класса, а не пустую заготовку функции Telement::rezult(). В выше приведенной задаче мы вынуждены использовать механизм позднего связывания, поскольку математическое выражение задается на этапе выполнения программы в режиме диалога, и структура дерева на момент описания создаваемых классов неизвестна.

Существование базового класса Telement дает возможность использовать единый для всех построенных классов описанный выше деструктор ~Telement(): благодаря однотипности вершин уничтожаются объекты классов Plus, Mult и Number.

Опишем классы-потомки. Начнем из класса Number:

class Number: public Telement{

float f; // действительное число находится в частной переменной f

public:

Number (float F):Telement(NULL,NULL)

{ // конструктор - присваивает числу f определенное значение, а

f = F; // у казатели на подчиненные вершины равны нулю

}

float rezult(void)

{ return f;}

// функция результата возвращает число f

};

Объект класса Number характеризует число, которое должно содержаться в конкретной вершине. Соответственно правилу 1, этот класс поддеревьев не имеет. Поэтому во время вызова конструктора базового класса вместо указателя на левую и правую ветвь передаются NULL-указатели.

Функция rezult() возвращает значение числа. Еще раз обратим внимание на квалификатор virtual в описании этой функции в базовом классе. Он означает: если доступ к объекту производного класса Number будет выполняться через указатель на базовый класс, то будет вызываться функция rezult() производного, а не базового класса. Проиллюстрируем это на примере:

Telement* A = new Number(3);

// Здесь А - указатель на тип Telement, *A - объект класса Number

A -> rezult();

// Вызовется метод rezult() класса Number, а нв класса Telement.

// Поэтому возвращается число 3, а не выполняется пустая заготовка

// виртуального метода rezult() класса Telement.

В этом фрагменте выполняется вызов функции Number::re-zult(). Если бы в базовом классе в описании функции rezult() не было слова virtual, то в этом примере вызвалась бы функция Telement::rezult().

Опишем классы, которые реализуют операции. Будем опираться на сформулированные выше правила.

struct Plus: public Telement{

Plus(Telement* I, Telement* r):Telement(I, r) // конструктор - вызовет

{}; // конструктор базового класса

float rezult(void) // Результатом есть сумма результатов левой и правой

{ return left->rezult() + right->rezult();} / /подчиненных вершин

}

// Альтернативное описание класса Plus

class Plus: public Telement{

public:

Plus(Telement* I, Telement* r): Telement (I, r) {};

float rezult(void)

{

return left -> rezult() + right -> rezult();

}

};

Конструктор этого класса лишь вызовет конструктор базового класса в соответствии с первым правилом. Функция rezult() вычисляет значения на левой и правой ветвях, а затем их подытоживает. Аналогично определенная функция rezult() для класса Mult (результаты на подчиненных ребрах перемножаются):

struct Mult: public Telement {

Mult (Telement*I,Telement*r):Telement(I,r) {};

float rezult(void)

{

return left -> rezult() * right -> rezult();

}

Если ветви есть поддеревьями, то выполнится вызов функции rezult() для вершины каждого поддерева, и так вплоть до последнего уровня, где rezult() возвращает значения числа или сменной. Поэтому достаточно вызвать rezult() для корня, после чего будет вычислено значение выражения для всего дерева.

Пример 1. Создадим дерево выражения 3 * 4 + 2:

 

Number a(3), b(4), c(2); // Объекты класса Number: a = 3, b = 4 и c = 2

Mult m(&a, &b); // a*b

Plus p(&m, &c); // m + c

Вызвав функции rezult() получим такие результаты:

p.rezult(); // возвращает значение 14

m.rezult(); // равняется 12

a.rezult(); // возвращает значение 3

Итак, мы получили набор классов, объектами которых удобно реализовать дерево, построенное на базе математического выражения. Для завершения реализации первой подзадачи рассмотрим функцию, которая строит такое дерево за заданным в виде строки символов математическим выражением, в котором переменная x обозначается маленькой латинской буквой, значения переменной x находится в поле редактирования Edit3 (см. рис.3, 4). Функция form() формирует дерево вследствие рекурсивных вызовов. Сначала функция выделяет слагаемые, дальше каждый из слагаемых раскладывается на множители, потом обрабатывает переменные и числа.

 

Telement* form(AnsiString s) // s - заданная строка символов

{ // Результат - указатель на вершину дерева построенного выражения

Telement* h;

intp; // p - позиция оператора „+"или „*"

int I = s.Length(); // I - длина заданной строки символов

AnsiString s1, s2; // искомые операнды вершины „+" ли „*"

if((p = s.Pos("+"))>1) // Если в строке есть операция „+"

{

s1 = s.SubString(1, p -1); // находим подстроки s1и s2,-

s2 = s.SubString(p + 1,1 - p); // операнды операции “+”,

h= new Plus(form(s1), form(s2));//Создаем объект Plus с

// подвершинами – найденными операндами операции “+”,

// которые будут анализироваться рекурсивными вызовами функции form

}

 

else if ((p = s.Pos("*")) > 1) // Аналогично разбиваем строку

}

s1 = s.SubString(1, p -1); // на операцию “*" і два операнди s1 и s2

s2 = s.SubString(p + 1,1 - p);

h = new Mult(form(s1), form(s2)); // С оздаем объект Multi

// рекурсивно вызываем функцию form для найденных операндов

}

else if (s == "x") // Если строка есть переменной x: создаем объект

// „число" и инициализируем его числовым значением переменной x с поля Edit3:

h = new Number(StrToFloat(Form1->Edit3->Text));

Else

// Если выражение задано правильно, в результате отсеивания

// операторов “+”, ”*” переменных „х" в строке s остается

// константа. Создаем объект „число" и инициализируем

// его числовым значением строки s:

h = new Number(StrToFloat(s));

return h; // Возвращаем указатель на созданный объект

}

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

Ход работы

1. Загрузите C++ Builder.

2. Замените Caption формы с "Forml" на "Вычисление выражения".

Поиск по сайту: