Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Литература'
Заказ № зн-110 Реферат Тема: «Закон Оукена, Естественная безработица и оценка потерь рыночной экономики из-за безработицы.» Содержание Введение 2 1. З...полностью>>
'Документ'
На основании п. 2.2 Договора возмездного оказания услуг по проведению проверки достоверности определения сметной стоимости от «__» 20__ г. № , просим ...полностью>>
'Документ'
Организатор аукциона - Администрация Лавровского сельского поселения Орловского района Орловской области. Аукцион проводится Администрацией с. Лаврово...полностью>>
'Документ'
Внеклассное воспитательное занятие - это организованное педагогом общение детей и взрослых, содержанием и смыслом которого является поиск истины, напр...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

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

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

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

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

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

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

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

Студент:

Группа:

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

СОДЕРЖАНИЕ

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

2. РЕШЕНИЕ 5

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

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

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

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

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

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

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

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

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

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

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

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

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



Похожие документы:

  1. Книги: Англо-русский и русско-английский словарь пк

    Документ
    ... (функция создания резидентной программы) ... используемый (совместно) с V V - format V-формат, переменный формат (способ представления записей переменной ... бинарная операция binary operation бинарное дерево binary tree (то же, что и Б-дерево) бинарный ...
  2. Программа последовательность машинных команд, предназначенная для достижения конкретного результата

    Программа
    ... узлах (right child) внутренних узлов. Математические свойства бинарных деревьев. Свойства бинарных деревьев: Бинарное дерево с N внутренними узлами имеет N + 1 внешних узлов. Бинарное дерево с N внутренними узлами ...
  3. Программа формирования универсальных учебных действий у обучающихся на ступени начального общего образования 2 17

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

    Программа
    ... программы Планируемые результаты Используемые документы (материалы) Итоговый вариант, созданный ... и мягкого знака «ь» «Работа» (функция) букв «я, ё, ю, е» — обозначать ... текст. Программу ... бинарной ... деревьев, красиво располагать деревья ... структур ... узлов; ... перемен, ...
  5. Образовательная программа основного общего образования Муниципального бюджетного общеобразовательного учреждения

    Образовательная программа
    ... функцию; • сопоставлять «чужие» тексты интерпретирующего характера, аргументированно оценивать их; • оценивать интерпретацию художественного текста, созданную ... , деревьев, графов и с простейшими операциями с этими структурами; • создавать программы для ...

Другие похожие документы..