Текст программы. 7 Используемые переменные. 7. Структура узла бинарного дерева. 7. Функция создания дерева. 7

Написать программу, читающую текст алгебраической формулы в инфиксной форме, включающей операции сложения, вычитания, умножения и деления, операнды (a, b, c, … , x, y, z) и круглые скобки.

Требуется построить бинарное дерево, представляющее формулу, и выдать на экран само дерево и формулу в префиксной и постфиксной форме.

Необходимо также обнаружить ошибки в написании входной формулы (например, баланс скобок).

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

(x+(y/z))*((x)-(y)*(f+d))/(a+3)+1

2. РЕШЕНИЕ

2. 1. Основные принципы алгоритма.

Существуют три вида записи выражений:

- инфиксная форма, в которой оператор расположен между операндами (например, "а + b");

- постфиксная форма, в которой оператор расположен после операндов ("а b + ");

- префиксная форма, в которой оператор расположен перед операндами ("+ а b").

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

Алгоритм вычисления постфиксной формы записи из инфиксной:

- К формуле на входе (в конец записи) и на вершину стека добавляем остановочный оператор – %;

- Поэлементно слева направо идем по формуле;

- Операнды переходят в результат;

- Левые круглые скобки толкаем(push) в стек;

- Встретив правую круглую скобку, выталкиваем(pop) из стека все операторы пока не встретим левую скобку;

- Если оператор имеет более высокий приоритет вычисления, чем оператор на вершине стека, то оператор толкаем в стек;

- Если оператор имеет равный или меньший приоритет вычисления, чем оператор на вершине стека, то выталкиваем оператор из стека в результат, и толкаем в стек новый оператор;

- Достигнув на входе % – остановочный оператор, выталкиваем все из стека, пока не дойдем до %.

Стек – это специальная область памяти, представляющая собой очередь типа «последним пришел – первым вышел».

Алгоритм вычисления префиксной формы записи реализуется следующим образом:

- Имеем на входе формулу в инфиксной форме: a+b/(c-d);

- Перепишем формулу справа налево: (d-c)/b+a;

- Воспользуемся алгоритмом постфиксной трансляции, получим: dc-b/a+;

- Полученную формулу перепишем справа налево, получим формулу в префиксной записи: +a/b-cd.

Все описанные алгоритмы (перевод в постфиксную и префиксную форму записи) реализованы в программе, написанной на объектно-ориентированном языке программирования Borland C++ Builder 4.

2. 2. Текст программы.

2 . 2. 1. Используемые переменные.

char formula[100]="";

char resultat[100]="";

char temp_formula[100]="";

char turn_formula[100]="";

int b=0, k, i=0, t=0, j=0;

2 . 2. 2. .Структура узла бинарного дерева.

struct node

{

char op;

node *left,*right;

};

2 . 2. 3. .Функция создания дерева.

node * BuildTree(char s[],int & ps){

node * n=new node;

n->op=s[ps++];

if(n->op=='+'||n->op=='-'||n->op=='*'||n->op=='/')

{

n->left=BuildTree(s,ps);

n->right=BuildTree(s,ps);

}

else

n->right=n->left=NULL;

return n;

}

2 . 2. 4. .Функция вывода дерева.

void PrintTree(node * p,int lev=0){

if(p==0) return;

PrintTree(p->left,lev+1);

Form1->Memo1->Lines->Add("");

for(int i=0;i<lev;i++) Form1->Memo1->Text=Form1->Memo1->Text+" ";

Form1->Memo1->Text=Form1->Memo1->Text+p->op;

PrintTree(p->right,lev+1);

}

2 . 2. 5. .Функции, реализующие стек.

const int maxsize=50;

char values[maxsize];

int top=0;

bool empty()

{

if (top==0) return true;

else return false;

}

void push(char c)

{

if (top==maxsize) ShowMessage("Overflow in stack!!!");

else values[top++]=c;

}

void pop(char &c)

{

if (empty()) ShowMessage("Stack is empty!!!");

else c=values[--top];

}

2 . 2. 6. .Функция перевода в постфиксную форму записи.

void PostFix(char *in, char *res)

{

int i=0;

int n_r=0;

char c, temp;

push('%');

while (in[i]!='%')

{

c=in[i++];

if (c=='(') {push(c); continue;}

if (c==')')

{

pop(temp);

while (temp!='(')

{

res[n_r++]=temp;

pop(temp);

}

continue;

}

if (c=='+'||c=='-')

{

pop(temp);

if (temp=='%'||temp=='(')

{

push(temp);

push(c);

}

else if (temp=='+'||temp=='-'||temp=='*'||temp=='/')

{

res[n_r++]=temp;

push(c);

}

continue;

}

if (c=='*'||c=='/')

{

pop(temp);

if (temp=='%'||temp=='('||temp=='+'||temp=='-')

{

push(temp);

push(c);

}

if (temp=='*'||temp=='/')

{

res[n_r++]=temp;

push(c);

}

continue;

}

else res[n_r++]=c;

}

pop(temp);

while (temp!='%')

{

res[n_r++]=temp;

pop(temp);

}

2 . 2. 7. . Алгоритм перевода в префиксную форму записи.

// Определяем количество символов в формуле

i=0;

while (formula[i]!='%')

{

k=i;

i++;

}

// Реверсируем формулу справа налево

for (i=k; i>=0; i--)

{

if (formula[i]=='(') temp_formula[j]=')';

else if (formula[i]==')') temp_formula[j]='(';

else {

temp_formula[j]=formula[i];

t++;

}

j++;

}

j=0;

// Добавляем остановочный символ - %

temp_formula[++k]='%';

// Обнуляем resultat

for (i=0; i<=100; i++)

resultat[i]=NULL;

// Запускаем алгоритм постфиксного преобразования

PostFix(temp_formula, resultat);

// Реверсируем формулу обратно справа налево и получаем формулу в префиксной форме

for (i=t-1; i>=0; i--)

{

turn_formula[j]=resultat[i];

j++;

}

2. 3. Графический интерфейс пользователя.

Графическая оболочка представляет собой окно (Рис. 1):

Рис. 1

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

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

2. 4. Результат.

В результате программа распознает формулу и выводит на экран бинарное дерево формулы (Рис. 2).

Рис. 2

Программа по заданному алгоритму вычислила:

(x+(y/z))*((x)-(y)*(f+d))/(a+3)+1 – инфиксная форма записи;

xyz/+xyfd+*-*a3+/1+ – постфиксная;

+*+x/yz/-x*y+fd+a31 – префиксная.

3. ЗАКЛЮЧЕНИЕ

Разработанная программа на языке программирования «Borland C++ Builder 4», представляет собой яркий пример использования объектного языка программирования. Разработка приложения «Транслятор формул» показала огромные возможности C++, высокую скорость разработки приложения, удобную организацию проекта, читабельность кода программы.

Любые изменения данной программы легко реализуются при наличии установленного на компьютере «Borland C++ Builder 4» и определенных знаний в области программирования. Данный же программный продукт представляет собой рабочую версию программы, реализующую в себе функцию распознавание формулы, последующий перевод в префиксную и постфиксную форму записи и построение бинарного дерева.