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

Министерство образования и науки РФ

Уральский государственный технический университет – УПИ

ТЕПЛОЭНЕРГЕТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ

КУРСОВАЯ РАБОТА

РАСПОЗНАВАНИЕ ФОРМУЛ

Преподаватель:

Студент:

Группа:

Екатеринбург, 2005


СОДЕРЖАНИЕ

1. ФОРМУЛИРОВКА ЗАДАЧИ. 3

2. РЕШЕНИЕ. 4

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

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

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

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

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

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

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

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

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

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

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

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

1. ФОРМУЛИРОВКА ЗАДАЧИ

Написать программу, читающую текст алгебраической формулы в инфиксной форме, включающей операции сложения, вычитания, умножения и деления, операнды (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» и определенных знаний в области программирования. Данный же программный продукт представляет собой рабочую версию программы, реализующую в себе функцию распознавание формулы, последующий перевод в префиксную и постфиксную форму записи и построение бинарного дерева.

еще рефераты
Еще работы по остальным рефератам