Здравствуйте, наверное, перед многими стояла задача создание своего парсера математических выражений для тех или иных задач. Вот и у меня возникла такая задача. В посте я расскажу о своем опыте и процессе создания такой программы, возможно он кому-либо пригодится.
Это мой первый пост и особо не судите строго, особенно код, он далеко не самый лучший. =)
История
Конечно же, идея создания парсера не возникла сама собой. Такое задание дали в учебном заведении, где я обучаюсь. Сначала, идей, каким образом это делать не приходило. Но после недолгого размышления и чтения статей с Википедии, решение показалось довольно ясным и не вызывающим вопросов.
Реализация
Первый пришла идея создания из математического выражения дерева выражения, которое будет построено с учетом приоритетов операций. Каждая математическая операция представляется своим классом, который реализует интерфейс IExpression с единственным методом Calculate:
public interface IExpression
{
double Calculate(ParameterCollection parameters);
}
Также, бинарные и унарные операторы имеют отдельные базовые классы. Класс UnaryExpression имеет только одну переменную типа IExpression, а BinnaryExpression - две. Благодаря этому и получается дерево. А методы Calculate реализованы так, что они также используют метод Calculate, объектов типа IExpression, которые содержатся в классе. Немного запутанное объяснение получается, но если взглянуть на код понятнее становится.
Всю структуру классов можно видеть на следующем изображении:
Меня такой способ вполне устраивал. И вполне нормально работал при ручном построении дерева. Но вот как построить такое дерево из вводимой строки, оставалось вопросом. Возникала проблема правильно рассчитывать приоритет операций и учитывать скобки для правильного построения дерева.
После недолгого гугления я узнал про Обратная Польская Нотация (ОПН). При помощи ОПН можно записать выражение таким образом, чтоб при чтении такой записи первыми были прочтено выражение с наибольшим приоритетом. Плюс отпадала необходимость в использовании скобок, тем самым упрощая запись.
Ну а далее уже было всё просто. Нужны были методы для конвертирования в ОПН и из ОПН в дерево классов IExpression. Также, я использовал ещё один метод, который из обычной строки создавал коллекцию токенов (для упрощения работы с входной строкой). Весь код создания токенов был написан вручную (обход всей строки по символьно). Регулярные выражения не использовались.
Для поддержки переменных в выражении использовался класс унаследованный от Dictionary<char, double>. И передаваемый в качестве параметра методу Calculate.
В итоге
Получилась вполне рабочая библиотека, к которой оставалось только прикрутить пользовательский интерфейс.
Код доступен на
codeplex.com и
github.com. В архиве два проекта: библиотека, в которой содержится весь код парсера и само приложение, содержащее пользовательский интерфейс на WPF.
P.S. Добавлена возможность постоить график функции.
P.P.S. Добавлена возможность парсинга логических выражений.
