Текст программы. 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) из стека все операторы пока не встретим левую скобку; Если оператор имеет более высокий приоритет вычисления, чем оператор на вершине стека, то оператор