суббота, 4 ноября 2017 г.

muParser

Вычисление строковых выражений

Юрий “yurembo” Язев

Не так давно передо мной встала задача вычисления математических выражений. Конечно, обычно записанное выражения вида: a = (4 + 6) – 4 * 2 вычисляется в 2 счета стандартными средствами любого языка программирования. Однако, когда выражение принимает вид: “a = (4 + 6) – 4 * 2”, то есть передается, как строка, ситуация усложняется. Никакой язык программирования не понимает выражения внутри строки. Такая задача распространена и достаточно часто встречается. Например, пользователь вводит в программу выражение целиком, или приложение читает выражение из файла, строки ввода или другого источника.

Первая приходящая в этом случае идея – написать свой парсер, который бы разбирал строку на операторы, операнды и осуществлял вычисления. И это вполне возможно. Между тем, стоит учесть большое количество математических операций, кроме вездесущих: +, –, *, / в математике есть: cos, sin, tan, asin, acos, log, sqrt, exp, etc., плюс логические операции: and, or, ==, <= и великое множество других. Прибавь к этому скобки и порядок вычисления. Из всего этого задача написания собственного парсера теперь не кажется простой. Еще к этому стоит прибавить необходимость удовлетворительной скорости парсинга, иначе перебор строк будет занимать долгое время.

Компиляция библиотеки и подключение ее к проекту


Решение – воспользоваться готовой библиотекой для парсинга математических выражений. Сделав небольшой ресерч, я остановил свой выбор на muParser. Во-первых, muParser – это проект с открытым исходным кодом, он обладает высокопроизводительным парсером для разбора строк и создания выражений, учитывая, как стандартные математические функции, так и пользовательские; в процесс вычисления можно добавить кастомные переменные и константы. Библиотека написана на C++, компилируется с любым современным компилятором. Имеет обертки для C и C#. Но последнее нам, в данном случае, не особо интересно, потому что мы будем использовать C++.

Давай откомпилируем либу из исходников, подключим ее к новому проекту, разберемся в ее возможностях более подробно и напишем  примерчик. muParser хоститься на GitHub, кроме того у либы есть своя страничка. Скачай с GitHub репозиторий muParser, распакуй его в удобный каталог. В подкаталоге build открой подпапку msvc2013. Я использую Visual Studio 2015, но проблем не обнаружил. В текущей папке открой решение muparser.sln. Согласись на обновление библиотек. В результате откроются 3 проекта: собственно, muparser, example1, example2, активным из которых будет первый. Из ниспадающего списка цели компиляции выбери Release Static. Я решил использовать статичную линковку в итоговом проекте, если у тебя другие планы, заюзай динамическую – Release DLL. Построй решение. Вместе с muparser будет скомпилирован example1. Можешь запустить последний и посмотреть его вывод. Кроме того, это приложение позволяет вводить любые математические выражения и получать соответствующие результаты. В подпапке lib будет создана итоговая статическая либа – muParser32.lib.

Следующим действием мы подключим либу к нашему новому проекту. Создай в студии новое консольное приложение. С ним удобнее упражняться.


Параметры создания проекта можно оставить по умолчанию.


Надо подключить muParser к нашему проекту. Открой свойства проекта. В ниспадающем списке Configuration выбери All Configuration. Далее добавь пути к папкам с заголовочными файлами muparser и библиотечными файлами (в пункте VC++ Directories). 


Разверни свиток Linker перейди на пункт Input. В списке справа строку Additional Dependencies дополни именем подключаемой библиотеки: muparser32.lib; (перед Additional Dependencies). Щелчком по кнопке OK окно можно закрыть. Не забудь из ниспадающего списка цели проекта выбрать Release, поскольку у нас релизная библиотека. Если тебе понадобится дебажный проект, тогда надо собрать дебажную версию либы. На этом настройка проекта окончена.

Ознакомление с функционалом muParser


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

#include "stdafx.h"
#include <iostream>
#include "muParser.h"

// Function callback
double MySqr(double a_fVal)
{
    return a_fVal*a_fVal;
}

// main program
int main(int argc, char* argv[])
{
    using namespace mu;

    try
    {
        double fVal = 1;
        Parser p;
        p.DefineVar(L"a", &fVal);
        p.DefineFun(L"MySqr", MySqr);
        p.SetExpr(L"MySqr(a)*_pi+min(10,a)");

        for (std::size_t a = 0; a < 100; ++a)
        {
            fVal = a;  // Change value of variable a
            std::cout << p.Eval() << std::endl;
        }
    }
    catch (Parser::exception_type &e)
    {
        std::cout << e.GetMsg().c_str() << std::endl;
    }
    return 0;
}

Это стандартный пример с официальной страницы muParser, немного дополненный для возможности компиляции в Visual Studio 2015. Центральное место занимает объект класса Parser. Собственно, с его помощью выполняются все действия по инициализации и вычислению выражения. Вначале в программе определяется функция обратного вызова MySqr, которая будет использована в вычислении. Затем, уже в функции main() после определения переменной fVal, значение которой так же использующееся в вычислении, объявляется объект Parser пространства имен mu. Так как мы создали его в стеке, нам не понадобится удалять его, с другой стороны, при его создании/удалении в куче нам послужат new/delete. 

При вычислении строкового выражения математический аппарат muParser работает в своем пространстве, которое содержит константы, переменные, функции и выражения. Чтобы они там оказались, предварительно их надо туда добавить. Для этого служит внушительный набор функций и методов. Чтобы добавить в математический аппарат переменную, надо вызвать метод DefineVar объекта класса Parser:

p.DefineVar(L"a", &fVal);

Как видно в примере, метод принимает 2 параметра: имя переменной, используемой в аппарате – строкового типа mu:string_type. Этот тип muPaser соответствует стандартному строковому типу широких символов, от чего предваряется литерой L. Вторым параметром передается указатель на ранее объявленную и инициализированную переменную в C++-коде. muParser поддерживает переменные только типа double. Между тем, математический аппарат работает со своим универсальным типом данных: value_type, который соответствует числу с плавающей точкой единичной или двойной точности.
Константы внутри математического аппарата могут быть двух типов: double и string. Значения констант, в отличие от значений переменных, хранятся в байт-коде и не ссылаются на значения извне аппарата. Чтобы добавить в аппарат константу первого типа, участвующую в вычислении, надо вызвать метод DefineConst с теми же двумя параметрами, что в предыдущем случае. Для добавления константы типа string, надо вызвать метод DefineConst, он принимает строку – имя константы и строку – ее значение.
Кроме добавления переменных и констант в аппарат, их можно оттуда удалить. Для удаления именованной переменой достаточно вызывать метод RemoveVar, который принимает название удаляемой переменной. Чтобы удалить из аппарата все переменные надо вызвать метод ClearVar. С другой стороны, ClearConst удаляет все константы.
Для объявления пользовательской функции достаточно вызвать метод DefineFun с двумя параметрами: именем функции, по которому она будет вызываться внутри аппарата, и именем ранее объявленной в C++-коде функции:

p.DefineFun(L"MySqr", MySqr);

MySqr – ранее объявленная функция для вычисления квадрата параметра:

double MySqr(double a_fVal)
{
    return a_fVal*a_fVal;
}

После определения переменных, констант и функций внутри аппарата, можно в него передать выражение для вычисления. Это осуществляется с помощью метода: SetExpr:

p.SetExpr(L"MySqr(a)*_pi+min(10,a)");

Он принимает один параметр – строковое выражение, где могут быть использованы константы, переменные и функции, объявленные в аппарате ранее.

Когда все готово для вычисления математического выражения, для получения его результата достаточно вызвать метод Eval объекта класса Parser. Он ничего не принимает. В зависимости от того, какое выражение задано, в итоге, метод возвращает или значение типа double, или указатель на массив значений типа value_type. В первом случае, это стандартное выражение, возвращающее один результат, такое, как представлено выше. Во втором случае, это несколько выражений, записанных через запятую, например: sin(x),y+x,x*x. То есть каждое из них выдает свой результат, из чего формируется массив значений value_type, указатель на который возвращается перегруженной функцией Eval.

Приложение в работе

Как видно в примере выше: в математическом аппарате может возникать свой ряд исключений, принадлежащих типу Parser::exception_type. У этого типа существуют функции для получения различных сведений о произошедшей проблеме:
  • exception.GetMsg() – возвращает сообщение об ошибке;
  • exception.GetExpr() – возвращает текущую формулу, в которой произошло исключение;
  • exception.GetToken() – возвращает лексему, соответствующую данной ошибке;
  • exception.GetPos() – возвращает позицию в текущей формуле;
  • exception.GetCode() – возвращает код ошибки;

После того, как математический аппарат будет укомплектован, во время компиляции C++-кода, сформированное в muParser выражение будет преобразовано в byte-код. Дальнейшие вычисления производятся не с помощью строк, а в байт-коде. От этого вычисление выражения в итоговой программе выполняется очень быстро. Если при следующей компиляции выражение будет изменено, то байт-код будет перекомпилирован.

Комментариев нет:

Отправить комментарий