Здравствуйте, наверное, перед многими стояла задача создание своего парсера математических выражений для тех или иных задач. Вот и у меня возникла такая задача. В посте я расскажу о своем опыте и процессе создания такой программы, возможно он кому-либо пригодится.
Это мой первый пост и особо не судите строго, особенно код, он далеко не самый лучший. =)
История
Конечно же, идея создания парсера не возникла сама собой. Такое задание дали в учебном заведении, где я обучаюсь. Сначала, идей, каким образом это делать не приходило. Но после недолгого размышления и чтения статей с Википедии, решение показалось довольно ясным и не вызывающим вопросов.
Реализация
Первый пришла идея создания из математического выражения дерева выражения, которое будет построено с учетом приоритетов операций. Каждая математическая операция представляется своим классом, который реализует интерфейс IExpression с единственным методом Calculate:
public interface IExpression
{
double Calculate(ParameterCollection parameters);
}
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. Добавлена возможность парсинга логических выражений.
P.S. Добавлена возможность постоить график функции.
P.P.S. Добавлена возможность парсинга логических выражений.