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

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

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

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

Студент:            

Группа:             

Екатеринбург, 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

 

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

 

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

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

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

 

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

 

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

РЕШЕНИЕ

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

 

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

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

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

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

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

 

 

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

 

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

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

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

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

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

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

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

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

 

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

 

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

 

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

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

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

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

 

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

 

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

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

 

char formula[100]="";

char resultat[100]="";

char temp_formula[100]="";

char turn_formula[100]="";

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

 

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

 

struct node

{

 char op;

 node *left,*right;

};

 

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

 

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;

}

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

 

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);

}

 

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

 

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];

}

 

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

 

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);

}

}

 

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

 

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

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++;

}

 

 

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

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

Рис. 1

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

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

 

Результат.

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

Рис. 2

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

 

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

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

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

ЗАКЛЮЧЕНИЕ

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

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