Парсер математических выражений

Спасибо всем! Статья набрала необходимое число плюсов и автор к нам присоединяется! Вот и он: elw00d
Представляю вниманию товарищей-дотнетчиков библиотечку собственного написания, с помощью которой можно легко обращаться с несложными математическими функциями, переводя их из строковой формы инфиксной записи в обработанное представление, составленное в постфиксной нотации, и обратно. Для чего это может понадобиться?

К примеру, можно написать приложение, которое принимает ввод функции пользователем в виде строки, анализирует корректность синтаксиса, вычисляет его значение в указанных точках, оптимизирует введенное выражение, минимизируя количество операций, требуемых для вычисления, и может выдавать результат в виде строки, представляющей собой корректное строковое представление оптимизированной функции. В качестве конкретных применений можно отметить различные специализированные калькуляторы (в том числе, построенные наподобие программируемых), приложения, используемые для построения графиков или других отчетов, требующие задания начальных функций, или как оригинальное средство для построения защиты от спама / автоматических регистраций.

А началось все с того, что я увидел написанное каким-то суперпрограммистом приложение-пособие для лабораторной работы по численным методам оптимизации. Ввод исходной функции в ней был организован следующим оригинальным образом: пользователь (== студент) вводил функцию, а программа генерировала исходник и запускала лежащий рядом компилятор Delphi для получения DLL. Затем появившаяся DLL подгружалась в программу и по функции строился график. Немного посмеявшись над находчивостью разработчика, я подумал — а как было бы можно организовать аналогичный функционал без применения такого толстого “плагина”, как компилятор Delphi? В результате загорелся идеей написать свой парсер для таких задач. Вот что из этой идеи получилось.

На данный момент реализован и протестирован следующий функционал:

1. Анализ строк выражений, составленных из стандартных математических операторов +,-,/,*, функций
sin, cos, скобок. Поддерживаются переменные с любыми именами, которые приемлемы для синтаксического
анализатора (состоят из букв и цифр, должны начинаться с буквы).

Примером такого выражения может быть строка
“-4+5.5*sin(1/3)*(2+5)”.

Для вычисления этого выражения необходимо написать код:

1. // Преобразуем исходную строку в скомпилированный вид
2. PreparedExpression preparedExpression = ToolsHelper.Parser.Parse("-4+5.5*sin(1/3)*(2+5)");
3. CompiledExpression compiledExpression = ToolsHelper.Compiler.Compile(preparedExpression);
4. // Создаем список переменных, который будет использован калькулятором при вычислении
5. // В данном примере он пуст, поскольку в исходном выражении нет переменных
6. List<VariableValue> variables = new List<VariableValue>();
7. // Получаем результат вычисления функции
8. double res = ToolsHelper.Calculator.Calculate(compiledExpression, variables);

* This source code was highlighted with Source Code Highlighter.

2. Возможность быстро добавлять необходимые функции и операторы путем простого конфигурирования xml-конфига библиотеки. Поддерживаются функции с несколькими аргументами, например, можно определить собственную сигнатуру функции myfunc, принимающую 2 параметра. В выражении её можно будет вызвать так: “myfunc(12, x)”. Здесь x — переменная, её значение необходимо передать калькулятору при вычислении.

Также поддерживаются операторы с более чем двумя операндами (в качестве примера в библиотеке уже определен тернарный оператор? :, который выдает значение второго или третьего операнда, в зависимости от знака первого операнда.

Все операции (операторы и функции) характеризуются сигнатурой (символьным представлением, по которому ищутся вхождения в исходной строке), приоритетом, количеством операндов и классом-вычислителем, который будет использоваться для вычисления этой операции. Класс-вычислитель реализует интерфейс

1. public interface IOperationCalculator {
2.  /// <summary>
3.  /// Returns a result of operation called.
4.  ///</summary>
5.  double Calculate(params double[] parameters);
6.  }
7. }

* This source code was highlighted with Source Code Highlighter.

Таким образом, для того, чтобы добавить новый оператор или функцию, нужно определить для этой функции класс-вычислитель и добавить запись в Operations.xml вида

1. <operation name="sinus" operands="1" kind="function">
2.  <signatures>
3.   <signature number="1" value="sin" />
4.  </signatures>
5.  <calculator type="ELW.Library.Math.Calculators.Standard.CalculatorSinus, ELW.Library.Math" />
6. </operation>

* This source code was highlighted with Source Code Highlighter.

При инициализации библиотека подгрузит типы, необходимые для обработки добавленной функции, и сопоставит этой операции экземпляр выбранного класса-вычислителя. При вычислении будет вызвана соответствующая функция Calculate() с переданными параметрами.

3. Возможность оптимизировать скомпилированное выражение за счет предвычисления констант. К примеру, выражение (3+5)/x можно привести к виду 8/x. Полученное выражение можно использовать в вычислениях вместо исходного, и даже вывести пользователю как слегка упрощенный вариант его функции. Алгоритм оптимизации можно улучшить, добавив новые возможности (если кто-нибудь, конечно, загорится такой идеей).

4. Возможность контролировать промежуточные этапы преобразования выражений. От строки к последовательности сигнатур и операндов, далее к обратной польской записи из операндов и операций, и обратно. Вообще возможные переходы отражены в следующей диаграмме:

String и Double – примитивные типы, с них начинается обработка выражений, ими же обычно и заканчивается.
Prepared Expression – состоит из набора элементов, каждый из которых представляет собой либо константу, либо имя переменной, либо разделитель, такой, как скобка или запятая, или строковую сигнатуру операции. К примеру, выражение (a+b)/3 будет представлять собой набор из ‘(‘, “a”, “+”, “b”, ‘)’, “/”, 3. Число 3 здесь уже не в строковой форме, а Double.

Compiled Expression – набор операндов и операций над ними в постфиксной нотации, то есть именно то, чем питается калькулятор. Представляет собой массив из операндов (либо константа, либо имя переменной) и операций (либо оператор, либо функция). Calculator, получая на вход это выражение, работает с ним по простому алгоритму, по очереди извлекая операнды и информацию об операциях и производя последовательные вычисления в стеке операндов.

5. Собирается как под .NET Framework 3.5, так и под .NET 2.0. Прилагаются nant скрипты для автоматизации
сборки, можно использовать совместно с Visual Studio.

Скриншот примера из библиотеки:

Эпилог.

Пока что возможности не слишком велики, однако достаточны для того, чтобы поиграться с изобретением собственных операторов, с изменением приоритета вычислений операторов, или для примитивной оптимизации математических выражений.

Скачать исходники библиотеки + тестовое приложение

Материалы для размышления:

ru.wikipedia.org/wiki/Обратная_польская_запись
msdn.microsoft.com/ru-ru/library/ms139741.aspx