Октябрь 2015
Том 30, номер 10
C# - Средство разбора выражений по алгоритму разделения-слияния на C#
Василий Каплан | Октябрь 2015
Продукты и технологии:
C#
В статье рассматриваются:
- алгоритм разделения-слияния (split-and-merge algorithm);
- разделение выражения на список ячеек;
- слияние списка ячеек;
- проектировочный шаблон Virtual Constructor в 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) для разбора математического выражения.
.png "Выполнение демонстрации алгоритма разделения-слияния")
Рис. 1. Выполнение демонстрации алгоритма разделения-слияния
Алгоритм состоит из двух этапов. На первом этапе строка, содержащая выражение, разделяется на список объектов Cell, где каждый Cell определен так:
class Cell
{
internal Cell(double value, char action)
{
Value = value;
Action = action;
}
internal double Value { get; set; }
internal char Action { get; set; }
}
Здесь action — это отдельный символ, который может быть любым математическим оператором: * (умножение), / (деление), + (сложение), – (вычитание) или ^ (возведение в степень) либо специальным символом, обозначающим конец выражения, — в данном случае я «зашил» его в код как закрывающую круглую скобку «)». Последний элемент в списке ячеек, подлежащих слиянию, всегда будет специальным символом в action «)», т. е. он указывает на отсутствие действия, но вы можете использовать вместо него любой другой символ.
Не слишком вероятно, что вам когда-нибудь придется писать код для разбора математического выражения, но методы, используемые в этом алгоритме, применимы и в других сценариях, например для разбора нестандартных строк.
На первом этапе выражение разбивается на лексемы (tokens), которые затем преобразуются в ячейки (cells). Все лексемы разделяются по одному из математических выражений или круглыми скобками. Маркер может быть либо вещественным числом, либо строкой с именем какой-либо функции. Класс ParserFunction (будет определен позднее) отвечает за разбор всех функций в строке или за разбор строки в число. Кроме того, он может рекурсивно вызывать алгоритм разбора всей строки. Если в строке нет функций или круглых скобок, рекурсия не применяется.
На втором этапе все ячейки объединяются. Давайте сначала рассмотрим второй этап, поскольку он немного проще, чем первый.
Слияние списка ячеек
Список ячеек объединяется по одной согласно приоритетам действий, т. е. математических операторов. Эти приоритеты вычисляются следующим образом:
static int GetPriority(char action)
{
switch (action) {
case '^': return 4;
case '*':
case '/': return 3;
case '+':
case '-': return 2;
}
return 0;
}
Две ячейки можно объединить, если и только если приоритет действия ячейки слева не ниже, чем приоритет действия следующей за ней ячейки:
static bool CanMergeCells(Cell leftCell, Cell rightCell)
{
return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action);
}
Слияние ячеек подразумевает применение действия ячейки слева к значениям ячейки слева и ячейки справа. Новая ячейка будет иметь то же действие, что и ячейка справа, как видно из рис. 2.
Рис. 2. Метод MergeCells
static void MergeCells(Cell leftCell, Cell rightCell)
{
switch (leftCell.Action)
{
case '^': leftCell.Value = Math.Pow(leftCell.Value, rightCell.Value);
break;
case '*': leftCell.Value *= rightCell.Value;
break;
case '/': leftCell.Value /= rightCell.Value;
break;
case '+': leftCell.Value += rightCell.Value;
break;
case '-': leftCell.Value -= rightCell.Value;
break;
}
leftCell.Action = rightCell.Action;
}
Например, слияние Cell(8, '–') и Cell(5, '+') даст новую Cell(8 – 5, '+') = Cell (3, '+').
Но что произойдет, если две ячейки нельзя объединить из-за того, что приоритет ячейки слева ниже, чем у ячейки справа? В этом случае осуществляется временное перемещение к следующей ячейке справа, чтобы попытаться объединить ее с соседней ячейкой и т. д.; все это выполняется рекурсивно. Как только ячейка справа объединена с соседней к ней ячейке, я возвращаюсь к исходной ячейке слева и пытаюсь повторно объединить ее с только что созданной ячейкой справа, как показано на рис. 3.
Рис. 3. Слияние списка ячеек
static double Merge(Cell current, ref int index, List<Cell> listToMerge,
bool mergeOneOnly = false)
{
while (index < listToMerge.Count)
{
Cell next = listToMerge[index++];
while (!CanMergeCells(current, next))
{
Merge(next, ref index, listToMerge, true /* mergeOneOnly */);
}
MergeCells(current, next);
if (mergeOneOnly)
{
return current.Value;
}
}
return current.Value;
}
Заметьте, что извне этот метод вызывается с параметром mergeOneOnly, установленным в false, поэтому он не вернет управление, пока не закончит слияние всех ячеек. В противоположность этому, когда метод слияния вызывается рекурсивно (если ячейки слева и справа нельзя объединить из-за их приоритетов), mergeOneOnly будет устанавливаться в true, потому что я хочу вернуть управление туда, где был, как только завершаю реальное объединение в методе MergeCells.
Также заметьте, что значение, возвращаемое методом Merge, является реальным результатом выражения.
Разделение выражения на список ячеек
Первая часть алгоритма разделяет выражение на список ячеек. Математический приоритет операций на этом этапе не принимается во внимание. Сначала выражение разбивается на список лексем. Все лексемы отделяются любым математическим оператором либо открывающей или закрывающей круглой скобкой. Круглые скобки могут (не обязательно) иметь связанную функцию, например в «1– sin(1–2)» есть связанная функция, а в «1– (1–2)» — нет.
Давайте посмотрим, что происходит в отсутствие функций или круглых скобок, когда имеется лишь выражение, содержащее вещественные числа и математические операторы между ними. В этом случае я просто создаю ячейки, состоящие из вещественного числа и последующего действия. Скажем, разделение «3–2*4» дает список из трех ячеек:
Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) }
У последней ячейки всегда будет специальное действие END_ARG, которое я определяю как:
const char END_ARG = ')';
Его нельзя поменять на что-то другое, но в этом случае следует учитывать соответствующую открывающую скобку в действии START_ARG, определенном мной так:
const char START_ARG = '(';
Список ячеек объединяется по одной согласно приоритетам действий, т. е. математических операторов.
Если одна из лексем является функцией или выражением в скобках, к ней применяется полный алгоритм разделения-слияния, используя рекурсию. Например, если выражение — "(3–1)–1", полный алгоритм сначала применяется к содержимому в скобках:
Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) }
Функция, выполняющая разделение, — LoadAndCalculate (рис. 4).
Рис. 4. Метод LoadAndCalculate
public static double LoadAndCalculate(string data,
ref int from, char to = END_LINE)
{
if (from >= data.Length || data[from] == to)
{
throw new ArgumentException(
"Loaded invalid data: " + data);
}
List<Cell> listToMerge = new List<Cell>(16);
StringBuilder item = new StringBuilder();
do // основной цикл обработки на первом этапе
{
char ch = data[from++];
if (StillCollecting(item.ToString(), ch, to))
{ // символ все еще относится к предыдущему операнду
item.Append(ch);
if (from < data.Length && data[from] != to)
{
continue;
}
}
// Я получил следующую лексему. Вызов getValue() ниже может
// рекурсивно вызывать loadAndCalculate(). Это произойдет,
// если извлеченный элемент является функцией или если
// следующий элемент начинается с START_ARG '('.
ParserFunction func = new ParserFunction(
data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
char action = ValidAction(ch) ? ch :
UpdateAction(data, ref from, ch, to);
listToMerge.Add(new Cell(value, action));
item.Clear();
} while (from < data.Length && data[from] != to);
if (from < data.Length && (data[from] == END_ARG ||
data[from] == to))
{ // это происходит при рекурсивном вызове:
// перемещение на один символ вперед
from++;
}
Cell baseCell = listToMerge[0];
int index = 1;
return Merge(baseCell, ref index, listToMerge);
}
Метод LoadAndCalculate добавляет все ячейки в список listToMerge, а затем вызывает вторую часть алгоритма разбора, функцию Merge. Элемент StringBuilder будет хранить текущую лексему, добавляя в нее символы по одному, как только они будут считываться из строки выражения.
Метод StillCollecting проверяет, собираются ли в данный момент символы для текущей лексемы. Это не относится к случаю, когда текущим символом является END_ARG или любой другой специальный символ «to» вроде запятой, когда разбираемые аргументы отделяются запятыми; чуть позже я дам пример этой ситуации, используя функцию power. Кроме того, лексема больше не собирается, если текущим символом является допустимое действие или START_ARG:
static bool StillCollecting(string item, char ch, char to)
{
char stopCollecting = (to == END_ARG || to == END_LINE) ?
END_ARG : to;
return (item.Length == 0 && (ch == '-' || ch == END_ARG)) ||
!(ValidAction(ch) || ch == START_ARG || ch == stopCollecting);
}
static bool ValidAction(char ch)
{
return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '^';
}
Я узнаю, что сбор текущей лексемы закончен, как только получаю математический оператор, описанный в методе ValidAction, или круглую скобку, определенную константами START_ARG или END_ARG. Существует также особый случай, включающий лексему «–», которая используется для обозначения числа, начинающегося с отрицательного знака.
В конце этого этапа разделения все подвыражения в скобках и все вызовы функций исключаются рекурсивными вызовами до полной оценки алгоритмом. Но результатом этих рекурсивных вызовов всегда будет действие END_ARG, которое не будет корректным в глобальной области выражения, если вычисляемое выражение не находится в конце оцениваемого выражения. Вот почему действие нужно обновлять после каждого рекурсивного вызова, например:
char action = ValidAction(ch) ? ch
: UpdateAction(data, ref from, ch);
Код для метода updateAction показан на рис. 5.
Рис. 5. Метод обновления действия
static char UpdateAction(string item, ref int from,
char ch, char to)
{
if (from >= item.Length || item[from] == END_ARG ||
item[from] == to)
{
return END_ARG;
}
int index = from;
char res = ch;
while (!ValidAction(res) && index < item.Length)
{ // смотрим на следующий символ в строке,
// пока не найдем допустимое действие
res = item[index++];
}
from = ValidAction(res) ? index : index > from ?
index – 1 : from;
return res;
}
Реальный разбор извлеченной лексемы происходит в следующем коде с рис. 4:
ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch);
double value = func.GetValue(data, ref from);
Если извлеченная лексема не является функцией, этот код попытается преобразовать ее в значение типа double. В ином случае будет вызвана ранее зарегистрированная, подходящая функция, которая в свою очередь рекурсивно вызовет метод LoadAndCalculate.
Пользовательские и стандартные функции
Я решил реализовать фабрику функций, используя идиому виртуального конструктора, которую впервые опубликовал Джеймс Коплен (см. п. 4 во врезке «Ссылки»). В C# она часто реализуется с использованием метода фабрики (см. п. 5 во врезке «Ссылки»), который опирается на дополнительный класс фабрики при создании необходимого объекта. Но более старый проектировочный шаблон Коплена не нуждается в дополнительном классе фасада фабрики и вместо этого просто конструирует новый объект «на лету», используя член реализации m_impl, производный от того же класса:
private ParserFunction m_impl;
Специальный внутренний конструктор инициализирует этот член соответствующим классом. Реальный класс созданного объекта реализации m_impl зависит от входных параметров, как показано на рис. 6.
Рис. 6. Виртуальный конструктор
internal ParserFunction(string data, ref int from,
string item, char ch)
{
if (item.Length == 0 && ch == Parser.START_ARG)
{
// Функции нет — только выражение в скобках
m_impl = s_idFunction;
return;
}
if (m_functions.TryGetValue(item, out m_impl))
{
// Функция есть, и она зарегистрирована
// (например, pi, exp и т. д.)
return;
}
// Функция не найдена, попытаемся разобрать это как число
s_strtodFunction.Item = item;
m_impl = s_strtodFunction;
}
Слияние ячеек подразумевает применение действия ячейки слева к значениям ячейки слева и ячейки справа.
Словарь используется для хранения всех функций разбора. В этом словаре строковое имя функции (например, «sin») сопоставляется с объектом, реализующим эту функцию:
private static Dictionary<string, ParserFunction> m_functions =
new Dictionary<string, ParserFunction>();
Пользователи объекта разбора могут добавлять сколько угодно функций, вызывая следующий метод базового класса ParserFunction:
public static void AddFunction(string name, ParserFunction function)
{
m_functions[name] = function;
}
Метод GetValue вызывается в созданной ParserFunction, но сама работа выполняется в функции реализации, которая будет переопределять метод Evaluate базового класса:
public double GetValue(string data, ref int from)
{
return m_impl.Evaluate(data, ref from);
}
protected virtual double Evaluate(string data, ref int from)
{
// Настоящая реализация будет в производных классах
return 0;
}
Классы реализации функции, производные от класса ParserFunction, не будут использовать внутренний конструктор с рис. 6. Вместо этого они задействуют следующий конструктор базового класса:
public ParserFunction()
{
m_impl = this;
}
В конструкторе ParserFunction на рис. 6 применяются две специальные «стандартные» функции:
private static IdentityFunction s_idFunction = new IdentityFunction();
private static StrtodFunction s_strtodFunction = new StrtodFunction();
Первая — это функция идентификации; она будет вызываться для разбора любого выражения в скобках, не имеющего сопоставленной функции:
class IdentityFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
}
}
Вторая функция «обобщающая» («catchall»); она вызывается, когда никакой функции, соответствующей последней извлеченной лексеме, не найдено. Это происходит, когда извлеченная лексема не является ни вещественным числом, ни реализованной функцией. В последнем случае генерируется исключение:
class StrtodFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double num;
if (!Double.TryParse(Item, out num)) {
throw new ArgumentException("Could not parse token [" + Item + "]");
}
return num;
}
public string Item { private get; set; }
}
Все остальные функции могут быть реализованы пользователем; простейшей функцией является pi:
class PiFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
return 3.141592653589793;
}
}
Более типичная реализация — функция exp:
class ExpFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Exp(arg);
}
}
Ссылки
- 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 (возведения в степень), которая требует передачи двух аргументов, разделенный запятой. Вот как пишется функция, требующая нескольких аргументов, отделяемых пользовательским разделителем:
class PowFunction : ParserFunction
{
protected override double Evaluate(string data, ref int from)
{
double arg1 = Parser.LoadAndCalculate(data, ref from, ',');
double arg2 = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG);
return Math.Pow(arg1, arg2);
}
}
В алгоритм можно добавить любое количество функций из пользовательского кода, например:
ParserFunction.AddFunction("pi", new PiFunction());
ParserFunction.AddFunction("exp", new ExpFunction());
ParserFunction.AddFunction("pow", new PowFunction());
Словарь используется для хранения всех функций разбора.
Заключение
Представленный здесь алгоритм разделения-слияния имеет сложность O(n), где n — это число символов в строке выражения. Дело в том, что каждая лексема будет считываться только раз на этапе разделения, а затем в самом худшем случае будет максимум 2(m – 1) – 1 сравнений на этапе слияния, где m — количество ячеек, созданных на первом этапе.
Поэтому данный алгоритм имеет ту же временную сложность, что и алгоритм Дейкстры (см. п. 3 во врезке «Ссылки»). В нем может проявляться некоторый недостаток в сравнении с алгоритмом Дейкстры, потому что он использует рекурсию. С другой стороны, я считаю, что алгоритм разделения-слияния проще в реализации именно из-за рекурсии и легче в расширении пользовательским синтаксисом, функциями и операторами.
Василий Каплан (Vassili Kaplan) — бывший разработчик Microsoft Lync. Увлекается программированием на C# и C++. В настоящее время живет в Цюрихе (Швейцарии) и работает как фрилансер на различные банки. С ним можно связаться по адресу iLanguage.ch.
Выражаю благодарность за рецензирование статьи эксперту Microsoft Джеймсу Маккаффри (James McCaffrey).