Парсер математических и логических выражений на C#

Здравствуйте, наверное, перед многими стояла задача создание своего парсера математических выражений для тех или иных задач. Вот и у меня возникла такая задача. В посте я расскажу о своем опыте и процессе создания такой программы, возможно он кому-либо пригодится.

Это мой первый пост и особо не судите строго, особенно код, он далеко не самый лучший. =)

История

Конечно же, идея создания парсера не возникла сама собой. Такое задание дали в учебном заведении, где я обучаюсь. Сначала, идей, каким образом это делать не приходило. Но после недолгого размышления и чтения статей с Википедии, решение показалось довольно ясным и не вызывающим вопросов.

Реализация

Первый пришла идея создания из математического выражения дерева выражения, которое будет построено с учетом приоритетов операций. Каждая математическая операция представляется своим классом, который реализует интерфейс 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. Добавлена возможность парсинга логических выражений.