Компьютер и человек — как сложно нам понять друг друга. По сути, процесс программирования — это объяснение машине то, что ты от неё хочешь на понятном ей языке.
В качестве введения
По своей работе, да и в качестве хобби, я связан с процессом написания кода, связанного с математическими вычислениями. Одной из последних задач было написание ПО, в котором пользователь имел бы возможность самостоятельно вводить и использовать при расчёте, визуализации данных и оптимизации некоторых математических выражений. А учитывая свою природную лень и нежелание постоянно дополнять библиотеку кода специальных математических функций пришла в голову мысль — а почему бы не реализовать бредовую студенческую идею, и не изобрести велосипед парсера математических выражений.
Конечно, прежде чем взяться за изобретательский процесс (опять же, в виду вселенской лени), было достаточно долгое изнасилование Яндекса и Гугла на предмет уже существующих реализаций. И их нашлось конечно же не мало. Но к сожалению того, чего хотелось добиться от конкретной реализации не нашлось. А критерии поиска были следующие:
- Парсер должен быть реализован под .NET не старше 4.0;
- Он должен обрабатывать все базовые математические операторы (+,-,*,/,^, и т.п.) с учётом их приоритетов и скобок разных видов;
- Он должен распознавать основные функции (вроде sin, cos), иметь возможность добавлять в созданный объект парсера свои функции с указанием делегатов методов, вычисляющих их значение (для любого количества входных переменных);
- Должна быть возможность использования известных парсеру констант, и добавления их с список, используемый при разборе выражения;
- Должен присутствовать механизм работы с параметрами и переменными. При этом требуются переменные разных типов: просто хранящие числовое значение, либо вызывающие событие, в котором внешний код определяет их значение на момент их вызова;
- Должен быть реализован механизм функционалов (минимум — интегрирование, сумма ряда и дифференцирование)
- Результат разбора строкового выражения должен быть представлен в объектной модели бинарного дерева;
- Самое главное — бинарное дерево должно иметь возможность отображения на дерево Linq.Expression с последующей компиляцией его в делегат, выполняющий вычисление на скорости самой платформы .NET.
Цель велосипедостроения
Собственно, главная цель изобретения велосипеда была в возможности компиляции строки мат.выражения в делегат с высокой скоростью выполнения процесса расчёта значения.
К сожалению мои скудные способности работы с поисковиками, отсутствие времени, сил и лень не дали положительного результата в поиске прототипа и было принято решение пуститься в путешествие по граблям.
Модель и основная идея
Объектная модель представляет собой два класса: класс парсера и класс математического выражения. Внутри используется ещё три дополнительных класса: класс дерева математического выражения, абстрактный класс узла дерева мат.выражения и класс логического элемента строки мат.выражения — терма. Коме того, реализованы классы функции, переменной, функционала и, соответственно, коллекций функций, переменных и функционалов (они вложены в класс мат.выражения).
Идея, не претендующая на открытие, или оптимальность решения, но являвшаяся попыткой подступиться к решению задачи, заключалась в том, что бы разбить исходную последовательность символов строки мат.выражения на некоторые логические составляющие. Сформировать иерархическую последовательность типизированных логических блоков мат.выражения. И на её основе построить дерево мат.выражения.
Проектирование началось с идеи — «а как бы я хотел, что бы это выглядело в завершённом виде, и что бы это было легко и удобно использовать?». Хотелось реализовать следующий сценарий использования:
Создаётся объект парсера, закрепляемый где-нибудь на уровне модели представления, либо в бизнес логике. Он конфигурируется: в него добавляются нужные константы, определяются функции, с которыми он должен в последствии работать. Добавляются подписчики событий для обработки неизвестных функций и переменных. И парсер ждёт вызова метода Parce(string).
В основной метод Parce() передаётся в качестве входных данных строка матвыражения, а его результатом является объект мат.выражения, содержащий дерево мат.выражения.
У объекта мат.выражения должны быть представлены коллекции функций, переменных и констант, которые в нём находятся. Должна быть возможность изменения значений этих объектов, а также возможность воздействия на дерево выражения с целью его модификаций. Объект мат.выражения должен иметь метод расчёта значения (путём обхода дерева мат.выражения), получающий в качестве параметров набор входных переменных и выдающий в качестве результата численное значение.
Объект мат.выражения должен иметь метод преобразования дерева мат.выражения в объект System.Linq.Expression. И метод, позволяющий получить сразу скомпилированный делегат на основе использования механизмов Linq.Expression.
К сожалению, ни готовых реализаций чего-то подобного, ни методик, описывающих в той, или иной мере создание подобного парсера ни где не описан.
Описание объектной модели
Жизнь в объекте (после создания) начинается с вызова метода Parse.
/// <summary>Разобрать строку математического выражения</summary> /// <param name="StrExpression">Строковое представление математического выражения</param> /// <returns>Математическое выражение</returns> [NotNull] public MathExpression Parse([NotNull] string StrExpression) { Contract.Requires(!string.IsNullOrWhiteSpace(StrExpression)); Contract.Ensures(Contract.Result<MathExpression>() != null); StrPreprocessing(ref StrExpression); OnStringPreprocessing(ref StrExpression); var expression = new MathExpression(StrExpression, this); ProcessVariables(expression); ProcessFunctions(expression); return expression; } Опуская контракты, смысл его работы сводится к предобработке строки, вызову конструктора мат.выражения и постобработке этого выражения на предмет анализа его переменных и функций.
Предобработка включает два этапа:
Приватный метод StrPreprocessing, удаляющий лишние символы из строки:
/// <summary>Предварительная обработка входного строкового выражения</summary> /// <param name="Str">Обрабатываемая строка</param> // Удаление из строки всех символов, из множества запрещённых символов protected virtual void StrPreprocessing([NotNull] ref string Str) { Contract.Requires(!string.IsNullOrEmpty(Str)); Contract.Ensures(!string.IsNullOrEmpty(Contract.ValueAtReturn(out Str))); Str = new string(Str.Where(f_ExcludeCharsSet.NotContains).ToArray()); }
и метод генерации события предобработки строки, что бы пользователь парсера мог самостоятельно подготовить строку к анализу:
/// <summary>Событие предобработки входящей строки</summary> public event EventHandler<EventArgs<string>> StringPreprocessing; /// <summary>Генерация события предобработки входящей строки</summary> /// <param name="args">Аргумент события, содержащий обрабатываемую строку</param> protected virtual void OnStringPreprocessing([NotNull] EventArgs<string> args) { Contract.Requires(args != null); Contract.Requires(args.Argument != null); Contract.Requires(args.Argument != string.Empty); Contract.Ensures(args.Argument != null); Contract.Ensures(args.Argument != string.Empty); StringPreprocessing?.Invoke(this, args); } /// <summary>Генерация события предобработки входящей строки</summary> /// <param name="StrExpression">Обрабатываемая строка</param> private void OnStringPreprocessing([NotNull] ref string StrExpression) { Contract.Requires(!string.IsNullOrEmpty(StrExpression)); Contract.Ensures(Contract.ValueAtReturn(out StrExpression) != null); Contract.Ensures(Contract.ValueAtReturn(out StrExpression) != string.Empty); var args = new EventArgs<string>(StrExpression); OnStringPreprocessing(args); StrExpression = args.Argument; }
После того, как строка очищена от мусора и подготовлена к разбору, она передаётся в конструктор мат.выражения. Также в него передаётся сам парсер, отвечающий за процессы определения функций, констант и переменных.
К классу парсера будем ещё возвращаться по мере упоминаний его членов, а сейчас… Класс Математического выражения:
Конструктор, в который передаётся вызов из метода Parse:
/// <summary>Инициализация нового математического выражения</summary> /// <param name="StrExpression">Строковое представление выражения</param> /// <param name="Parser">Ссылка на парсер</param> internal MathExpression([NotNull] string StrExpression, [NotNull] ExpressionParser Parser) : this() { Contract.Requires(!string.IsNullOrEmpty(StrExpression)); Contract.Requires(Parser != null); Contract.Ensures(Tree != null); var terms = new BlockTerm(StrExpression); // разбить строку на элементы var root = terms.GetSubTree(Parser, this); // выделить корень дерева из первого элемента f_ExpressionTree = new ExpressionTree(root); // Создать дерево выражения из корня }
Опять же, опуская блок контрактов, сначала на основе строки создаётся иерархическая объектная структура термов мат.выражения. Затем из самого первого её блока вызывается метод получения корня дерева мат.выражения. И на его основе работает конструктор дерева.
На первом этапе разбора мат.выражения необходимо строковое представление (последовательность символов) объединить в последовательность логических блоков. Некоторые из них могут быть рекуррентно вложены друг в друга.
Строка разбивается на 4 вида термов:
- BlockTerm — терм, содержащий массив термов;
- StringTerm — терм, содержащий строковое значение
- CharTerm — терм, содержащий один символ, который нельзя ассоциировать с обычными строками;
- NumberTerm — терм, содержащий целое число.
Таким образом, вся строка изначально представляется как один блочный терм, внутри которого лежат составляющие элементы.
/// <summary>Новый блок математического выражения</summary> /// <param name="Str">Строковое значение блока</param> public BlockTerm(string Str) : this("", Str, "") { } /// <summary>Новый блок выражения</summary> /// <param name="OpenBracket">Открывающаяся скобка</param> /// <param name="Str">Строковое значение блока</param> /// <param name="CloseBracket">Закрывающаяся скобка</param> public BlockTerm([NotNull] string OpenBracket, [NotNull] string Str, [NotNull] string CloseBracket) : base(string.Format("{0}{2}{1}", OpenBracket ?? "", CloseBracket ?? "", Str)) { Contract.Requires(!string.IsNullOrEmpty(Str)); f_OpenBracket = OpenBracket; f_CloseBracket = CloseBracket; f_Terms = GetTerms(Str); }
Ну и базовый класс терма:
/// <summary>Элемент математического выражения</summary> abstract class Term { /// <summary>Строковое содержимое</summary> protected string f_Value; /// <summary>Конструктор элемента математического выражения</summary> /// <param name="Value">Строковое содержимое</param> protected Term(string Value) { f_Value = Value; } /// <summary>Метод извлечения поддерева для данного элемента математического выражения</summary> /// <param name="Parser">Парсер математического выражения</param> /// <param name="Expression">Математическое выражение</param> /// <returns>Узел дерева мат.выражения, являющийся поддеревом для данного элемента</returns> [NotNull] public abstract ExpressionTreeNode GetSubTree([NotNull] ExpressionParser Parser, [NotNull] MathExpression Expression); /// <summary>Строковое представление элемента мат.выражения</summary> /// <returns>Строковое содержимое элемента мат.выражения</returns> public override string ToString() => f_Value; }
Разбивка подстроки на составляющие элементы осуществляется методом GetTerms:
/// <summary>Получить список элементов математического выражения из строки</summary> /// <param name="Str">Строковое представление математического выражения</param> /// <returns>Массив элементов математического выражения</returns> [CanBeNull] private static Term[] GetTerms([CanBeNull] string Str) { if(Str == null) return null; if(Str.Length == 0) return new Term[0]; var pos = 0; var len = Str.Length; var result = new List<Term>(); while(pos < len) { var c = Str[pos]; if(char.IsLetter(c) || c == '∫') { Term value = new StringTerm(GetNameString(Str, ref pos)); if(pos < len) switch(Str[pos]) { case '(': { var blokStr = Str.GetBracketText(ref pos); var block = new BlockTerm("(", blokStr, ")"); value = new FunctionTerm((StringTerm)value, block); } break; case '[': { var blokStr = Str.GetBracketText(ref pos, "[", "]"); var block = new BlockTerm("[", blokStr, "]"); value = new FunctionTerm((StringTerm)value, block); } break; case '{': { var blokStr = Str.GetBracketText(ref pos, "{", "}"); var block = new BlockTerm("{", blokStr, "}"); value = new FunctionTerm((StringTerm)value, block); } break; } if(pos < len && Str[pos] == '{') value = new FunctionalTerm ( (FunctionTerm)value, new BlockTerm("{", Str.GetBracketText(ref pos, "{", "}"), "}") ); result.Add(value); } else if(char.IsDigit(c)) result.Add(new NumberTerm(GetNumberString(Str, ref pos))); else switch(c) { case '(': { var blokStr = Str.GetBracketText(ref pos); var block = new BlockTerm("(", blokStr, ")"); result.Add(block); } break; case '[': { var blokStr = Str.GetBracketText(ref pos, "[", "]"); var block = new BlockTerm("[", blokStr, "]"); result.Add(block); } break; case '{': { var blokStr = Str.GetBracketText(ref pos, "{", "}"); var block = new BlockTerm("{", blokStr, "}"); result.Add(block); } break; default: result.Add(new CharTerm(Str[pos++])); break; } } return result.ToArray(); }
Метод начинается с проверок на пустоту входной строки и нулевую длину. После фиксируются текущая позиция анализируемого символа в строке и её длина, после чего в цикле до достижения конца строки рассматривается символ в текущей позиции:
— Если он является буквой, или символом интеграла, то идёт попытка захвата имени методом GetNameString.
/// <summary>Получить имя из строки</summary> /// <param name="Str">Исходная строка</param> /// <param name="pos">Положение в строке</param> /// <returns>Строка имени</returns> private static string GetNameString([NotNull] string Str, ref int pos) { Contract.Requires(!string.IsNullOrEmpty(Str)); Contract.Ensures(Contract.ValueAtReturn(out pos) >= 0); Contract.Ensures(Contract.ValueAtReturn(out pos) < Str.Length); var result = ""; var L = Str.Length; var i = pos; while(i < L && (char.IsLetter(Str[i]) || Str[i] == '∫')) result += Str[i++]; if(i == L || !char.IsDigit(Str[i])) { pos = i; return result; } while(i < L && char.IsDigit(Str[i])) result += Str[i++]; pos += result.Length; return result; }
После этого проверяется текущий символ на предмет наличия в нём открывающейся скобки. Если обнаружена одна из скобок, то из строки извлекается вложенный блок, ограниченный открывающейся и соответствующей ей закрывающейся скобкой. Созданный таким образом блоковый тёрм помещается в конструктор функционального тёрма с указанием установленного ранее имени функции.
Подстрока, ограниченная открывающейся и закрывающейся скобками выделяется из строки методом-расширением:
/// <summary> /// Выделение подстроки, ограниченной шаблоном начала и шаблоном окончания строки начиная с указанного смещения /// </summary> /// <param name="Str">Входная строка</param> /// <param name="Offset"> /// Смещение во входной строке начала поиска - в конце работы метода соответствует месту окончания поиска /// </param> /// <param name="Open">Шаблон начала подстроки</param> /// <param name="Close">Шаблон окончания подстроки</param> /// <returns>Подстрока, заключённая между указанными шаблонами начала и окончания</returns> /// <exception cref="FormatException"> /// Если шаблон завершения строки на нейден, либо если количество шаблонов начала строки превышает /// количество шаблонов окончания во входной строке /// </exception> public static string GetBracketText(this string Str, ref int Offset, string Open = "(", string Close = ")") { var Start = Str.IndexOf(Open, Offset, StringComparison.Ordinal); if(Start == -1) return null; var Stop = Str.IndexOf(Close, Start + 1, StringComparison.Ordinal); if(Stop == -1) throw new FormatException(); var start = Start; do { start = Str.IndexOf(Open, start + 1, StringComparison.Ordinal); if(start != -1 && start < Stop) Stop = Str.IndexOf(Close, Stop + 1, StringComparison.Ordinal); } while(start != -1 && start < Stop); if(Stop == -1 || Stop < Start) throw new FormatException(); Offset = Stop + Close.Length; Start += Open.Length; return Str.Substring(Start, Stop - Start); }
Сначала определяются индексы первых вхождений символов начала и конца. Если начальный символ не найден, то возвращаем пустоту. Если на найден конечный символ, то это ошибка формата.
Идея метода в последовательном циклическом поиске шаблонов начала и окончания строки. Пытаемся найти следующий открывающий символ. Если он найден, и он стоит до закрывающего, то надо обновить индекс закрывающего символа. Цикл продолжается до тех пор, пока не будет такой закрывающий символ, которому не предшествует открывающий.
В результат метода попадает подстрока, расположенная между открывающим и закрывающим символом.
Если после сформированного функционального тёрма найдена открывающаяся фигурная скобка, то это начинается тело функционала. Выделяем содержимое фигурных скобок в блок и создаёт тёрм-функционал, указывая ему тёрм-функцию, которая будет с этом контексте содержать имя функционала и его параметры, а телом будет блок в фигурных скобках.
Если скобок обнаружено не было, то найденное имя является литералом (будущей переменной… или константой).
— Если очередной символ строки был цифрой, то начинается целое число. Выделяем подстроку, содержащую только цифры.
/// <summary>Получить цифровую строку</summary> /// <param name="Str">Исследуемая строка</param> /// <param name="pos">Исходная позиция в строке</param> /// <returns>Строка цифрового значения</returns> private static string GetNumberString([NotNull] string Str, ref int pos) { Contract.Requires(!string.IsNullOrEmpty(Str)); Contract.Ensures(Contract.ValueAtReturn(out pos) >= 0); Contract.Ensures(Contract.ValueAtReturn(out pos) < Str.Length); var p = pos; var l = Str.Length; while(p < l && !char.IsDigit(Str, p)) p++; if(p >= l) return null; var start = p; while(p < l && char.IsDigit(Str, p)) p++; pos = p; return Str.Substring(start, p - start); }
Результат работы этого метода — строка с цифрами — попадает в конструктор целочисленного тёрма.
— Если очередной символ строки — это открывающаяся скобка, то начинается блок. Выделяем его подстроку методом-расширением GetBracketText.
— Если очередной символ — не скобка, то это неопределённый символ, который превращается в символьный тёрм.
Все созданные термы сперва собираются с список, а затем возвращаются в виде массива.
Конструкторы всех остальных термов менее интересные. Они просто сохраняют получаемые параметры во внутренних полях (возможно, с преобразованием типов).
После этого строка будет преобразована в логическую иерархическую структуру вложенных друг в друга последовательностей термов разного вида. Из этой последовательности рекуррентно строится бинарное дерево мат.выражения.
Основой дерева является базовый класс узла дерева мат.выражения.
Каждый узел — класс, хранящий ссылки на узел-корень левого поддерева и узел-корень правого поддерева, а также ссылку на своего предка. Абстрактный класс узла дерева предоставляет интерфейс для доступа к узлам предкам/потомкам, методы обхода, функциональные индексаторы, позволяющие получить перечисления узлов, связанных с текущим, рекурсивные методы получения известных данному узлу (как корня своего поддерева) переменных, функций и т.п. Также базовый класс узла предоставляет ряд вычислимых свойств: признаки — является ли узел левым/правым поддеревом, является ли узел корнем, ссылку на корень дерева, символьный путь к текущему узлу из корня дерева и итератор предков.
Код этого класса позволяет осуществлять основные манипуляции с элементами дерева для их замены, перестановки, обхода и доступа. Отдельные методы я приведу по мере надобности. Полный текст займёт много места. Его можно посмотреть/скопировать из исходников проекта.
Все узлы дерева могут быть либо вычислимыми, либо используемыми при разборе.
Узлы разбора включают в себя строковый узел, символьный узел и узел интервального значения. Они нужны для дополнения определённых метоструктур в дереве вроде функционала интегрирования, где надо указать интервал.
Вычислимые узлы — основные в результирующей структуре дерева. Они представляют все элементы, которые могут быть описаны в мат.выражении.
В их число входит:
- ComputedBracketNode — представляет блок скобок
- ValueNode — абстрактный класс, представляющий узел-значение. Его наследники:
— ConstValueNode — узел числового значения
— VariableValueNode — узел переменной (которая может быть и константой вроде pi, e, …) - FunctionNode — узел, представляющий объект-функцию
- FunctionalNode — узел, представляющий объект-функционал
- ОператорNode — абстрактный класс узла-оператора. Его наследники
— Простейшие мат.операторы +,-,*,/,^;
— Логические операторы ==, !, >,<, &&, ||;
— Оператор условия"<результат_работы_логического оператора>?" и совместно с ним используемый оператор выбора "<вариант_1>:<вариант_2>"
— Оператор, реализующий доступ к аргументу функции и используемый совместно с ним оператор доступа к имени аргумента функции.
Процесс построения дерева
Класс терма объявляет абстрактный метод GetSubTree, который позволяет из любого терма получить описываемое им поддерево. Процесс построения дерева начинается с вызова этого метода у сформированного из исходной строки блокового терма.
/// <summary>Получить корень поддерева выражений</summary> /// <param name="Parser">Парсер выражения</param> /// <param name="Expression">Математическое выражение</param> /// <returns>Корень поддерева</returns> public override ExpressionTreeNode GetSubTree(ExpressionParser Parser, MathExpression Expression) { Contract.Requires(Parser != null); Contract.Requires(Expression != null); Contract.Ensures(Contract.Result<ExpressionTreeNode>() != null); var separator = Parser.ExpressionSeparator; // фиксируем символ-разделитель выражений // Разбиваем последовательность элементов выражения на группы, разделённые симовлом-разделителем // Извлекаем из каждой группы корень дерева выражений и складываем их в массив var roots = Terms .Split(t => t is CharTerm && ((CharTerm)t).Value == separator) .Select(g => Parser.GetRoot(g, Expression)).ToArray(); if(roots.Length == 1) return roots[0]; // Если найден только один корень, то возвращаем его // Иначе корней найдено много ExpressionTreeNode argument = null; // объявляем ссылку на аргумент for(var i = 0; i < roots.Length; i++) // проходим по всем найденным корням { var root = roots[i]; ExpressionTreeNode arg; // Если очередной корень дерева if(root is FunctionArgumentNode) // - аргумент функции arg = root; // -- оставляем его без изменений else if(root is FunctionArgumentNameNode) // - узел имени аргумента // -- создаём новый именованный аргумент функции arg = new FunctionArgumentNode(root as FunctionArgumentNameNode); else if(root is VariantOperatorNode && root.Left is VariableValueNode) arg = new FunctionArgumentNode(((VariableValueNode)root.Left).Name, root.Right); else // - во всех остальных случаях arg = new FunctionArgumentNode("", root); // -- создаём аргумент функции без имени if(argument == null) argument = arg; // Если аргумент не был указан, то сохраняем полученный узел, как аргумент else // иначе argument = argument.Right = arg; // сохраняем полученный узел в правое поддерево аргумента } // Если аргумент не был выделен, то что-то пошло не так - ошибка формата if(argument == null) throw new FormatException("Не определён аргумент функции"); return argument.Root; // Вернуть корень аргумента }
Метод извлекает из передаваемого ему объекта мат.выражения символ, который разделяет выражения в блоке. По умолчанию установлен разделитель ‘;’ — точка с запятой.
Затем в Linq-последовательности весь массив вложенных термов разбивается на подмассивы по разделителю — символьному терму, содержащему символ-разделитель выражений. За это отвечает метод-расширение Split.
/// <summary>Разделить входной массив на подмассивы указанным методом</summary> /// <typeparam name="T">Тип элементов массива</typeparam> /// <param name="array">Разделяемый массив</param> /// <param name="Splitter">Метод, возвращающий истину, когда надо начать новый подмассив</param> /// <returns> /// Массив подмассивов элементов исходного массива, разделённый выбранными указанным методом элементами. /// Выбранные элементы в результат не входят. /// </returns> [NotNull] public static T[][] Split<T>([NotNull] this T[] array, [NotNull] Func<T, bool> Splitter) { Contract.Requires(array != null); Contract.Requires(Splitter != null); Contract.Ensures(Contract.Result<T[][]>() != null); var result = new List<T[]>(array.Length); var aggregator = new List<T>(array.Length); for(var i = 0; i < array.Length; i++) { var value = array[i]; if(Splitter(value) && aggregator.Count != 0) { result.Add(aggregator.ToArray()); aggregator.Clear(); } else aggregator.Add(value); } if(aggregator.Count != 0) result.Add(aggregator.ToArray()); return result.ToArray(); }
Для каждого из подмассива термов вызывается метод парсера GetRoot, который призван определить корень дерева этой группы термов. Затем все найденные корни объединяются в массив.
Метод GetRoot:
/// <summary>Метод извлечения корня дерева из последовательности элементов математического выражения</summary> /// <param name="Group">группа элементов математического выражения</param> /// <param name="MathExpression">Ссылка на математическое выражение</param> /// <returns>Корень дерева мат.выражения</returns> internal ExpressionTreeNode GetRoot([NotNull] Term[] Group, [NotNull] MathExpression MathExpression) { Contract.Requires(Group != null); Contract.Requires(MathExpression != null); Contract.Ensures(Contract.Result<ExpressionTreeNode>() != null); // Ссылка на последний обработанный узел дерева ExpressionTreeNode Last = null; for(var i = 0; i < Group.Length; i++) // в цикле по всем элементам группы { var node = Group[i].GetSubTree(this, MathExpression); // извлечь поддерево для текущего элемента группы // Если очередной элемент группы... if(Group[i] is NumberTerm) // ...очередной элемент число, то { //...если есть впереди ещё два элемента и прошла удачная попытка считать разделитель дробного числи и мантиссу if(i + 2 < Group.Length && NumberTerm.TryAddFractionPart(ref node, Group[i + 1], DecimalSeparator, Group[i + 2])) i += 2; //...то увеличить индекс текущей группы на два. } else if(Group[i] is BlockTerm) //...очередной элемент блок (со скобками) node = new ComputedBracketNode( // очередной узел дерева - это вычислимый блок new Bracket( //вид скобок: (((BlockTerm)Group[i]).OpenBracket), // копируем вид открывающей скобки ((BlockTerm)Group[i]).CloseBracket), // копируем вид закрывающей скобки node); //Внутри узел дерева //Проводим комбинацию текущего узла предыдущим узлом дерева Combine(Last, Last = node); // и назначаем текущий узел дерева предыдущим if(Last.IsRoot && Last is VariantOperatorNode && Last.Left is VariableValueNode) Last = new FunctionArgumentNameNode(((VariableValueNode)Last.Left).Name); OnNewNodeAdded(ref Last); } // Если ссылка на предыдущий узел отсутствует, то это ошибка формата if(Last == null) throw new FormatException(); return Last.Root; // вернуть корень дерева текущего элемента }
Здесь последовательно просматриваются входной массив термов выражения. Из каждого очередного терма выражения мы извлекаем корень его дерева (здесь возникает рекурсия). После чего надо проверить:
— если текущий терм целочисленный и он как минимум третий с конца массива, то пытаемся добавить к текущему узлу дробную часть.
/// <summary>Попытаться добавить дробное значение числа</summary> /// <param name="node">Узел выражения</param> /// <param name="SeparatorTerm">Блок разделитель</param> /// <param name="DecimalSeparator">Блок с целой частью числа</param> /// <param name="FrationPartTerm">Блок с дробной частью числа</param> /// <returns>Истина, если действие совершено успешно. Ложь, если в последующих блоках не содержится нужной информации</returns> public static bool TryAddFractionPart(ref ExpressionTreeNode node, Term SeparatorTerm, char DecimalSeparator, Term FrationPartTerm) { var value = node as ConstValueNode; if(value == null) throw new ArgumentException("Неверный тип узла дерева"); var separator = SeparatorTerm as CharTerm; if(separator == null || separator.Value != DecimalSeparator) return false; var fraction = FrationPartTerm as NumberTerm; if(fraction == null) return false; var v_value = fraction.Value; if(v_value == 0) return true; node = new ConstValueNode(value.Value + v_value / Math.Pow(10, Math.Truncate(Math.Log10(v_value)) + 1)); return true; }
Методу указывается символ-разделитель целой и дробной части десятичного числа, а также два следующих за текущим терма. Если второй терм — символьный и содержит символ-разделитель, а третий числовой, то узел заменяется на новый узел-константное значение
— Вторая проверка — если текущий терм блочный, то формируется узел-блок_скобок.
По завершении проверок выполняется метод, комбинирующий узел, созданный на предыдущем цикле с текущим:
/// <summary>Комбинация предыдущего и текущего узлов дерева</summary> /// <param name="Last">Предыдущий узел дерева (уже интегрированный в дерево)</param> /// <param name="Node">Текущий узел, который надо вставить в дерево</param> // ReSharper disable once CyclomaticComplexity public virtual void Combine([CanBeNull] ExpressionTreeNode Last, [NotNull] ExpressionTreeNode Node) { Contract.Requires(Node != null); if(Last == null) return; // Если предыдущий узел дерева не указан, возврат if(Node is CharNode) // Если текущий узел - символьный узел, то { Last.LastRightChild = Node; // просто назначить его самым правым дочерним return; } var operator_node = Node as OperatorNode; // представляем текущий узел в виде узла-оператора if(operator_node != null) // если текущий узел является оператором... { //Пытаемся получить оператор предыдущего узла: // пытаемся привести предыдущий узел к типу узла оператора // либо пытаемся привести родительский узел предыдущего узла к типу узла оператора var parent_operator = Last as OperatorNode ?? Last.Parent as OperatorNode; if(parent_operator != null) // Если получена ссылка не предыдущий узел-оператор (и текущий является оператором)... то { // Если левое поддерево предыдущего оператор пусто и родитель предыдущего оператора - тоже оператор // op <- устанавливаем предыдущим оператором родителя // | // op // / \ // null ? if(parent_operator.Left == null && parent_operator.Parent is OperatorNode) parent_operator = (OperatorNode)parent_operator.Parent; if(parent_operator.Left == null) // Если левое поддерево предыдущего оператора пусто... operator_node.Left = parent_operator; // устанавливаем предыдущий оператор в качестве левого поддерева текущего else if(parent_operator.Right == null) // Иначе если правое поддерево пусто parent_operator.Right = Node; // установить текущий оператор правым поддеревом предыдущего else // Иначе если конфликт приоритетов { var priority = operator_node.Priority; // извлекаем приоритет текущего узла // Если приоритет текущего оператора меньше, либо равен приоритету предыдущего if(priority <= parent_operator.Priority) { // то надо подниматься вверх под дереву до тех пор parent_operator = (OperatorNode)parent_operator.Parents // пока встречаемые на пути операторы имеют приоритет выше приоритета текущего оператора .TakeWhile(n => n is OperatorNode && priority <= ((OperatorNode)n).Priority) // взять последний из последовательности .LastOrDefault() ?? parent_operator; // если вернулась пустая ссылка, то взять предыдущий оператор // На текущий момент предыдущий оператор имеет приоритет выше приоритета текущего оператора if(parent_operator.IsRoot) // Если предыдущий оператор - корень дерева // Если приоритет оператора в корне дерева больше, либо равен приоритету текущего оператора if(priority <= parent_operator.Priority) // Присвоить левому поддереву текущего оператора предыдущий operator_node.Left = parent_operator; else // Иначе если предыдущий оператор не корень { var parent = parent_operator.Parent; // сохранить ссылку на родителя предыдущего оператора parent.Right = Node; // записать текущий оператор в качестве правого поддерева operator_node.Left = parent_operator;// записать предыдущий оператора левым поддеревом текущего } } else //если приоритет текущего оператора больше приоритета предыдущего { // то надо спускаться в правое поддерево до тех пор parent_operator = (OperatorNode)parent_operator.RightNodes // пока встречаемые на пути операторы имеют левые поддеревья и приоритет операторов меньше текущего .TakeWhile(n => n is OperatorNode && n.Left != null && ((OperatorNode)n).Priority < priority) // взять последний из последовательности .LastOrDefault() ?? parent_operator; // если вернулась пустая ссылка, то взять предыдущий оператор // На текущий момент предыдущий оператор имеет приоритет ниже приоритета текущего оператора var right = parent_operator.Right; // сохранить правое поддерево предыдущего оператора parent_operator.Right = Node; // в правое поддерево предыдущего оператора попадает текущий operator_node.Left = right; // в левое поддерево текущего оператора записывается сохранённое правое } } } else // Если предыдущий узел не является оператором { var parent = Last.Parent; var is_left = Last.IsLeftSubtree; var is_right = Last.IsRightSubtree; operator_node.Left = Last; // записать предыдущий узел левым поддеревом текущего if(is_left) parent.Left = operator_node; else if(is_right) parent.Right = operator_node; } return; // возврат } // Если текущий узел оператором не является if(Last is OperatorNode) // если предыдущий узел является оператором { Last.Right = Node; // добавить текущий в правое поддерево предыдущего return; // возврат } // Если ни текущий не предыдущий узлы не являются операторами //Если предыдущий узел был числом, или предыдущий узел был скобками и текущий - скобки if(Last is ConstValueNode || (Last is ComputedBracketNode && Node is ComputedBracketNode)) { //Сохраняем ссылку на родителя предыдущего узла var parent = Last.Parent; if(parent != null) // если родитель есть // в правое поддерево родителя записываем оператор перемножения предыдущего узла и текущего parent.Right = new MultiplicationOperatorNode(Last, Node); else // если предыдущий узел был узлом дерева // создаём новый узел-оператор умножения предыдущего узла и текущего, который становится новым корнем дерева new MultiplicationOperatorNode(Last, Node); return; // возврат. } Last.Right = Node; }
Это один из центральных методов. Он, в соответствии с логикой создаваемого дерева мат.выражения, присоединяет новые узлы к уже существующему, учитывая узлы-операторы (их приоритеты). Безусловно, метод требует рефакторинга по причине размера объёмов кода в нём. Логика его работы отражена в комментариях в коде.
Когда комбинация двух узлов выполнена проводится последняя проверка: если обработанный узел — корень дерева и узел является узлом вариантов выбора, и при этом в его левом поддереве узел-переменная <Переменная>:<вариант_2>, то его следует рассматривать как узел аргумента функции <имя_аргумента>:<значение_аргумента>. При этом именем аргумента становится имя переменной.
По завершении итерации в объекте-парсере генерируется событие NewNodeAdded, в которое передаётся созданный узел для внешней обработки его пользователем. При этом узел передаётся по ссылке, так что существует возможность полностью переопределить создаваемое дерево.
После того, как для группы термов парсером было создано поддерево и в методе GetSubTree блокового терма все корни таких поддеревьев были объединены в массив, метод проверяет:
- если массив содержит всего один элемент, то он и возвращается в качестве результата (это тривиальный случай)
- если корней много, то каждый из них упаковывается в узел аргумента функции FunctionArgumentNode ( в его правое поддерево), а в левое поддерево цепляется следующий аргумент.
Структура дерева матвыражения
Таким образом формируемое дерево отвечает следующим правилам:
- Узлы операторов содержат свои операнды в левом и правом поддеревьях
- Узлы значений (переменные, числовые значения) должны быть листьями дерева (но не обязательно)
- Узлы блоков скобок хранят значение в левом поддереве
- Узлы функций имеют пустое левое поддерево. В правом поддереве хранится узел первого аргумента.
- Узел аргумента функции в левом поддереве хранится либо корень дерева аргумента, либо узел имени аргумента. В правом поддереве хранится ссылка на следующий аргумент функции;
- Узел имени аргумента — в левом поддереве хранится невычислимый строковый узел со строкой-именем, а правом поддереве хранится корень дерева-аргумента.
- Узел функционала является листом. Параметры и выражение хранятся отдельно (что позволяет более гибко переопределять логику работы с ними).
Сами функции и функционалы выделены в отдельные объекты.
Дерево построено. В процессе построения были созданы в том числе узлы переменных и функций. Каждый такой узел был создан соответствующим ему термом прямым вызовом конструктора узла соответствующего типа:
/// <summary>Строковый элемент выражения</summary> class StringTerm : Term { /// <summary>Имя строкового элемента</summary> [NotNull] public string Name => f_Value; /// <summary>Новый строковый элемент</summary> /// <param name="Name">Имя строкового элемента</param> public StringTerm([NotNull] string Name) : base(Name) { Contract.Requires(!string.IsNullOrEmpty(Name)); } /// <summary>Поддерево элемента, состоящее из узла-переменной</summary> /// <param name="Parser">Парсер</param> /// <param name="Expression">Математическое выражение</param> /// <returns>Узел дерева с переменной, полученной из Expression.Variable[Name]</returns> public override ExpressionTreeNode GetSubTree(ExpressionParser Parser, MathExpression Expression) => new VariableValueNode(Expression.Variable[Name]); } /// <summary>Блок определения функции</summary> sealed class FunctionalTerm : FunctionTerm { /// <summary>Параметры оператора</summary> [NotNull] public BlockTerm Parameters { get; set; } /// <summary>Инициализация блока комплексного оператора</summary> /// <param name="Header">Заголовок блока</param> /// <param name="Body">Тело блока</param> public FunctionalTerm([NotNull] FunctionTerm Header, [NotNull] BlockTerm Body) : base(Header.Name, Body) { Contract.Requires(Header != null); Contract.Requires(Body != null); Parameters = Header.Block; } /// <summary>Получить поддерево комплексного оператора</summary> /// <param name="Parser">Парсер</param> /// <param name="Expression">Математическое выражение</param> /// <returns>Узел комплексного оператора</returns> public override ExpressionTreeNode GetSubTree(ExpressionParser Parser, MathExpression Expression) => new FunctionalNode(this, Parser, Expression); public override string ToString() => $"{Name}{Parameters}{Block}"; }
При этом, при создании узел требует от выражения коллекцию переменных/функций что бы извлечь из неё по имени нужный объект-переменную/функцию.
/// <summary>Инициализация нового функционального узла</summary> /// <param name="Term">Выражение функции</param> /// <param name="Parser">Парсер выражения</param> /// <param name="Expression">Математическое выражение</param> internal FunctionNode(FunctionTerm Term, ExpressionParser Parser, MathExpression Expression) : this(Term.Name) { var arg = Term.Block.GetSubTree(Parser, Expression); if(!(arg is FunctionArgumentNode)) if(arg is FunctionArgumentNameNode) arg = new FunctionArgumentNode((FunctionArgumentNameNode)arg); else if(arg is VariableValueNode) arg = new FunctionArgumentNode(null, arg); else if(arg is VariantOperatorNode && arg.Left is VariableValueNode) arg = new FunctionArgumentNode(((VariableValueNode)arg.Left).Name, arg.Right); else arg = new FunctionArgumentNode(null, arg); Right = arg; //Определение объекта-функции из выражения Function = Expression.Functions[Name, ArgumentsNames]; }
После создания дерева в объекте мат.выражения коллекции переменных и функций будут содержать перечни использовавшихся объектов. Но их значения будут пусты. Часть переменных необходимо классифицировать, как известные парсеру константы (перенести их в соответствующую коллекцию, объектам-функциям надо определить реализующие их делегаты.
Инициализация дерева
После создания «сырого» дерева мат.выражения его надо заполнить значениями переменных и функций. Метод Parse парсера последовательно вызывает два метода ProcessVariables и ProcessFunctions передавая в них созданное «сырое» дерево.
Метод обработки переменных:
/// <summary>Обработка переменных</summary> /// <param name="Expression">Обрабатываемое математическое выражение</param> internal void ProcessVariables([NotNull] MathExpression Expression) { Contract.Requires(Expression != null); var tree_vars = Expression.Tree.Root.GetVariables().ToArray(); Expression.Variable .Where(v => !tree_vars.Contains(v)) .ToArray() .Foreach(v => Expression.Variable.Remove(v)); foreach(var variable in Expression.Variable.ToArray()) { if(f_Constans.ContainsKey(variable.Name)) { Expression.Variable.MoveToConstCollection(variable); variable.Value = f_Constans[variable.Name]; } OnVariableProcessing(variable); } }
Его задача — обойти дерево, найти все узлы-переменные и извлечь из них использованные в них объекты-переменные. После чего надо из коллекции переменных мат.выражения удалить всё, что не используется в дереве.
После этого для каждой переменной в дереве проверяется — не содержится ли её имя в коллекции известных констант парсера. Если да, то она изымается из коллекции переменных мат.выражения, заносится в коллекцию констант мат.выражения, инициализируется значением, известным парсеру и в ней выставляется флаг, что она является константой.
После этого для неё в парсере вызывается событие обнаружения новой переменной. При обработке этого события пользователь парсера может переопределить значение этой переменной, либо изменить сам объект переменной.
Второй метод ProcessFunctions заполняет делегатами известные мат.выражению функции:
/// <summary>Обработка функций</summary> /// <param name="Expression">Обрабатываемое математическое выражение</param> [SuppressMessage("ReSharper", "CyclomaticComplexity")] internal void ProcessFunctions([NotNull] MathExpression Expression) { Contract.Requires(Expression != null); foreach(var function in Expression.Functions) switch(function.Name) { case "Sin": case "SIN": case "sin": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Sin); break; case "COS": case "Cos": case "cos": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Cos); break; case "TAN": case "Tan": case "tan": case "tn": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Tan); break; case "ATAN": case "ATan": case "Atan": case "atan": case "atn": case "Atn": if(function.Arguments.Length == 1) function.Delegate = new Func<double, double>(Math.Atan); else if(function.Arguments.Length == 2) function.Delegate = new Func<double, double, double>(Math.Atan2); else goto default; break; case "Atan2": case "atan2": if(function.Arguments.Length != 2) goto default; function.Delegate = new Func<double, double, double>(Math.Atan2); break; case "CTG": case "Ctg": case "ctg": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(x => 1 / Math.Tan(x)); break; case "Sign": case "sign": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(x => Math.Sign(x)); break; case "Abs": case "abs": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Abs); break; case "Exp": case "EXP": case "exp": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Exp); break; case "Sqrt": case "SQRT": case "√": case "sqrt": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Sqrt); break; case "log10": case "Log10": case "LOG10": case "lg": case "Lg": case "LG": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Log10); break; case "loge": case "Loge": case "LOGe": case "ln": case "Ln": case "LN": if(function.Arguments.Length != 1) goto default; function.Delegate = new Func<double, double>(Math.Log); break; case "log": case "Log": case "LOG": if(function.Arguments.Length != 2) goto default; function.Delegate = new Func<double, double, double>(Math.Log); break; default: var f = OnFunctionFind(function.Name, function.Arguments); if(f == null) throw new NotSupportedException($"Обработка функции {function.Name} не поддерживается"); function.Delegate = f; break; } }
Если имя функции находится среди вариантов оператора case, то при совпадении требуемого функции числа аргументов ей назначается делегат, который будет вычислять её значение. Если функция не определена, то делегат определяется, как результат генерации события обнаружения неизвестной функции. При этом пользователь может определить в реакции на это событие требуемое по имени и количеству (и именам) аргументов требуемый делегат.
На этом генерация мат.выражения завершается.
Использование
Предположим, что у нас стоит задача вычислить интеграл функции A*cos(2*x)/pi+G(x/2) делёный на А и + 1, где G(x)=2cos(x). При А, скажем, равной 5. И интеграл надо взять с шагом 0,05.
var parser = new ExpressionParser(); parser .FindFunction += (s, e) => { if(e.SignatureEqual(name: "G", ArgumentsCount: 1)) e.Function = new Func<double, double>(x => 2 * Math.Cos(x)); }; var expr = parser.Parse(@"Int[x=-10..10;dx=0.05]{A*cos(2x) + G(x/2)}/A + 1"); expr.Variable["A"] = 5; var y = expr.Compute(); //y = 0.30928806858920344 var f = expr.Compile(); var y2 = f(); //y = 0.30928806858920344
Заключение
Учитывая получившийся объём статьи я ставлю здесь… не точку, а точку с запятой. В результате вышеизложенного удалось:
- Получить общее представление о методе решения поставленной задачи;
- Сформировать объектную модель парсера мат.выражений, самого мат.выражения и его дерева;
- Создать эффективный метод разбора строки мат.выражения на логические составляющие;
- Создать эффективный метод построения дерева мат.выражения с учётом особенностей использования скобок, приоритетов операторов и специальных конструкций (функционалов);
- Обеспечить контроль над разными этапам обработки входных данных парсером на основе системы событий;
- Добавить возможность расширения функциональности.
Чего не удалось описать в данной статье:
- Логику работы переменных (их типы и методы их получения и последующей замены);
- Структуру коллекций переменных, констант, функций, участвующих в работе мат.выражения;
- Метод расчёта значения мат.выражения путём обхода его дерева;
- Метод компиляции дерева мат.выражения в делегат.
Чего не удалось пока в реализации самого парсера:
- Реализовать методы оптимизации дерева мат.выражения;
- Убрать костыли из ряда мест;
- Добавить проверки на предмет соответствия входных данных формату мат.выражения;
- Собственно, очертить границы этого формата;
- Повысить покрытие кода модульными тестами;
- Провести сравнительные исследования быстродействия как этапов разбора, так и этапов вычисления.
В целом, работа над этим кодом к сожалению носит фоновый характер и длиться уже пару лет, но на данном этапе он уже решает поставленные перед ним задачи. Хотя в теперешнем виде пускать его в продакшен нельзя.
Полные исходные коды можно найти тут.
ссылка на оригинал статьи https://habrahabr.ru/post/281495/
Добавить комментарий