Реферат: Текст программы. 7 Используемые переменные. 7. Структура узла бинарного дерева. 7. Функция создания дерева. 7
Министерство образования и науки РФ
Уральский государственный технический университет – УПИ
ТЕПЛОЭНЕРГЕТИЧЕСКИЙ ФАКУЛЬТЕТ
КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ
РАСПОЗНАВАНИЕ ФОРМУЛ
Преподаватель:
Студент:
Группа:
СОДЕРЖАНИЕ
2. 1. Основные принципы алгоритма. 4
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
Написать программу, читающую текст алгебраической формулы в инфиксной форме, включающей операции сложения, вычитания, умножения и деления, операнды (a, b, c, …, x, y, z) и круглые скобки.
Требуется построить бинарное дерево, представляющее формулу, и выдать на экран само дерево и формулу в префиксной и постфиксной форме.
Необходимо также обнаружить ошибки в написании входной формулы (например, баланс скобок).
Продемонстрировать работу программы на примере распознавания формулы:
( x +( y / z ))*(( x )-( y )*( f + d ))/( a +3)+1
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. 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).
Рис. 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» и определенных знаний в области программирования. Данный же программный продукт представляет собой рабочую версию программы, реализующую в себе функцию распознавание формулы, последующий перевод в префиксную и постфиксную форму записи и построение бинарного дерева.