Backend developer
0,1
рейтинг
25 января 2009 в 00:40

Разработка → Парсер математических выражений

.NET*
Спасибо всем! Статья набрала необходимое число плюсов и автор к нам присоединяется! Вот и он: 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. Возможность контролировать промежуточные этапы преобразования выражений. От строки к последовательности сигнатур и операндов, далее к обратной польской записи из операндов и операций, и обратно. Вообще возможные переходы отражены в следующей диаграмме:
image
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.

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

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

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

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

ru.wikipedia.org/wiki/Обратная_польская_запись
msdn.microsoft.com/ru-ru/library/ms139741.aspx
Александр @NeonXP
карма
34,3
рейтинг 0,1
Backend developer
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (34)

  • +3
    А чего не в песочнице? Он бы так еще и кармы поднабрал.
    • 0
      Мы давно уже собирались так опубликовать.
      • +2
        Какой в этом смысл? В песочнице за эту статью автор практически сразу получит инвайт, не дожидаясь +50-ти, и тут же её сам от своего имени и опубликует, за что получит заслуженные плюсы.
  • –5
    надо дать инвайт человеку, может еще что хорошее напишет
  • 0
    А ссылку на исходники?
    • +1
      Добавил. Спасибо за примечание.
      • +1
        Поглядел одним глазом на код. Весьма неплохо. Правда местами проскакивает разный coding convention — иногда поля в классах имеют вотТакие имена, а иногда _ВотТакие.
        У меня только вопрос возник. У вас есть класс CompiledExpressionItem, который то константа, то операция, то переменная. Почему не сделать его абстрактным и не унаследовать от него три отдельных класса для каждой из вышеупомянутых сущностей? ИМХО так более правильно с точки зрения ООП. Все эти три сущности, должны выполнять два действия — возвращать свое значение (константа — константу, переменная свое значение, операция или функция — результат выполнения) и свое написание. Собственно этих двух методов достаточно для базового класса.
        То же касается и PreparedExpressionItem, за исключением того, что там еще есть тип Delimiter, что, как мне кажется, ошибка дизайна — уж слишком у вас compiled и prepared похожи. Есть повод подумать о рефакторинге.
        А вообще красиво, продолжайте в том же духе.
        • 0
          Ответ от автора статьи:

          Насчет выделения базового абстрактного класса — да, такой путь вполне возможен как рефакторинг, приводящий к более прозрачному дизайну. Но в конкретном случае возникает вопрос — какой интерфейс должен быть у такого класса, скажем, BaseCompiledExpressionItem? метод наподобие abstract object GetAggregatedObject() не очень подходит в силу необходимости последующего кастинга к конкретному типу (double const или string variableName). Подумаю на досуге )
          Compiled и Prepared действительно похожи, но только внешне. Внутренне они представляют совершенно разные сущности, т.к. являются контейнерами для разных по смыслу объектов.
          Имена с подчеркивания _ я использую очень редко, в данном случае это было сделано для того, чтобы показать, что это свойство может быть преобразовано в autoproperty. Но из соображений совместимости с .Net 2.0 оставлю пока так.
          А вообще, спасибо за ценные замечания.
  • +2
    Интересно, что совпало с этим постом.
    • +3
      Это чистейшая случайность. Мы давно хотели опубликовать. Только сегодня закончили статью. А ту заметили после того как опубликовали.
  • +5
    [мигающий кислотными цветами баннер]
    Поздравляем, вы написали миллион первый парсер выражений, нажмите сюда для получения выигрыша!
    [/мигающий кислотными цветами баннер]
  • +2
    Ой, ностальжи… Помнится, когда надо было освоить синтаксис С#, я как раз такую же задачу реализовывал: разбор строки, проверку валидности и расчёт её. Несколько часов и полное удовлетворение от результата.
  • +3
    Ой, а я тоже подобную штуку написал не так давно! Во флэше на AS 3.0. И встроил в прогу, которая умеет строить графики, теперь ей школьники в контакте пользуются:)

    Умеет класс-парсер чуточку побольше:
    — поддерживает огромное количество функций, причем функции могут быть многих переменных, а также константы и аргументы;
    — умеет проводить качественный анализ ошибки ввода, с указанием места, где была произведена ошибка и давать пояснение к ней (на разных языках);
    — умеет форматировать исходную формулу (удалять пробелы, менять регистр элементов и тд);
    — умеет оптимизировать участки формулы, в которых не содержатся аргументы формулы;
    — каждый объект класса использует общие для всех (статические) функции, константы, но есть возможность задавать локальные функции, константы и аргументы (т.е. туда по сути можно «обучить» любым формулам). После разбора форулы (а он проходит автоматически, после смены входной строки) можно, передавая массив значений аргументов, получать результаты вычисления выражения.
    В той проге, ссылку на которую я дал, не весь функционал виден, потому что я писал его на будущее себе же, а GUI состряпал на скорую руку:)

    Собираюсь к своему модулю документацию написать в ближайшем будущем и сорцы выложить куда-нибудь, если кому-то интересным покажется то, о чем я сейчас написал:)
    • 0
      Мне приложение понравилось, и не понятно к чему тут минусы.
    • 0
      да и сорцам очень был бы рад! Спасибо!
    • 0
      Отлично, спасибо!
  • +2
    Статья хорошая, но однозначно надо в песочницу, зря что ли делали её?
  • +4
    Спасибо всем откликнувшимся и отдельно NeonXP )
    // по традиции
    Console.WriteLine(«Hello, habr»);
    • 0
      И с первым минусом!
  • +1
    У вас есть генерация IL-кода из выражения?
    • +1
      Нет, это же не компилятор в MSIL. Но эта возможность реализуема, если прикрутить генерацию IL по заданному CompiledExpression. Можно посмотреть PostSharp, там вроде бы есть такой функционал.
      • +1
        Через Emit можно генерить IL код в программе и тут же его использовать. То есть можно классы и методы создавать на лету.
  • +1
    Код написан неплохо, но дизайн кода… overdeveloped, имхо. Ничего страшного, конечно, в этом нет, первая версия — как правило, жуткий прототип-франкенштейн слепленный из того, что было.

    Видео по теме: «The Clean Code Talks — Inheritance, Polymorphism, & Testing», совсем по теме начинается с 07:43.
    • +1
      Я старался сделать код таким, чтобы он одновременно был не слишком сложен в использовании и универсален в смысле возможности добавления новых операций. Возможно, с первого взгляда кажется сложноватым, но спасибо за отзыв, есть над чем подумать. )
  • +1
    Есть простой способ добавить в свою программу поддержку макросов или функций — через Microsoft.CSharp.CSharpCodeProvider. Компилирование выражения, функции или класса через этот класс занимает десяток строк, а в итоге получается готовая сборка. Плюсы очевидны: простота; надёжность компилятора (используется тот же, что и в csc.exe); результат является не интерпретируемым, а исполняемым (офигенный бонус в скорости).
    • +1
      А вы в курсе, что в CLR сборки не выгружаемы?
      • 0
        А что если создать второй домен, поработать в нем и потом его выгрузить, когда он будет не нужен?
    • 0
      Да, конечно это можно сделать, но мне кажется, это — не очень элегантный способ для простых действий (по сути эквивалентен описанному мной примеру с Delphi). К тому же, при использовании готовых решений мы лишаемся гибкости, которую приобретаем при написании собственных небольших (но полезных) решений.
  • +1
    Судя по комментариям, я так понял, что выражение интерпретируется, а не компилируется. Поправьте, если ошибаюсь.
    В таком случае это представлает чисто академический интерес для студентов, которые начинают делать свои парсеры. Но, если говорить о практическом использовании, то большим упущением являтся отсутствие нормального скомпилированного кода (не интерпретируемого). Тем паче, что пост был рамещен в .NET.
    Я бы предложил вам продолжить эту тему и представить публике вторую версию, где выражение по настоющему компилируется. В .NET это возможно сделать и сейчас, не дожидаясь выхода 4-ого Frameworka, где компилятор можно будет удобно использовать в runtime как сервис, т.е. подобная задача там будет решаться в несколько строк. Сейчас решение подобной задачи (имеется ввиду компиляция в IL) хоть и несколько утомительна (по сравнению с тем, что будем иметь в будущем), но думаю даст ощутимый прирост в скорости, и покажет по данной теме все возможности платформы .NET.
    • 0
      Я бы назвал это интерпретацией предкомпилированного (если можно так выразиться) кода. Что-то вроде псевдокода, в котором роль инструкций выполняют элементы (операнды и операции) в постфиксной нотации. Интерпретацией бы это было, если бы сразу из строки переводилось в результат. Здесь же — нечто среднее.
      Насчет генерации IL-кода — хорошая идея, которая уже фигурировала в комментариях, спасибо, я подумаю над этим.
      Спасибо за отзыв )
  • 0
    Хорошая статья, сам что-то такое писал, с использованием польской натации.
  • 0
    В файле compiller.cs в строке 58 нужно добавить ещё одно условие, чтобы из
    ((itemIndex > 0) && (preparedExpression.PreparedExpressionItems[itemIndex - 1].Kind == PreparedExpressionItemKind.Delimiter) && (preparedExpression.PreparedExpressionItems[itemIndex - 1].DelimiterKind == DelimiterKind.OpeningBrace)))

    * This source code was highlighted with Source Code Highlighter.

    получить
    ((itemIndex > 0) && ((preparedExpression.PreparedExpressionItems[itemIndex - 1].Kind == PreparedExpressionItemKind.Delimiter) && (preparedExpression.PreparedExpressionItems[itemIndex - 1].DelimiterKind == DelimiterKind.OpeningBrace)) || (preparedExpression.PreparedExpressionItems[itemIndex - 1].Kind == PreparedExpressionItemKind.Signature)))

    * This source code was highlighted with Source Code Highlighter.


    Это позволит избежать ситуации, вида 1 < -1, при которой знак "-" ошибочно трактовался как бинарная операция.
    • +1
      Надо добавить не только PreparedExpressionItemKind.Signature, но и DelimiterKind.Comma, чтобы верно работала такая ситуация:
      Вот описание операции:
      />

      />

      Вот выражение power(5,-(-5)), на нём получаю stack disbalance, правим так:
      ((itemIndex > 0) && (preparedExpression.PreparedExpressionItems[itemIndex — 1].Kind == PreparedExpressionItemKind.Delimiter) && ((preparedExpression.PreparedExpressionItems[itemIndex — 1].DelimiterKind == DelimiterKind.OpeningBrace) || (preparedExpression.PreparedExpressionItems[itemIndex — 1].DelimiterKind == DelimiterKind.Comma)))
      Пока проверить не могу, как совместить это с вышеописанным патчем.
      • 0
        Откусилось описание операции, вот:
        />

        />


Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.