使用递归下降解析进行数学表达式解析
4.78/5 (44投票s)
使用递归下降解析进行数学表达式解析
引言
我记得美好的大学时光，特别是我的第一堂数值算法课。那门课的第一个作业是创建一个数学计算器，它可以接收表达式进行计算。该应用程序将在本学期的其他作业中使用（请注意，这是开学第一天的第一个作业），在这些作业中，我们将用我们编写的算法替换常见的数学函数。在大学里只上过一门编程课，这个作业感觉很艰巨。我脑海中浮现的第一个问题是：“如果这是一门数学课，为什么我们不能直接在MatLab中编写数值算法，并在那里展示其简单的用法呢？” 我觉得创建一个像我珍贵的TI 92那样的计算器完全让人不知所措。
回想起来，如果我花时间为这个作业定义了需求，我就会意识到这个作业其实很简单。要完成的工作量并不可怕，而且为这个作业编写的代码也不会像最终那样丑陋和充满bug。
当我接到那个作业时，我面临的问题是我没有一个可以开始思考解决方案的起点（是的，我记得BODMAS（括号、乘方、除法、乘法、加法和减法））。然而，我不知道如何将所需的需求组织成合适的格式或语法，以便我只专注于实现为该语法创建的规则。我更关心的是功能以及如何解析我能想到的每一个边缘情况。
几年后，在阅读 Leendert Ammeraal 的《C++ 算法与数据结构》一书时，特别是第 11 章（讨论解释器和编译器的基础知识），我决定重新审视我那个可怕的作业。
背景
本文详细介绍的数学表达式求值器中使用了两个概念。一是使用 BNF 来设计适合创建数学表达式的语法，二是使用递归下降解析将语法转换为代码。
我不敢自称语法专家，因此我定义的规则可以根据读者的意愿进行修改（我犯的任何错误都可以转发给我，我会修正）。我大致遵循了维基百科上关于 EBNF 的页面规则 http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form。但读者应注意，本文中的实现与我的语法规则相符。
下面是已实现的语法。我假定语法非常直观，因此我只提及我在语法中做的一些假设。
首先，我假定_变量_的名称不包含_数字_（变量可以是1个或多个_字母_）。我假定一元运算符“-”（例如，-1 或 -ab）是由“( -_表达式_”定义的因子（例如，(- 1)，((-a) + b) 或 (-ab)）。我假定_函数_是_项_的一部分，并且可以分解回一个因子。我认为值得提及的另一个假设是阶乘“!”运算符，它对_项_是可选的。我曾选择将其移至_因子_或_项_，我最终决定将其放在_项_的定义中。
INPUT = EXPRESSION
EXPRESSION = TERM { "+" | "-" TERM }
TERM = (FUNCTION | FACTOR) { "*" | "/" | "%" | "^" FUNCTION | FACTOR } { "!" }
FUNCTION = ( "COS"| "SIN" | "TAN" | "EXP" |"LN" | "LOG" "(" FACTOR ")" )
FACTOR = NUMBER|VARIABLE| ( "(" ["-"] EXPRESSION ")" )
VARIABLE = ALPHABHET,{ALPHABHET}
NUMBER= DIGIT,{["."] DIGIT}
DIGIT = 0|1|..|9
ALPHABHET = a|b|..|z|A|B|..|Z
将语法转换为代码的技术称为递归下降解析 (RDP)，它是一种自上而下的解析形式，由一组相互调用的函数构成。考虑到递归，我为所有非终结符标识符创建了一个函数，这些函数只关注其定义的语法的特定方面。
以下是用于表示语法的主要方法。
ISymbol Expression()
Symbol Term()
Symbol FunctionEvaluator()
Symbol Factor()
利用下面讨论的代码，我创建了一个数学表达式解析器示例。如下图所示：
Using the Code
在考虑如何实现表达式解析器时，我首先想到的是我希望如何使用解析器。我想到 `Evaluator` 类的用户可能希望能够设置和获取要解析的 `Expression`，如果表达式可以被求值，用户会想要获取浮点 `Result`。如果无法求值（即如果它包含未定义的变量），用户会想要获取一个处理过的字符串结果。考虑到这一点，我创建了 `IExpression` 接口。然后我为在处理每个符号时所需的中间信息类型创建了 `ISymbol` 接口。对于数字，使用 `FloatingValue` 变量；对于变量、操作和函数，使用 `StringValue`。为了区分所有变量、操作、函数和括号，我创建了 `SymbolType` 枚举（在所附的表达式计算器示例中，符号类型有助于实现“ -1”、“1--1”、“1*-1”等情况）。
public interface IExpression
{
string Expression { get; set; }
double Result { get; set; }
bool CanEvaluate { get; set; }
string StrResult { get; set; }
}
public enum SymbolType {expression, operation, function, variable, digit,brackets,endTag}
public interface ISymbol:IExpression
{
SymbolType SymbolType { get; set; }
double FloatingValue { get; set; }
string StringValue { get; set; }
}
`Symbol` 类实现了 `ISymbol` 接口，并包含 `TypedClone()` 方法，该方法实现了 `Symbol` 对象本身的强类型成员级克隆。需要克隆以保持传入的原始表达式。静态类 `ExtensionLib` 中的扩展方法提供了一种将 `IExpression` 类型克隆为 `Symbol` 类型的方法。
public class Symbol:ISymbol
{
public string Expression { get; set; }
public double Result { get; set; }
public bool CanEvaluate { get; set; }
public string StrResul { get; set; }
public SymbolType SymbolType { get; set; }
public double FloatingValue { get; set; }
public string StringValue { get; set; }
public Symbol TypedClone()
{
return this.MemberwiseClone() as Symbol;
}
}
public static class ExtensionLib
{
public static Symbol TypedClone(this IExpression v)
{
return ((Symbol) v).TypedClone();
}
}
字段 `_currentPositionCnt` 维护 `Expression` 字符串中的位置，指示从何处继续解析。`_processVariableExpression` 是一个标志，用于检查 `Variable` 是否可以映射到值。`_lastReadSymbol` 保存上次解析但尚未使用的 `Symbol`。`_expression` 对象保存原始对象的副本，可以对其进行修改。`_originalExpression` 对象保存未修改的原始对象。`_listOfFunctions` 保存支持的函数列表。`_listOfBinaryOperators` 保存在执行计算时接受两个参数的运算符。`_listOfUnaryOperators` 保存作用于单个参数（或 `Expression`）的运算符，`VariableMapper` 字典保存变量到值的映射。
private int _currentPositionCnt;
private bool _processVariableExpression;
private Symbol _lastReadSymbol;
private IExpression _expression;
private IExpression _originalExpression;
private readonly List<string> _listOfFunctions = new List<string>();
private readonly List<string> _listOfBinaryOperators = new List<string>();
private readonly List<string> _listOfUnaryOperators = new List<string>();
public readonly Dictionary<string, double> VariableMapper { get; private set; }
构造函数使用各自的值（函数、运算符以及变量到值的字典）初始化 `_listOfFunctions`、`_listOfBinaryOperators`、`_listOfUnaryOperators` 列表和 `VariableMapper` 字典。
public Evaluator()
{
_listOfFunctions.AddRange(new [] { "COS", "SIN", "TAN", "EXP", "LN", "LOG" });
_listOfBinaryOperators.AddRange(new [] { "*", "/", "^", "%", "+", "-" });
_listOfUnaryOperators.Add("!");
VariableMapper = new Dictionary<string, double> {{"PI", Math.PI}};
}
`Resolve()` 方法接受一个遵循 `IExpression` 接口的对象和一个布尔参数，该参数告诉我们是否应该评估可映射变量。该方法会修剪字符之间的空格，它还会将包含变量的表达式进行因子分解，以便在实际将变量与值匹配时进行紧凑的计算。后一部分可以移除，并更新 `Factor()` 方法以始终只检查 `Variable` 是否可以映射到值。
public IExpression Resolve(IExpression exp, bool resolveExp=false)
{
_currentPositionCnt = 0;
_originalExpression = exp;
_expression = exp.TypedClone();
_expression.Expression = _expression.Expression.Replace(" ", "");
_expression.Expression += "#";
var result = Expression();
if (!NextIs("#"))
throw new Exception
("An error occurred while procession the expression [ "
+ _originalExpression.Expression + " ] At position "
+ _currentPositionCnt.ToString());
if (resolveExp && !result.CanEvaluate && VariableMapper.Count > 0)
{
_processVariableExpression = true;
_lastSymbolType = SymbolType.expression;
_currentPositionCnt = 0;
_lastReadSymbol = null;
_expression.Expression = result.StrResult.Replace(" ", "");
result = Expression();
}
return result;
}
`ResolveAsString()` 方法接受一个遵循 `IExpression` 接口的对象，以及一个布尔参数，该参数指示我们是否应该评估可映射变量。该方法向调用者返回一个字符串结果，该结果可以是浮点值或字符串表达式。
public string ResolveAsString(IExpression exp, bool resolveExp=false)
{
var result = Resolve(exp, resolveExp);
return result.CanEvaluate ? result.Result.ToString() : result.StrResult;
}
`Expression()` 方法调用 `Term()` 方法。该调用的结果可以是一个可求值的值、一个_变量_或一个_表达式_。然后进行检查，看通过 `NextIs()` 方法调用检索到的下一个 `Symbol` 是否是诸如“`+`”、“`-`”之类的运算符，如果是，则再次调用 `Term()` 以获取求值所需的第二个参数。否则，我们返回 X `Symbol`。
private ISymbol Expression()
{
var x = Term();
if (x == null) return null;
for (; ; )
{
if(NextIs("+"))
{
var y = Term();
if (y.CanEvaluate && x.CanEvaluate)
x.Result = x.FloatingValue = x.FloatingValue + y.FloatingValue;
else
{
x.StringValue =
"("+(x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +
" + " + (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else if (NextIs("-"))
{
var y = Term();
if (y.CanEvaluate && x.CanEvaluate)
x.Result = x.FloatingValue = x.FloatingValue - y.FloatingValue;
else
{
x.StringValue = "("+(x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +
" - "+ (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else
{
break;
}
}
x.Result = x.FloatingValue;
x.StrResult = x.StringValue;
return x;
}
`Term()` 方法调用 `Factor()` 方法。结果可以是一个可求值的值、一个变量或一个表达式。然后检查通过 `NextIs()` 方法调用检索到的下一个 `Symbol` 是否是运算符，例如“`*`”、“`/`”、“`%`”、“`^`”、“`!`”或一个_函数_，否则返回 X 符号。如果它是上述运算符之一，我们再次调用 `Factor()` 方法以获取下一个 `Symbol`（它同样可以是一个值、一个变量或一个表达式）。请注意，阶乘情况不会再次调用 `Factor()` 方法。另外值得指出的是，此方法中的运算符优先级都相等。要提高任何操作的优先级，需要使用括号来包含表达式的该部分。
private Symbol Term()
{
var x = Factor();
if (x == null) return null;
for (; ; )
{
if (NextIs("*"))
{
var y = Factor();
if (y.CanEvaluate && x.CanEvaluate)
x.Result = x.FloatingValue = x.FloatingValue * y.FloatingValue;
else
{
x.StringValue = "("+(x.CanEvaluate? x.FloatingValue.ToString()
: x.StringValue) +
" * " + (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else if (NextIs("/"))
{
var y = Factor();
if (y.CanEvaluate && x.CanEvaluate)
x.Result = x.FloatingValue = x.FloatingValue / y.FloatingValue;
else
{
x.StringValue = "("+(x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +
" / " + (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else if (NextIs("%"))
{
var y = Factor();
if (y.CanEvaluate && x.CanEvaluate)
{
x.Result = x.FloatingValue = x.FloatingValue % y.FloatingValue;
}
else
{
x.StringValue = "("+(x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +
" % " + (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else if (NextIs("^"))
{
var y = Factor();
if (y.CanEvaluate && x.CanEvaluate)
{
x.Result = x.FloatingValue = Math.Pow(x.FloatingValue , y.FloatingValue);
}
else
{
x.StringValue = "( (" + (x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +
")^ " + (y.CanEvaluate ? y.FloatingValue.ToString()
: y.StringValue) + ")";
x.CanEvaluate = false;
}
}
else if (NextIs("!"))
{
if (x.CanEvaluate)
{
x.Result = x.FloatingValue = Factorial(x.FloatingValue);
}
else
{
x.CanEvaluate = false;
x.StringValue = "(" + (x.CanEvaluate ? x.FloatingValue.ToString()
: x.StringValue) +")! ";
}
}
else if (_listOfFunctions.Contains(x.StringValue))
{
x = FunctionEvaluator(x.StringValue);
}
else
{
break;
}
}
return x;
}
`Factor()` 方法调用 `Next()` 方法来获取下一个 `Symbol`。如果 `Symbol` 可以被求值，则立即返回；否则，我们检查 `Symbol` 是否是括号。如果 `Symbol` 是括号，我们再次调用表达式。注意 `PreviewNextifTrueMoveTrackerByOne()` 方法。这用于处理负号紧跟在开括号后面的情况。如果我们可以处理变量，我们会在 `VariableMapper` 字典中查找变量名并获取相应的值。注意：我本想在这里实现的一个功能是，变量能够指向变量。
private Symbol Factor()
{
var x = Next();
_lastReadSymbol = null;
if (x != null && x.CanEvaluate)
return x;
if (x != null)
{
if (x.StringValue == "(")
{
bool isunaryMinus = PreviewNextifTrueMoveTrackerByOne("-");
x = Expression() as Symbol;
if (x == null || !NextIs(")"))
{
throw new
Exception("Expression needs to end with a parenthesis "
+ "[ " + _originalExpression.Expression
+ " ] Error at position "
+ _currentPositionCnt.ToString());
}
if (isunaryMinus)
{
if (x.CanEvaluate)
x.FloatingValue *= -1;
else
x.StringValue = "((-1) * " + x.StringValue+")";
}
}
if(_processVariableExpression && x.SymbolType == SymbolType.variable)
{
if (VariableMapper.ContainsKey(x.StringValue))
{
x.FloatingValue = VariableMapper[x.StringValue];
x.StringValue = string.Empty;
x.CanEvaluate = true;
}
}
}
_lastReadSymbol = null;
return x;
}
`FunctionEvaluator()` 方法调用 `Factor()` 方法以获取作为函数参数传入的预期值、变量或表达式。如果 `Factor()` 方法返回的 `Symbol` 可以被求值，则调用相应的数学函数；否则，假定参数组成包含变量，并组成假定的数学函数和参数的字符串组合。
public Symbol FunctionEvaluator(string value)
{
Symbol x;
if (NextIs("("))
{
_lastReadSymbol = new Symbol
{
SymbolType = SymbolType.brackets,
StringValue = "("
};
x = Factor();
}
else
{
throw new Exception(
"Function must be imediately followed by parenthesis. Error : ["
+ _originalExpression.Expression
+ " ] At position "
+ _currentPositionCnt.ToString());
}
if (x != null && x.CanEvaluate)
{
switch(value.ToLower())
{
case "sin":
{
x.FloatingValue = Math.Sin(Math.PI/180 * x.FloatingValue);
break;
}
case "cos":
{
x.FloatingValue = Math.Cos(Math.PI / 180 * x.FloatingValue);
break;
}
case "tan":
{
x.FloatingValue = Math.Tan(Math.PI / 180 * x.FloatingValue);
break;
}
case "exp":
{
x.FloatingValue = Math.Exp(x.FloatingValue);
break;
}
case "ln":
{
x.FloatingValue = Math.Log(x.FloatingValue, Math.E);
break;
}
case "log":
{
x.FloatingValue = Math.Log10(x.FloatingValue);
break;
}
}
}
else if (x != null && !x.CanEvaluate)
{
x.StringValue = "( " + value + "( " + x.StringValue + " ))";
}
return x;
}
`Next()` 方法负责将字符串字符解析成符号。它处理将字符串字母分离为函数或变量。注意：您会看到，变量仅限于字符串字符的限制是通过我们解析变量和整数的方式强制执行的。开头的 `If` 语句是为了避免在之前设置的 `Symbol` 尚未被声明时前进到下一个 `Symbol`。
private Symbol Next()
{
if (_lastReadSymbol != null)
{
var sym = _lastReadSymbol;
_lastReadSymbol = null;
return sym;
}
if (_expression.Expression != null &&
_expression.Expression.Length > _currentPositionCnt)
{
var length = _expression.Expression.Length;
if (IsNumber())
{
var val = _expression
.Expression[_currentPositionCnt]
.ToString();
_currentPositionCnt++;
while (_currentPositionCnt < length && IsNumber())
{
val += _expression.Expression[_currentPositionCnt++];
}
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.digit,
FloatingValue = double.Parse(val),
CanEvaluate = true
};
return _lastReadSymbol;
}
if (IsString())
{
var val = _expression
.Expression[_currentPositionCnt]
.ToString();
_currentPositionCnt++;
while (_currentPositionCnt < length && IsString())
{
val += _expression.Expression[_currentPositionCnt++];
}
if (_listOfFunctions.Contains(val))
{
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.function,
StringValue = val
};
return _lastReadSymbol;
}
//return variable
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.variable,
StringValue = val ,
CanEvaluate = false
};
return _lastReadSymbol;
}
if ((_expression.Expression[_currentPositionCnt] == '.'
&& (_expression.Expression[_currentPositionCnt + 1] < '0'
&& _expression.Expression[_currentPositionCnt + 1] > '9')))
{
throw new
Exception("Expression can not have a decimal point"
+" without an accompanying digits."
+" Expression [ "
+ _originalExpression.Expression
+ " ] At position "
+ _currentPositionCnt.ToString());
}
if (_expression.Expression[_currentPositionCnt] == '(' ||
_expression.Expression[_currentPositionCnt] == ')')
{
_lastReadSymbol = new Symbol
{
SymbolType = SymbolType.brackets,
StringValue = _expression
.Expression[_currentPositionCnt++]
.ToString()
};
return _lastReadSymbol;
}
if (_listOfBinaryOperators.Contains(_expression
.Expression[_currentPositionCnt]
.ToString()))
{
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.operation,
StringValue = _expression
.Expression[_currentPositionCnt++]
.ToString()
};
return _lastReadSymbol;
}
if (_listOfUnaryOperators.Contains(_expression
.Expression[_currentPositionCnt]
.ToString()))
{
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.operation,
StringValue = _expression
.Expression[_currentPositionCnt++]
.ToString()
};
return _lastReadSymbol;
}
if (_expression.Expression[_currentPositionCnt] == '#')
{
_lastReadSymbol =
new Symbol
{
SymbolType = SymbolType.endTag,
StringValue = _expression
.Expression[_currentPositionCnt++]
.ToString()
};
return _lastReadSymbol;
}
}
return null;
}
编写 `Factorial()` 方法是为了让我可以将阶乘作为表达式求值器中的一个函数。
private double Factorial(double number)
{
var val = (long)number;
double retVal=1;
for (long i =val; i>0; i--)
{
retVal *= i;
}
return retVal;
}
`NextIs()` 方法通过调用 `Next()` 来选择下一个 `Symbol`，如果其值（对于可求值的 `Symbol` 为 `FloatingValue`，对于不可求值的 `Symbol` 为 `StringValue`）与传入的参数匹配，则将 `_lastReadSymbol` 设置为 null，以便通过 `Next()` 方法继续选择新的 `Symbol`。
private bool NextIs(string val)
{
var t = Next();
if (t != null)
{
if (t.CanEvaluate)
if (t.FloatingValue.ToString() == val)
{
_lastReadSymbol = null;
return true;
}
else
{
_lastReadSymbol = t;
}
else
if (t.StringValue == val)
{
_lastReadSymbol = null;
return true;
}
else
_lastReadSymbol = t;
}
return false;
}
预览下一个并提前跟踪器一步的方法是为了处理负号跟在括号开头“(-”后面的情况（它在 `Factor()` 函数中使用）。
private bool PreviewNextifTrueMoveTrackerByOne(string val)
{
if (_expression.Expression != null
&& _expression.Expression.Length > _currentPositionCnt)
{
if (_expression.Expression[_currentPositionCnt].ToString() ==val)
{
_currentPositionCnt++;
return true;
}
}
return false;
}
`IsNumber()` 方法在 `Next()` 方法中使用，用于检查当前字符是否为数字而不是字母。该检查适用于浮点数，通过检查如果出现点，则下一个字符必须是数字。
private bool IsNumber()
{
return ((_expression.Expression[_currentPositionCnt] >= '0'
&& _expression.Expression[_currentPositionCnt] <= '9') ||
(_expression.Expression[_currentPositionCnt] == '.' &&
(_expression.Expression[_currentPositionCnt + 1] >= '0'
&& _expression.Expression[_currentPositionCnt + 1] <= '9')));
}
`IsString()` 方法在 `Next()` 方法中使用，用于检查当前字符是否为字母而不是数字。
private bool IsString()
{
return ((_expression.Expression[_currentPositionCnt] >= 'A'
&& _expression.Expression[_currentPositionCnt] <= 'Z') ||
(_expression.Expression[_currentPositionCnt] >= 'a'
&& _expression.Expression[_currentPositionCnt] <= 'z'));
}
关注点
附件中的示例是一个数学表达式计算器，它利用上述代码的变体实现了一个功能完善的计算器。它允许用户编写包含变量的数学表达式，并以变量的形式对这些表达式进行因式分解。它还允许将变量映射到值，从而实现表达式的完整求值。它允许存储表达式和回忆表达式（此功能以循环方式进行）。“定义”按钮允许您定义变量映射。
可以增强给定示例代码的一些有趣事情是：
- 实现一个微分计算器，就像 CodeProject 中以下文章所示：https://codeproject.org.cn/Articles/13731/Symbolic-Differentiation
- 将实现改为使用后缀表达式。
- 实现图形功能（可能是我最喜欢的，因为这意味着你必须处理变量中的变量情况）。
历史
暂无修订。