Программирование сложных арифметических выражений — это программная реализация алгоритма вычисления различных арифметических выражений и формул.
Введение
Парсер - это программа, которая осуществляет анализ входного арифметического выражения. Такие программы часто называют «распознавателями».
Парсинг - это процедура разложения входных арифметических выражений на отдельные более упрощённые компоненты. Итогом действий парсера становится построенное дерево лексем.
Лексема – это фрагмент входного арифметического выражения, который не возможно дальше разделить на составляющие компоненты.
Алгоритм распознавания обычно описывается без ориентации на какой-либо язык программирования, то есть он может быть реализован фактически на любом из известных языков.
Программирование сложных арифметических выражений
Допустим, на вход парсера поступает арифметическое выражение, представленное в следующем виде:
(x + 10.2)^2 + 5 * y – z
Входное выражение будет считаться правильным согласно грамматическим правилам для арифметических выражений, а именно:
- Число открывающих скобок равняется числу скобок зарывающих.
- Целая составляющая числа отделяется от дробной при помощи точки.
- В строчке имеются лишь разрешённые символы, то есть цифры от нуля до девяти, операторы +-*/^, скобки, точка и символы x, y, z.
Парсеру необходимо выстроить дерево лексем, позволяющее осуществить вычисление числового значения входного выражения. Величины параметров должны передаваться методу, который и будет выполнять расчёт числового значения. Каждому конкретному выражению соответствует одно дерево объектов. Далее, при помощи сформированного дерева объектов, производится вычисление результата выходного выражения при заданных значениях параметров. Вычисления могут быть повторены любое количество раз.
Алгоритм обязан допускать обработку входных выражений любого размера (естественно при разумных пределах) без всяких границ по степени вложенности скобок.
Вначале следует выполнить лексический анализ входного выражения, то есть нужно осуществить удаление незначащих символов типа пробелов и тому подобное, и реализовать цельные лексемы. Такая операция не считается обязательной в рамках алгоритма, но она значительно упрощает восприятие самого алгоритма и его программной реализации. Цельная лексема может быть или оператором, то есть арифметической операцией, или операндом, то есть числом, состоящим из одной или нескольких цифр, или параметром, или скобкой, то есть элементом, изменяющим приоритет осуществления арифметических операций в строке.
Все цельные лексемы, входящие в состав древовидной структуры, описываются объектами. Каждый объект дерева имеет набор свойств (полей) и определённое поведение. Каждый объект, моделирующий лексему, может иметь следующие поля:
- Name является полем, определяющим присвоенное объекту имя.
- Lec является полем, определяющим массив лексем, предназначенный для сохранения информации о том сегменте входного выражения, вершиной которого выступает этот узел дерева объектов.
- Const является полем, хранящим значение переменной, если этот объект выступает как число.
- Var является полем, хранящим наименование переменной, если этот объект является параметром.
Поведение всех объектов может быть охарактеризовано набором методов. Для приведённого выше примера достаточно одного метода, к примеру, calc(). Когда объект выполняет описание поведения операнда (числа) или параметра, то нужно чтобы он осуществлял возврат этого числа или значения параметра. Когда объект выполняет описание лексемы, которая является одним из операторов, то есть это арифметические операции, тогда метод обязан осуществить возврат результата использования этого оператора с двумя числами.
Весь набор объектов древовидной структуры может принадлежать к одному классу, надо просто выполнить переопределение на один метод при формировании объекта. Или же имеется возможность описания абстрактного класса с единой абстрактной функцией calc().
Дальше для всех типов лексем необходимо описать свой класс, который наследует абстрактный класс и определяет фактическое поведение метода calc(). Отдельные поля могут не заполняться, это определяется тем обстоятельством, модель какой лексемы осуществляет выбранный объект.
Лексема является узлом древовидной структуры, а объекты моделируют лексемы. Необходимо из объектов сформировать древовидную структуру. Эта проблема является типичной для проектов программного обеспечения. Чтобы скомпоновать объекты в древовидную структуру следует прибавить к каждому объекту следующие поля:
- Children Left является полем левого наследника выбранного объекта.
- Children Right является полем правого наследника выбранного объекта.
- Parent является родителем выбранного объекта.
Термины «родитель» и «наследник» используются для указания на взаимное расположение объектов по отношению к заданному объекту в спроектированной древовидной структуре. Для примера, ниже приведено изображение древовидной структуры для выражения «(x + 10.2)^2 + 5 * y – z», с указанием значений всех полей объектов:
Рисунок 1. Древовидная структура. Автор24 — интернет-биржа студенческих работ
Из этой схемы очевидно, что все узлы могут иметь лишь пару наследников или их может не быть совсем. Сформированная структура объектов может использоваться для вычисления значений арифметических выражений путём вызова метода calc() для расположенного на самом верху схемы объекта.
После получения на входе массива цельных лексем всего арифметического выражения, следует определить в нём точку «перегиба». Значение определённой точки «перегиба» даёт возможность однозначного определения класса объекта, расположенного на вершине структуры. Затем нужно разделить массив лексем на две части и в каждой из частей так же определить точки «перегиба», указывающие на класс объектов наследников слева и справа.
