C# - Средство разбора выражений по алгоритму разделения-слияния на C#
Я публиковал новый алгоритм для разбора математических выражений на C++ в майском и июльском номерах «CVu Journal» (см. пп. 1 и 2 во врезке «Ссылки»). Две статьи понадобились потому, что один проницательный читатель, Сайлес С. Браун (Silas S. Brown), нашел в первой реализации алгоритма ошибку, поэтому мне пришлось ее модифицировать. Благодаря этому читателю алгоритм стал более зрелым. С тех пор я исправил и несколько более мелких ошибок. Теперь я намерен представить реализацию исправленного алгоритма на C#.
Не слишком вероятно, что вам когда-нибудь придется писать код для разбора математического выражения, но методы, используемые в этом алгоритме, применимы и в других сценариях, например для разбора нестандартных строк. Кроме того, в этом алгоритме можно легко определить новые функции, которые будет делать все, что вы пожелаете (скажем, выдавать веб-запрос для заказа пиццы). С небольшими изменениями вы также можете создать собственный компилятор C# для вашего нового пользовательского скриптового языка. Более того, алгоритм может заинтересовать вас просто сам по себе.
Алгоритм Эдсгера Дейкстры (Edsger Dijkstra), опубликованный более 50 лет назад в 1961 году, часто применяется для разбора математических выражений (см. п. 3 во врезке «Ссылки»). Но неплохо иметь альтернативу этому алгоритму, которая при той же временной сложности, является, по моему мнению, более простой в реализации и расширении.
Заметьте, что я собираюсь использовать идиому виртуального конструктора для реализации фабрики функций. Эту идиому ввел в C++ Джеймс Коплен (James Coplien) (см. п. 4 во врезке «Ссылки»). Надеюсь, вы сочтете интересным ее применение и в мире C#.
Алгоритм разделения-слияния
Демонстрационная программа на рис. 1 показывает алгоритм разделения-слияния (split-and-merge algorithm) для разбора математического выражения.
Рис. 1. Выполнение демонстрации алгоритма разделения-слияния
Алгоритм состоит из двух этапов. На первом этапе строка, содержащая выражение, разделяется на список объектов Cell, где каждый Cell определен так:
Здесь action — это отдельный символ, который может быть любым математическим оператором: * (умножение), / (деление), + (сложение), – (вычитание) или ^ (возведение в степень) либо специальным символом, обозначающим конец выражения, — в данном случае я «зашил» его в код как закрывающую круглую скобку «)». Последний элемент в списке ячеек, подлежащих слиянию, всегда будет специальным символом в action «)», т. е. он указывает на отсутствие действия, но вы можете использовать вместо него любой другой символ.
Не слишком вероятно, что вам когда-нибудь придется писать код для разбора математического выражения, но методы, используемые в этом алгоритме, применимы и в других сценариях, например для разбора нестандартных строк.
На первом этапе выражение разбивается на лексемы (tokens), которые затем преобразуются в ячейки (cells). Все лексемы разделяются по одному из математических выражений или круглыми скобками. Маркер может быть либо вещественным числом, либо строкой с именем какой-либо функции. Класс ParserFunction (будет определен позднее) отвечает за разбор всех функций в строке или за разбор строки в число. Кроме того, он может рекурсивно вызывать алгоритм разбора всей строки. Если в строке нет функций или круглых скобок, рекурсия не применяется.
На втором этапе все ячейки объединяются. Давайте сначала рассмотрим второй этап, поскольку он немного проще, чем первый.
Слияние списка ячеек
Список ячеек объединяется по одной согласно приоритетам действий, т. е. математических операторов. Эти приоритеты вычисляются следующим образом:
Две ячейки можно объединить, если и только если приоритет действия ячейки слева не ниже, чем приоритет действия следующей за ней ячейки:
Слияние ячеек подразумевает применение действия ячейки слева к значениям ячейки слева и ячейки справа. Новая ячейка будет иметь то же действие, что и ячейка справа, как видно из рис. 2.
Рис. 2. Метод MergeCells
Например, слияние Cell(8, '–') и Cell(5, '+') даст новую Cell(8 – 5, '+') = Cell (3, '+').
Но что произойдет, если две ячейки нельзя объединить из-за того, что приоритет ячейки слева ниже, чем у ячейки справа? В этом случае осуществляется временное перемещение к следующей ячейке справа, чтобы попытаться объединить ее с соседней ячейкой и т. д.; все это выполняется рекурсивно. Как только ячейка справа объединена с соседней к ней ячейке, я возвращаюсь к исходной ячейке слева и пытаюсь повторно объединить ее с только что созданной ячейкой справа, как показано на рис. 3.
Рис. 3. Слияние списка ячеек
Заметьте, что извне этот метод вызывается с параметром mergeOneOnly, установленным в false, поэтому он не вернет управление, пока не закончит слияние всех ячеек. В противоположность этому, когда метод слияния вызывается рекурсивно (если ячейки слева и справа нельзя объединить из-за их приоритетов), mergeOneOnly будет устанавливаться в true, потому что я хочу вернуть управление туда, где был, как только завершаю реальное объединение в методе MergeCells.
Также заметьте, что значение, возвращаемое методом Merge, является реальным результатом выражения.
Разделение выражения на список ячеек
Первая часть алгоритма разделяет выражение на список ячеек. Математический приоритет операций на этом этапе не принимается во внимание. Сначала выражение разбивается на список лексем. Все лексемы отделяются любым математическим оператором либо открывающей или закрывающей круглой скобкой. Круглые скобки могут (не обязательно) иметь связанную функцию, например в «1– sin(1–2)» есть связанная функция, а в «1– (1–2)» — нет.
Давайте посмотрим, что происходит в отсутствие функций или круглых скобок, когда имеется лишь выражение, содержащее вещественные числа и математические операторы между ними. В этом случае я просто создаю ячейки, состоящие из вещественного числа и последующего действия. Скажем, разделение «3–2*4» дает список из трех ячеек:
У последней ячейки всегда будет специальное действие END_ARG, которое я определяю как:
Его нельзя поменять на что-то другое, но в этом случае следует учитывать соответствующую открывающую скобку в действии START_ARG, определенном мной так:
Список ячеек объединяется по одной согласно приоритетам действий, т. е. математических операторов.
Если одна из лексем является функцией или выражением в скобках, к ней применяется полный алгоритм разделения-слияния, используя рекурсию. Например, если выражение — "(3–1)–1", полный алгоритм сначала применяется к содержимому в скобках:
Функция, выполняющая разделение, — LoadAndCalculate (рис. 4).
Рис. 4. Метод LoadAndCalculate
Метод LoadAndCalculate добавляет все ячейки в список listToMerge, а затем вызывает вторую часть алгоритма разбора, функцию Merge. Элемент StringBuilder будет хранить текущую лексему, добавляя в нее символы по одному, как только они будут считываться из строки выражения.
Метод StillCollecting проверяет, собираются ли в данный момент символы для текущей лексемы. Это не относится к случаю, когда текущим символом является END_ARG или любой другой специальный символ «to» вроде запятой, когда разбираемые аргументы отделяются запятыми; чуть позже я дам пример этой ситуации, используя функцию power. Кроме того, лексема больше не собирается, если текущим символом является допустимое действие или START_ARG:
Я узнаю, что сбор текущей лексемы закончен, как только получаю математический оператор, описанный в методе ValidAction, или круглую скобку, определенную константами START_ARG или END_ARG. Существует также особый случай, включающий лексему «–», которая используется для обозначения числа, начинающегося с отрицательного знака.
В конце этого этапа разделения все подвыражения в скобках и все вызовы функций исключаются рекурсивными вызовами до полной оценки алгоритмом. Но результатом этих рекурсивных вызовов всегда будет действие END_ARG, которое не будет корректным в глобальной области выражения, если вычисляемое выражение не находится в конце оцениваемого выражения. Вот почему действие нужно обновлять после каждого рекурсивного вызова, например:
Код для метода updateAction показан на рис. 5.
Рис. 5. Метод обновления действия
Реальный разбор извлеченной лексемы происходит в следующем коде с рис. 4:
Если извлеченная лексема не является функцией, этот код попытается преобразовать ее в значение типа double. В ином случае будет вызвана ранее зарегистрированная, подходящая функция, которая в свою очередь рекурсивно вызовет метод LoadAndCalculate.
Пользовательские и стандартные функции
Я решил реализовать фабрику функций, используя идиому виртуального конструктора, которую впервые опубликовал Джеймс Коплен (см. п. 4 во врезке «Ссылки»). В C# она часто реализуется с использованием метода фабрики (см. п. 5 во врезке «Ссылки»), который опирается на дополнительный класс фабрики при создании необходимого объекта. Но более старый проектировочный шаблон Коплена не нуждается в дополнительном классе фасада фабрики и вместо этого просто конструирует новый объект «на лету», используя член реализации m_impl, производный от того же класса:
Специальный внутренний конструктор инициализирует этот член соответствующим классом. Реальный класс созданного объекта реализации m_impl зависит от входных параметров, как показано на рис. 6.
Рис. 6. Виртуальный конструктор
Слияние ячеек подразумевает применение действия ячейки слева к значениям ячейки слева и ячейки справа.
Словарь используется для хранения всех функций разбора. В этом словаре строковое имя функции (например, «sin») сопоставляется с объектом, реализующим эту функцию:
Пользователи объекта разбора могут добавлять сколько угодно функций, вызывая следующий метод базового класса ParserFunction:
Метод GetValue вызывается в созданной ParserFunction, но сама работа выполняется в функции реализации, которая будет переопределять метод Evaluate базового класса:
Классы реализации функции, производные от класса ParserFunction, не будут использовать внутренний конструктор с рис. 6. Вместо этого они задействуют следующий конструктор базового класса:
В конструкторе ParserFunction на рис. 6 применяются две специальные «стандартные» функции:
Первая — это функция идентификации; она будет вызываться для разбора любого выражения в скобках, не имеющего сопоставленной функции:
Вторая функция «обобщающая» («catchall»); она вызывается, когда никакой функции, соответствующей последней извлеченной лексеме, не найдено. Это происходит, когда извлеченная лексема не является ни вещественным числом, ни реализованной функцией. В последнем случае генерируется исключение:
Все остальные функции могут быть реализованы пользователем; простейшей функцией является pi:
Более типичная реализация — функция exp:
Ссылки
- V. Kaplan «Split and Merge Algorithm for Parsing Mathematical Expressions», CVu, 27-2, May 2015 (bit.ly/1Jb470l).
- V. Kaplan «Split and Merge Revisited», CVu, 27-3, July 2015 (bit.ly/1UYHmE9).
- E. Dijkstra «Shunting-yard algorithm» (bit.ly/1fEvvLI).
- J. Coplien «Advanced C++ Programming Styles and Idioms» (p. 140), Addison-Wesley, 1992.
- E. Gamma, R. Helm, R. Johnson and J. Vlissides «Design Patterns: Elements of Reusable Object-Oriented Software», Addison-Wesley Professional Computing Series, 1995.
Ранее я говорил, что предоставлю пример, используя функцию power (возведения в степень), которая требует передачи двух аргументов, разделенный запятой. Вот как пишется функция, требующая нескольких аргументов, отделяемых пользовательским разделителем:
В алгоритм можно добавить любое количество функций из пользовательского кода, например:
Словарь используется для хранения всех функций разбора.
Заключение
Представленный здесь алгоритм разделения-слияния имеет сложность O(n), где n — это число символов в строке выражения. Дело в том, что каждая лексема будет считываться только раз на этапе разделения, а затем в самом худшем случае будет максимум 2(m – 1) – 1 сравнений на этапе слияния, где m — количество ячеек, созданных на первом этапе.
Поэтому данный алгоритм имеет ту же временную сложность, что и алгоритм Дейкстры (см. п. 3 во врезке «Ссылки»). В нем может проявляться некоторый недостаток в сравнении с алгоритмом Дейкстры, потому что он использует рекурсию. С другой стороны, я считаю, что алгоритм разделения-слияния проще в реализации именно из-за рекурсии и легче в расширении пользовательским синтаксисом, функциями и операторами.
Василий Каплан (Vassili Kaplan) — бывший разработчик Microsoft Lync. Увлекается программированием на C# и C++. В настоящее время живет в Цюрихе (Швейцарии) и работает как фрилансер на различные банки. С ним можно связаться по адресу iLanguage.ch.
Выражаю благодарность за рецензирование статьи эксперту Microsoft Джеймсу Маккаффри (James McCaffrey).