65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 表达式解析器，使用 RPN

deepeddie
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.57/5 (25投票s)

2004年1月18日

5分钟阅读

viewsIcon

215137

downloadIcon

7435

使用 C# 中的 RPN 进行表达式解析器的设计与实现。

引言

本文的目的是在 C# 中使用 RPN 的设计与实现一个简单的表达式解析器和求值器，来演示面向接口的编程范式。目标受众的技能水平应为初级到中级。

背景

有关表达式和逆波兰表示法（RPN）的介绍，请参阅本文 - 表达式求值器：使用 RPN，作者 lallous，位于 C++/MFC 部分。

设计说明

(此处引用的所有代码均在 RPNParser.cs 文件中。)

接口

每个表达式都由操作数和运算符组成。这在接口 IOperand 和 IOperator 中得到了体现。

  • IArithmeticOperations 定义了二元算术运算符（+、-、*、\、%）的方法。
  • IComparisonOperations 定义了所有比较运算符（>、>=、<、<=、==、!=）的方法。
  • ILogicalOperations 定义了逻辑运算符（&& 、||）的方法。

这些接口背后的思想如下——

每个操作数支持一组操作，而运算符则使用两个操作数所支持的操作来计算一对操作数。

例如：Long 操作数支持算术和比较运算，而 String 可能只支持比较运算。Boolean 操作数仅支持逻辑运算。

像 + 这样的运算符只需要知道它需要调用实现 IArithmeticOperations 接口的 IOperand 上的 Plus 方法。这使得表达式解析与求值（在此例中为 RPN 序列化）的算法与执行实际求值的数据类型分离，因此可以非常方便地扩展以支持新的数据类型。

操作数

Operand 类是一个抽象基类，实现了 IOperand 接口，并额外提供数据存储。

LongOperand 是一个 Operand 类，专门用于 Long 和 Int（Int64 和 Int32）类型的操作数，并实现了 IArithmeticOperations、IComparisonOperations 接口。

BoolOperand 是一个 Operand 类，专门用于 bool 类型操作数，并且仅实现 ILogicalOperations 接口。

OperandHelper 是一个静态类，提供对象工厂功能，根据传递给它的 Type 来创建相应的 Operand 对象（OperandHelper.CreateOperand）。

对于 Decimal/String 或用户定义类型（例如 Matrix）等新的操作数类型，则需要扩展此工厂方法。

运算符

IOperator 定义了一个名为 Eval 的方法，用于计算表达式的左侧（LHS）和右侧（RHS）。

Operator 是一个实现了此接口的抽象基类，并为运算符提供数据存储。

ArithmeticOperator、ComparisonOperator、LogicalOperator 是运算符类，分别用于支持 IArithmeticOperations、IComparisonOperations、ILogicalOperations。

OperatorHelper 是一个辅助类，提供对象工厂功能，用于创建相应的 Operator 对象（OperatorHelper.CreateOperator）。此类提供确定运算符优先级的服务。这基于运算符在 m_AllOps 变量中定义的相对索引。它还提供用于解析输入表达式字符串的正则表达式。例如，使用正则表达式 [=<>!]{1,2} 来解析比较运算符。

表达式解析

Tokenizer 类提供使用正则表达式解析输入表达式字符串的功能。

TokenEnumerator 类支持 IEnumerator 接口，用于遍历输入表达式字符串中的各种标记。标记以 Token 对象的形式返回给调用者。

给定的表达式可以解析为算术、逻辑或比较表达式类型。这由 enums ExpressionType::ET_ARITHMETIC, ExpressionType::ET_COMPARISON 和 ExpressionType::ET_LOGICAL 控制。也可以组合这些 enum 类型。

例如，要将表达式解析为所有这些类型，请将 ExpressionType.ET_ARITHMETIC| ExpressionType.ET_COMPARISON|ExpressionType.ET_LOGICAL 传递给 Tokenizer 构造函数。

RPN 序列的生成在 RPNParser::GetPostFixNotation 方法中完成，并使用了上述 C++ 文章中描述的算法。返回值是一个 ArrayList，其中包含 RPN 序列中的操作数和运算符。

此方法接受一个名为 bFormula 的参数，该参数确定正在解析的表达式是公式（形式为 x+y*z/t）还是包含直接值（3+6*7/2）。如果表达式不是公式，则此方法会提取值并将其存储在 Token 对象中以供后续求值。如果表达式是公式，则需要将相应变量的值作为哈希表单独传递以进行求值。

表达式求值

RPNParser::EvaluateRPN 是执行 RPNParser::GetPostFixNotation 方法生成的 RPN 的实际求值方法，同样基于上述 C++ 文章中描述的算法。此方法以包含 RPN 序列的 ArrayList 作为输入，如果表达式是公式，则还需要一个包含表达式中变量值的哈希表。

用法

解析器的典型用法如下——

RPNParser parser = new RPNParser();

string szExpression = @"((2+3)*2<10 || 1!=1) && 2*2==4";

parser.EvaluateExpression( szExpression, 
    Type.GetType("System.Int64" ), false, null );

附带的代码包含了一个小型基于窗体的应用程序来测试该逻辑。

它使用 RPN_Parser::Convert2String() 方法来获取 RPN 序列的字符串表示。

可扩展性

通过继承 Operand 和 Operator 类，可以轻松地扩展解析器以支持新的操作数类型和运算符。由于解析和求值逻辑完全基于接口，因此通常无需更改它们。当然，需要扩展工厂类以支持新类型，并且如果添加新运算符，则需要相应地修改 Operatorhelper 类中使用的正则表达式及其优先级信息。

希望有人能从中受益。

当前的不足

  1. 未处理一元运算符（+、-、!）。
  2. 尚不支持混合变量和值的表达式（例如，x+y/3*z%2）。
  3. 未处理按位 & 和 |。
  4. 是否不支持将带有多个括号的组合表达式仅视为一种 ExpressionType？

    // 例如，((2+3)*2<10 || 1!=1) && 2*2==4 无法仅作为逻辑表达式处理。

© . All rights reserved.