2015 年 10 月
第 30 卷第 10 期
C# - C# 中的一种分裂与合并表达式分析器
作者 Vassili Kaplan | 2015 年 10 月 | 获取代码： C#VB
我曾经在《CVu 期刊》的 2015 年 5 月和 7 月的版次上发表过一种用于分析 C++ 中数学表达式的新算法（请参阅“参考”中的第 1 项和第 2 项）。我用了两篇文章来阐述这种新算法，因为一位机敏的读者 Silas S. Brown 在第一个算法实现中发现了一个 Bug，所以我不得不对其做些修改。衷心感谢这位读者，这种算法变得更成熟了。从那以后，我还修正了一些较小的 Bug。如今我打算在 C# 中提供一种校正过的算法实现。
编写代码来分析一个数学表达式不太可能，但是用于此算法中的技术也可以应用到其他方案中，比如分析非标准的字符串。使用这种算法，还可以很轻松地定义新函数来做任何你想做的事情（例如，发出 Web 请求来订购一份披萨）。通过小幅的调整，还可以为新自定义的脚本语言创建你自己的 C# 编译器。而且，你可能会发现它本身就是一种很有趣的算法。
Edsger Dijkstra 算法，发表于 50 多年前的 1961 年，它常用于分析数学表达式（请参阅“参考”中的第 3 项）。不过有一种替代算法也挺好，尽管有着同样的时间复杂度，但我个人认为它更易于实现和扩展。
请注意，对于函数工厂实现，我打算使用“虚拟构造函数”用语。此用语是由 James Coplien 引入 C++ 中的（请参阅“参考”中的第 4 项）。我希望你们也将能够在 C# 世界里发现其使用乐趣。
分裂与合并算法
图 1 中的演示程序阐明了用以分析数学表达式的分裂与合并算法。
.png "分裂与合并算法的演示运行")
图 1 分裂与合并算法的演示运行
这种算法由两个步骤组成。在第一步中，包含表达式的字符串分裂为一列“存储单元”对象，其中每个“存储单元”定义如下：
class Cell
{
internal Cell(double value, char action)
{
Value = value;
Action = action;
}
internal double Value { get; set; }
internal char Action { get; set; }
}
此操作是一个可以是任何数学运算符的单一字符：“*”（乘）、“/”（除）、“+”（加）、“-”（减）或“^”（幂），或是一个表示表达式结尾的特殊字符，我将其硬编码为“)”。 位于这列要合并的存储单元中的最后一个元素总是有一个特殊的操作“)”，也就是没有操作，不过可以使用任何其他符号或一个圆括号代替。
在第一步中，表达式分裂为标记，然后又转换为存储单元。所有标记均由一个数学表达式或一个圆括号分隔开。标记可以是一个实数或者是一个带有函数名称的字符串。后来定义的 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 合并存储单元的方法
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;
}
例如，合并“存储单元 (8, ‘-’)”和“存储单元 (5, ‘+’)”将会产生新的“存储单元 (8 – 5, ‘+’)”，即“存储单元 (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 方法中完成一个实际合并后，就立刻返回到原来的位置。
还需要注意从该“合并”方法返回的值是表达式的实际值。
将一个表达式分裂为一列存储单元
此算法的第一部分是将一个表达式分裂为一列存储单元。在此步骤中，不考虑数学运算符的优先次序。首先，表达式分裂为一列标记。所有标记均由任何数学运算符或者由一个左括号或右括号分隔开。圆括号可能（但不是必须）有相关联的函数，例如，“1- sin(1-2)”具有相关联的函数，而“1- (1-2)”则没有。
首先，让我们来看一下当没有函数或圆括号而在它们之间仅有一个包含实数和数学运算符的表达式时，将会出现什么情况。在这种情况下，我只创建了由一个实数和一个后续的操作组成的存储单元。例如，分裂“3-2*4”就会产生一个由 3 个存储单元组成的列表：
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 // Main processing cycle of the first part.
{
char ch = data[from++];
if (StillCollecting(item.ToString(), ch, to))
{ // The char still belongs to the previous operand.
item.Append(ch);
if (from < data.Length && data[from] != to)
{
continue;
}
}
// I am done getting the next token. The getValue() call below may
// recursively call loadAndCalculate(). This will happen if extracted
// item is a function or if the next item is starting with a 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))
{ // This happens when called recursively: move one char forward.
from++;
}
Cell baseCell = listToMerge[0];
int index = 1;
return Merge(baseCell, ref index, listToMerge);
}
LoadAndCalculate 方法会将所有存储单元添加到 listToMerge 列表，然后调用分析算法的第二部分，即合并函数。StringBuilder 项将保留当前标记，当从表达式的字符串中读取字符后，StringBuilder 项就会立刻将字符逐一地添加到标记中。
StillCollecting 方法检查是否仍在收集用于当前标记的字符。如果当前字符为 END_ARG 或者任何其他特殊的“to”字符（比如逗号，如果分析参数由逗号分隔；稍后我将使用幂函数来举一个这样的示例），则不会是这种情况。另外，如果当前字符是一个有效操作或 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);
图 5 中 updateAction 方法的代码。
图 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)
{ // Look to the next character in string until finding a valid action.
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);
如果提取标记不是函数，该代码将尝试将其转换为一个类似的替代函数。否则就会调用一个合适的、之前已注册、可以轮流递归调用 LoadAndCalculate 方法的函数。
用户定义的函数和标准函数
我决定使用由 James Coplien 首次发表的虚拟构造函数用语来实现函数工厂（请参阅“参考”中的第 4 项）。在 C# 中，通常使用工厂方法来实现函数工厂（请参阅“参考”中的第 5 项），这种方法使用额外的工厂类来产生所需要的对象。不过 Coplien 的早期设计模式并不需要额外的工厂外层类，而是使用由同样的类派生的实现成员 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)
{
// There is no function, just an expression in parentheses.
m_impl = s_idFunction;
return;
}
if (m_functions.TryGetValue(item, out m_impl))
{
// Function exists and is registered (e.g. pi, exp, etc.).
return;
}
// Function not found, will try to parse this as a number.
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 上调用，但实际工作在实现函数中完成，这将会取代基类的求值方法：
public double GetValue(string data, ref int from)
{
return m_impl.Evaluate(data, ref from);
}
protected virtual double Evaluate(string data, ref int from)
{
// The real implementation will be in the derived classes.
return 0;
}
函数实现类派生自 ParserFunction 类，将不会在图 6 中使用内部构造函数。他们将改用基类的以下构造函数：
public ParserFunction()
{
m_impl = this;
}
在图 6 中，两个特殊的“标准”函数用在 ParserFunction 构造函数中：
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);
}
}
之前我说过将使用幂函数来举一个需要两个自变量（由逗号分隔）的示例。下面介绍如何编写需要多个自变量（由自定义的分隔符分隔）的函数：
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());
总结
如果 n 是表达式字符串中的字符数，则这里介绍的分裂与合并算法具有 O(n) 复杂度。之所以如此是因为在分裂步骤中仅读取一次标记，并且在最差的情况下，合并步骤中将最多有 2(m - 1) – 1 个比较，其中 m 为第一步中创建的存储单元的数量。
所以这种算法与 Dijkstra 算法有同样的时间复杂度（请参阅“参考”中的第 3 项）。由于使用递归，因此与 Dijkstra 算法相比，这种算法稍微有一点劣势。另一方面，恰恰由于递归，我相信分裂与合并算法更易于实现，并且通过自定义语法、函数和运算符，也更易于扩展。
参考
- V.Kaplan，“用于分析数学表达式的分离与合并算法，”CVu，27-2，2015 年 5月，bit.ly/1Jb470l
- V.Kaplan，“再论分裂与合并，”CVu，27-3，2015 年 7月，bit.ly/1UYHmE9
- E.Dijkstra，Shunting-yard 算法，bit.ly/1fEvvLI
- J.Coplien，“高级 C++ 编程样式和用语”（第 140 页），Addison-Wesley，1992 年
- E.Gamma，R. Helm，R. Johnson 和 J. Vlissides，“设计模式： 可重复使用的面向对象的软件元素”，Addison-Wesley 专业计算系列，1995 年
Vassili Kaplan是一位前 Microsoft Lync 开发人员。他对 C# 和 C++ 编程充满热情。现居住于瑞士的苏黎世，作为一名自由职业者供职于各银行。你可以通过 iLanguage.ch 与他联系。
衷心感谢以下 Microsoft 技术专家对本文的审阅： James McCaffrey