|
Министерство образования и науки РФ
Уральский государственный технический университет – УПИ
ТЕПЛОЭНЕРГЕТИЧЕСКИЙ ФАКУЛЬТЕТ
КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ
КУРСОВАЯ РАБОТА
РАСПОЗНАВАНИЕ ФОРМУЛ
Преподаватель:
Студент:
Группа:
Екатеринбург, 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» и определенных знаний в области программирования. Данный же программный продукт представляет собой рабочую версию программы, реализующую в себе функцию распознавание формулы, последующий перевод в префиксную и постфиксную форму записи и построение бинарного дерева.
|