Виды записи выражений. Особенности обратной польской записи. Вычисления на стеке. Преобразование из инфиксной нотации. Операторы входного языка. Описание выходной информации. Алгоритмические аспекты программы-распознавателя арифметических выражений.
Аннотация к работе
Формулы встречаются повсеместно в экономике, физике, биологии, и, конечно же, в математике. Можно представить выражение в виде графика, или таблицы. В данной курсовой работе будет разработана программа, которая продемонстрирует способ распознавания компьютером введенных пользователем математических формул. Цель данной работы - разработать программу распознавания математических формул.Существуют три вида записи выражений: 1. инфиксная форма, в которой оператор расположен между операндами (например, "а b"); 2. постфиксная форма, в которой оператор расположен после операндов ("а b "); Постфиксная и префиксная формы образуют т.н. польскую форму записи (польская нотация). Обратная польская нотация была разработана австралийским философом и специалистом в области теории вычислительных машин Чарльзом Хэмблином в середине 1950-х на основе польской нотации, которая была предложена в 1920 году польским математиком Яном Лукасевичем. Первыми компьютерами, поддерживающими обратную польскую нотацию были KDF9 от English Electric Company, который был анонсирован в 1960 и выпущен (появился в продаже) в 1963, и американский Burroughs B5000, анонсирован в 1961, выпущен в том же 1963.В общем виде запись выглядит следующим образом: · Запись набора операций состоит из последовательности операндов и знаков операций. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность ее операндов и ее знак, после чего выражение вычисляется дальше по тому же правилу. Очевидное расширение обратной польской записи на унарные, тернарные и операции с любым другим количеством операндов: при использовании знаков таких операций в вычислении выражения операция применяется к соответствующему числу последних встретившихся операндов. Особенности обратной польской записи следующие: · Порядок выполнения операций однозначно задается порядком следования знаков операций в выражении, поэтому отпадает необходимость использования скобок и введения приоритетов и ассоциативности операций.Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека. Если на вход подан операнд, он помещается на вершину стека. Если на вход подан знак операции, то соответствующая операция выполняется над требуемым количеством значений, извлеченных из стека, взятых в порядке добавления.Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. В процессе преобразования используется стек, хранящий еще не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ - это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан. * Если символ является открывающей скобкой, помещаем его в стек. * Если символ является закрывающей скобкой: До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку.В рамках данного курсового проекта необходимо разработать программу - распознаватель арифметических выражений. Для эффективной организации процесса разработки и получения удовлетворительного результата мною были определены следующие требования к программе: 1.Программа разработана в соответствии со следующей спецификацией входной информации: Входная информация - строка символов, являющаяся правильным математическим выражением, содержащая операнды и операторы. 1 Сложение Складывает два операнда находящиеся справа и слева от оператора. 2 - - Вычитание Вычитает из операнда находящегося слева из операнда, находящегося справа от оператора. / : Частное Делит операнд, находящейся слева, на операнд, находящейся справа от оператора.Выходной информацией данной программы являются следующие данные: 1. Дерево разбора.Дерево разбора представляет собой отображение структуры дерева в табличном виде, для связи родительских веток с дочерними используются специального вида ссылки.Алгоритм программы представляет собой соединение двух алгоритмов: 1. Построение выражение по принципу польской префиксной записи. Первый алгоритм представляет собой построение дерева, представленного в табличном виде, по принципу разности приоритета используемых во входном выражении операндов. Приоритеты операндов показаны в таблице 3. Кроме того, в набор языка вводиться новый операнд, представляющий цифру, обозначенную с двух сторон кавычками.Алгоритм программы представлен следующей схемой: Рисунок 1 - Алгоритм программы Рисунок 2 - Алгоритм программыРазработанная программа не требует инсталляции. Рисунок 9 - Введено выражение. Программа заполнит дерево разбора узлами с информацией в виде префиксной записи и список промежуточных результатов.В результате работы была разработана программа, реализующая алгоритм разбора арифметического выражения, используя классически
План
Оглавление
Введение
1. Теоретическая часть
1.1 История разработки вопроса разбора математических выражений
1.2 Обратная польская нотация
1.3 Вычисления на стеке
1.4 Преобразование из инфиксной нотации
2. Практическая часть
2.1 Постановке задачи
2.2 Описание входного языка
2.3 Описание выходной информации
2.4 Алгоритмические аспекты программы
2.5 Алгоритм программы
2.7 Работа с программой
Заключение
Литература
Приложение
Введение
Мы все знаем, что такое математическое выражение. Это формула. Формулы встречаются повсеместно в экономике, физике, биологии, и, конечно же, в математике. В общем, везде, где нужно символически представить какую-нибудь функцию или соотношение. Символическое представление, конечно, не единственное. Можно представить выражение в виде графика, или таблицы. Но все же формула является самым компактным и универсальным способом.
В данной курсовой работе будет разработана программа, которая продемонстрирует способ распознавания компьютером введенных пользователем математических формул.
Цель данной работы - разработать программу распознавания математических формул.
Для достижения цели необходимо выполнить следующие задачи: 1. Изучить теоретический материал по предмету.
2. Разработать концепцию реализации программы.
3. Реализовать программу на языке программирования Delphi 7.
4. Составить пояснительную записку.
Вывод
Дерево разбора представляет собой отображение структуры дерева в табличном виде, для связи родительских веток с дочерними используются специального вида ссылки.
Результаты промежуточных вычислений представляют собой результаты примитивных математических операций, выполняющихся в пределах одного узла дерева разбора.
Конечный результат представляет собой итог всех операций и является результатом вычисления арифметического выражения.