使用解释器模式解析代数表达式
如何使用解释器模式解析代数表达式。
引言
解释器模式用于使用一组类来建模语法，这些类代表语法中可能的表达式。例如，对于代数表达式 4 + 4，可以使用 AddExpression 类来表示该表达式。AddExpression 类将包含对两个操作数的引用以及评估表达式并基于两个操作数返回值的能力。
不深究文字，您可以看到代数表达式的各种可能形式如何使用类来表示。此外，表达式本身可以作为其他表达式的操作数，这取决于定义的运算顺序。
当涉及表示变量表达式时，情况会变得棘手一些，因为变量表达式的求值会根据变量的当前值而改变。解释器模式通过定义一个上下文类来提供解决此问题的简洁方案，该类提供可能出现在正在求值的表达式中的变量的当前值。
在本文中，我将展示如何使用解释器模式开发一个功能齐全的代数表达式解析器。这是一个易于处理且非微不足道的任务，使其成为演示解释器模式的绝佳候选。此外，还会自然出现使用其他设计模式（如工厂、模板方法和组合模式）的实例，这使其成为演示设计模式总体纪律使用的更好候选。
不应忘记关于设计模式的标准警告。它们只能在适当的地方应用。对于非微不足道的复杂问题，好的解决方案几乎不可能遵循理想的面向对象设计。权衡取舍是不可避免的。通常，简单的设计比复杂的设计更好，而包含一堆设计模式的设计通常是最复杂的。
总体结构
项目的结构遵循编译器术语中解析器的通用结构。在高层，解析器将定义明确的语法的字符序列转换为可以在以后求值的数据中间结构，同时根据输入的变化而变化。在低层，解析过程的第一步是将字符序列转换为标记序列。此步骤称为词法分析。下一步是将标记序列转换为可求值的数据中间结构。
AXTokenizer 类负责将初始字符序列转换为标记序列。如果字符序列不是有效的标记序列，则会抛出异常。如果字符序列是有效的标记序列，下一步是 AXValidator 类执行的常规验证。
一旦获得有效的标记序列，ExpressionFactory 将用于从标记序列创建一系列 Expression 对象。然后，AXParser 类中的代码会对表达式序列进行求值，以通过 Expression 对象树的形式生成一个 Expression 对象，该对象表示输入的代数表达式。这个表达式树是解析器生成的数据中间结构。ExpressionContext 类作为表达式树的输入，并传递给叶子表达式，通过替换的方式进行求值。
表达式基类
所有 Expression 类都包含在 Expressions.cs 文件中。每个 Expression 类都代表我们语法中可能的表达式，在本例中是代数。所有 Expression 类都派生自抽象基类 Expression。我选择抽象基类而不是接口，因为我想提供一些通用实现，同时要求派生类实现某些函数。
Expression 类为 IsBound、Bind 和 Evaluate 方法提供了实现，并期望在派生类中定义 InnerBind 和 InnerEvaluate 方法。InnerBind 方法接受参数并将它们绑定到将由 InnerEvaluate 方法求值。IsBound 方法指示是否已将参数绑定到操作数。当解析时，IsBound 方法的实用性将显而易见。至于 Evaluate 和 InnerEvaluate 方法，它们都接受一个 ExpressionContext 对象作为参数。最终会利用 VariableExpression 对象，如下文所述。
一个障碍是 System.Math 库的运行方式。通常，超越函数（无法通过代数方法求值的函数，如三角函数）通过项的总和来近似。从微积分的角度来看，可以通过相应的无限级数获得三角函数的精确值。由于计算机无法计算无限级数的结果，因此必须近似三角函数的值。问题是，结果是 Math.Cos(Math.PI/2.0) 返回一个非常小的非零数，这是不正确的。
我选择使用模板方法模式。在这种情况下，模板方法是 InnerEvaluate。每个 Expression 派生类都可以实现它选择的任何数学运算，并返回结果，而无需担心零问题。Evaluate 方法本身会将 ZERO_THRESHOLD 常量以下的所有值转换为零。Bind 方法遵循相同的模式，InnerBind 方法作为模板方法。这提供了一定的对称性，并确保正确设置了 _isBound 成员。
以下是 Expression 类的实现。
public abstract class Expression
{
protected readonly double ZERO_THRESHOLD = 1.0 * Math.Pow(10.0, -14.0);
protected bool _isBound;
public Expression()
{
_isBound = false;
}
public bool IsBound()
{
return _isBound;
}
public void Bind(params object[] arguments)
{
InnerBind(arguments);
_isBound = true;
}
public double Evaluate(ExpressionContext context)
{
double result = InnerEvaluate(context);
if (Math.Abs(result) <= ZERO_THRESHOLD)
return 0;
else
return result;
}
protected abstract void InnerBind(params object[] arguments);
protected abstract double InnerEvaluate(ExpressionContext context);
}
这里的情况并不十分完美。专业的代数表达式解析器将不得不使用一个更好的数学库，该库从三角函数返回已知的零值。这也可以在各个表达式类中完成，但这会使工作不必要地复杂化。
此外，Expression 类的设计也可以受到质疑。装饰器模式是一种将一个类包装在另一个类中，该类实现相同的接口，但只是将调用委托给内部类，然后添加自己的行为到结果中的好模式。在这种情况下，装饰器模式不能使用，因为它隐藏了它所装饰类的实际类型。通常，OOD 文档会警告不要编写与类类型相关的代码。然而，在这种情况下，利用 ExpressionFactory 就没有那么简洁了。这是一个决策不是非黑即白，并且正在做出权衡的领域。
表达式派生类
Expression 派生类包括 ConstantExpression、NumericExpression、BinaryExpression 和 FunctionExpression。这些类中的每一个都实现了 InnerBind 方法，该方法接受可变数量的参数并将它们绑定到内部维护的操作数。当调用 Bind 方法时，会依次调用 InnerBind 方法，并将 Expression 视为已绑定。当调用 Evaluate 方法时，会依次调用 InnerEvaluate 方法，此时会对绑定的操作数进行运算以产生结果。
例如，以下是派生自 BinaryExpression 的 AddExpression 类的定义。
public sealed class AddExpression : BinaryExpression
{
protected override double InnerEvaluate(ExpressionContext context)
{
return _operand1.Evaluate(context) + _operand2.Evaluate(context);
}
}
另一个例子是，以下是派生自 FunctionExpression 的 CosExpression 类的定义。
public sealed class CosExpression : FunctionExpression
{
protected override double InnerEvaluate(ExpressionContext context)
{
return Math.Cos(_operand.Evaluate(context));
}
}
ConstantExpression 对象始终被视为已绑定，并且它们的 InnerEvaluate 方法始终返回相同的值。NumericExpression 对象同样简单，只有一个操作数被绑定，并且是 InnerEvaluate 方法返回的值。
VariableExpression 和 ExpressionContext
总的来说，Expression 派生类都很简单，除了 VariableExpression，它是唯一一个利用 Evaluate 方法的 ExpressionContext 参数而不是简单地将其传递给操作数的 Evaluate 方法的表达式。
ExpressionContext 类维护一个字典，该字典将一个双精度值与一个 Variable 枚举值关联起来。虽然 ExpressionContext 不派生自 Expression，但它有自己的 Bind 方法来关联变量的值。可以通过在 ExpressionContext 对象上执行查找来获取与变量关联的值。以下是 Lookup 方法的代码。
public double Lookup(Variable variable)
{
if (_bindings.ContainsKey(variable))
return _bindings[variable];
else
return double.NaN;
}
当在 VariableExpression 对象上调用 Evaluate 方法时，会在 ExpressionContext 参数上执行查找，然后返回该值。以下是 VariableExpression 类的定义。
public sealed class VariableExpression : Expression
{
private Variable _variable;
protected override void InnerBind(params object[] arguments)
{
_variable = (Variable)arguments[0];
}
protected override double InnerEvaluate(ExpressionContext context)
{
return context.Lookup(_variable);
}
}
分词
在介绍了 Expression 类之后，是时候看看字符序列如何精确地转换为表达式序列了。如上所述，此过程的第一步是标记化。AXTokenizer 类负责标记化字符序列。总而言之，AXTokenizer 是一个如此简单的类，以至于将此步骤称为词法分析似乎是错误的。
标记被定义为匹配给定正则表达式模式的字符序列。AXTokenizer 类有两种用于添加和删除模式的方法，分别是 AddPattern 和 RemovePattern。它还有一个额外的用于根据当前模式集执行实际标记的方法，即 Tokenize。Tokenize 接受一个字符串并返回一个字符串列表，表示原始字符串中的标记序列。
我希望此步骤完全确定性，忽略可能出现的任何警告。例如，区分数字的否定运算和减法运算。考虑到这一点，Tokenize 方法首先倾向于匹配较长的字符串到模式，然后迭代地尝试匹配越来越小的子字符串到模式。在此阶段，我没有发现需要关注性能，因为 Tokenize 不是一个需要重复调用的方法。
以下是 Tokenize 方法的实现。
public List<string> Tokenize(string text)
{
List<string> tokens = new List<string>();
for (int i = 0; i < text.Length; i++)
{
bool matched = false;
for (int j = text.Length - i; j > 0 && !matched; j--)
{
foreach(KeyValuePair<string,Regex> pair in _patterns)
{
if (pair.Value.IsMatch(text.Substring(i, j)))
{
matched = true;
tokens.Add(text.Substring(i, j));
i += j - 1;
break;
}
}
}
if (!matched)
{
throw new AXTokenException(i,
"Unrecognized character sequence starting at index " +
i.ToString() + ".");
}
}
return tokens;
}
ExpressionFactory
一旦从 AXTokenizer.Tokenize 方法获得标记序列，就需要将其转换为相应的 Expression 派生类对象的序列。这借助 ExpressionFactory 类来完成。
就像 AXTokenizer 类有用于模式的添加和删除方法一样，ExpressionFactory 类也有用于添加和删除模式与 Expression 派生类类型之间关联的方法，分别是 AddAssociation 和 RemoveAssociation。此外，它定义了一个 Create 方法，该方法基于标记参数创建一个 Expression 派生类类型的实例。
通过迭代 AXTokenizer 返回的标记列表，并对适当初始化的 ExpressionFactory 对象调用 Create 方法，就可以获得一个表达式序列。从技术上讲，ExpressionFactory 是简单工厂模式的一个实例。以下是 Create 方法的代码。
public Expression Create(string token)
{
if (!string.IsNullOrEmpty(token))
{
foreach (KeyValuePair<string, KeyValuePair<Regex,Type>> pair in _associations)
{
if (pair.Value.Key.IsMatch(token))
{
ConstructorInfo info = pair.Value.Value.GetConstructor(Type.EmptyTypes);
return (Expression)info.Invoke(null);
}
}
}
return null;
}
解析
您可能已经注意到 AXTokenizer、ExpressionFactory 和 AXValidator 类都标记为 internal。那么，它们的设施是如何使用的呢？AXParser 类将所有这些联系在一起。
AXParser 有一个 AXTokenizer 成员和一个 ExpressionFactory 成员。在构造时，这些成员被初始化以支持最常见的代数表达式。AddAssociation 方法允许客户端通过为 ConstantExpression 和 FunctionExpression 类型添加新关联来扩展此功能。
除了 AddAssociation 方法之外，AXParser 还有一个公共方法 Parse。Parse 接受一个字符串并返回一个 Expression 对象。这个 Expression 对象就是表达式树，代表作为参数传入的完全解析的代数表达式。现在可以为独立变量的任何赋值来求值代数表达式。这通过构造一个 ExpressionContext 对象，为每个独立变量调用 ExpressionContext.Bind 方法，并将对象作为参数传递给返回的 Expression 对象的 Evaluate 方法来完成。
Parse 方法要做的第一件事是删除输入字符串中的空格。之后，它使用 AXTokenizer.Tokenize 方法将字符串转换为标记序列。然后，如上所述，它将标记序列转换为表达式序列。一旦获得表达式序列，就会使用 AXValidator 来验证它。此时，表达式序列已准备好构建成一个单一的表达式树。
表达式树的构建在一个 `while` 循环中进行，该循环一直迭代到列表中只剩下一个 Expression。在进入循环之前和每次循环迭代之后，都会通过调用 RemoveExcessParens 方法来删除多余的括号。在每次循环迭代中，最高优先级运算的索引由调用 DetermineHighestPrecedence 方法确定，然后将该索引作为参数传递给 CollapseExpression 方法。
为了对解析过程有一个高层视图，以下是 Parse 方法的定义。
public Expression Parse(string text)
{
string copy = text.Replace(" ", string.Empty).Trim();
List<string> tokens = _tokenizer.Tokenize(copy);
List<Expression> expressions = TokensToExpressions(tokens);
AXValidator.Validate(expressions); //throws
RemoveExcessParens(expressions);
while (expressions.Count > 1)
{
int i = DetermineHighestPrecedence(expressions);
CollapseExpression(expressions, i);
RemoveExcessParens(expressions);
}
return expressions[0];
}
前面我提到了 Expression.IsBound 函数。通过查看下面的 CollapseExpression 方法的实现，现在可以理解为什么这个函数是必需的。首先，一旦一个表达式被绑定，你就可以对其 Evaluate 方法进行有效调用。考虑到这一点，一个已绑定的表达式就等同于一个 ConstantExpression 对象，并在后续解析中应如此看待。例如，注意if语句中对 IsBound 方法的调用。
private void CollapseExpression(List<Expression> expressions, int i)
{
Expression current = expressions[i];
Expression previous = new NullExpression();
Expression next = new NullExpression();
if (i - 1 >= 0)
previous = expressions[i - 1];
if (i + 1 < expressions.Count)
next = expressions[i + 1];
if (current is SubtractExpression && !previous.IsBound() && !(
previous is RightParenExpression))
{
SubtractExpression expression = (SubtractExpression)current;
NumericExpression zero = new NumericExpression();
zero.Bind(0.0);
expression.Bind(zero, next);
expressions.RemoveAt(i + 1);
}
else if (current is FunctionExpression)
{
FunctionExpression expression = (FunctionExpression)current;
expression.Bind(next);
expressions.RemoveAt(i + 1);
}
else if (current is BinaryExpression)
{
BinaryExpression expression = (BinaryExpression)current;
expression.Bind(previous, next);
expressions.RemoveAt(i + 1);
expressions.RemoveAt(i - 1);
}
}
IsBound 方法的相同考虑因素也体现在 DetermineHighestPrecedence 方法的实现中。一个已绑定的 Expression 对象有效地被视为一个 ConstantExpression。
另一个需要认识到的重要点是 DetermineHighestPrecedence 和 CollapseExpression 方法如何处理否定情况。否定就是从零中减去。这个决定遵循奥卡姆剃刀原则，“实体不应被不必要地增加。” 我认为我在这里呈现的内容已尽可能接近最优的简洁。
如何使用
在文章的开头，我包含了一个指向项目文件的链接。该项目编译成一个名为 AXLibrary.dll 的类库。我没有包含演示项目，因为我希望在关于 The Code Project 的 WPF 3D 图形计算器文章中使用 AXLibrary 库。此外，使用该库非常简单。以下是如何使用该库的示例。
AXParser parser = new AXParser();
Expression expression = parser.Parse("cos(PI/4)*(5+x)");
ExpressionContext context = new ExpressionContext();
context.Bind(Variable.x, 4);
MessageBox.Show(expression.Evaluate(context).ToString());
该项目在 Visual Studio 2008 中针对 .NET Framework 版本 3.5 进行编译。但是，由于它使用了 C# 语言的标准功能，该项目可以轻松转换为任何其他 .NET Framework 版本。不幸的是，您将不得不先创建一个容器项目并手动复制文件，因为据我所知，没有将项目转换为旧版本的工具。
历史
- 2008 年 3 月 5 日 -- 发布原始版本