基于C#的表达式解析器设计方法

肖 巍

（长春师范学院 传媒科学学院，吉林 长春130032）

基于C#的表达式解析器设计方法

肖 巍

（长春师范学院 传媒科学学院，吉林 长春130032）

在MIS系统开发和报表系统的设计中，经常会用到通用的表达式解析器。为此，本文给出了一种采用后缀表达式实现的表达式解析和计算方法，并用C#语言给予实现。

后缀表达式；表达式解析；C#

开发MIS系统时，报表设计中经常会碰到表达式解析器，完成用户自定义的公式运算，使得报表系统显示的数据更加完善和灵活，因此开发一个相对独立的表达式解析器组件显得尤为重要。

一、表达式表示法

表达式中最常见的表示法形式有中缀、前缀和后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。

中缀表示法是表达式的常规表示法，称它为中缀表示法，是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数时（在操作符是二元操作符，如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。

Syntax：operand1 operator operand2Example:（A+B）*C-D/（E+F）

前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学特别是编译器设计方面，为纪念其发明者波兰科学家Jan Lukasiewicz，这种表示法也称为“波兰表示法”。

Syntax:operator operand1 operand2 Example:-*+ABC/D+EF

后缀表示法中，操作符位于操作数后面，后缀表示法也称为“逆波兰表示法”（RPN）。

Syntax : operand1 operand2 operator Example :AB+C*DEF+/-

中缀表达式的计算比较复杂，它必须遵守以下三条规则：（1） 先计算括号内，后计算括号外；（2） 在无括号或同层括号内，先进行乘除运算，后进行加减运算，即乘除运算的优先级高于加减运算的优先级；（3）同一优先级运算，从左向右依次进行。从这三条规则中可以看出，在中缀表达式的计算过程中，既要考虑括号的作用，又要考虑运算符的优先级，还要考虑运算符出现的先后次序。因此，各运算符实际的运算次序往往同它们在表达式中出现的先后次序是不一致的，是不可预测的。当然，凭直观判别一个中缀表达式中哪个运算符最先算，哪个次之……，哪个最后算并不困难，但通过计算机处理就比较困难了。因为计算机只能一个字符一个字符地扫描，要想得到哪一个运算符先算，就必须对整个中缀表达式扫描一遍，一个中缀表达式中有多少个运算符，原则上就得扫描多少遍才能计算完毕，这样十分浪费时间，显然是不可取的。

前缀和后缀表示法主要有三条特征：（1）操作数的顺序与等价的中缀表达式中操作数的顺序一致；（2） 不需要括号；（3）操作符的优先级不相关。在后缀表达式中，因为其不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需要一遍扫描即可完成，显然比中缀表达式的计算要简单得多，因此我们采用后缀表达式来实现表达式解析器的解析和计算。

二、从中缀表达式到后缀表达式的转换

要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。

Left associativity:A+B+C= （A+B） +C

Right associativity:A^B^C=A^（B^C）

转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：（1）初始化一个空堆栈，将结果字符串变量置空；（2）从左到右读入中缀表达式，每次一个字符；（3）如果字符是操作数，将它添加到结果字符串；（4）如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号，把这个操作符压入（push）堆栈；（5）如果字符是个开括号，把它压入堆栈；（6）如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串；（7）如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

三、后缀表达式求值

对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中不需要括号，而且操作符的优先级也不再起作用，可以用如下算法对后缀表达式求值：（1）初始化一个空堆栈；（2）从左到右读入后缀表达式；（3）如果字符是一个操作数，把它压入堆栈；（4）如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈，如果您不能够弹出两个操作数，后缀表达式的语法就不正确；（5）到后缀表达式末尾，从堆栈中弹出结果，若后缀表达式格式正确，那么堆栈应该为空。

四、解析器组件中的几个重要类

1.Formula类：该类包含了表达式的验证属性和计算方法

Formula（string name） :构造方法，应用表达式字符串初始化此类；

Varible属性:Ivariable接口属性，用来设置表达式计算时所需要的自定义变量对象，如不设置，则采用默认的自定义变量对象；

Valid属性:Error结构体属性，获取表达式的验证信息Error，no为错误编号，location为错误位置，info为错误信息，表达式验证正确no为0，location为0，info为空串；

ExpResult Eva（） :计算表达式的方法，返回ExpResult类型。

2.ExpResult类:该类包含了表达式计算后返回的结果，应用Formula类的Eva方法实例化

IsRight属性:表达式是否计算出结果；

ErrorNo属性:获取表达式验证后的错误号，正确返回为0；

ErrorLocation属性:获取表达式验证后的位置，正确返回为0；

abstract double Eval（ArrayList oprands）:此方法根据oprands进行计算，operands个数为operator元数。

4.Ivariable接口:自定义变量类实现此接口

Double GetValue（string str） :此方法返回变量计算时对应的值；

String GetType（string） :此方法返回变量计算时的类型。

五、结 语

本文通过对几种表达式表示法特点的分析，采用了先把中缀表达式转换成后缀表达式，再对后缀表达式进行求值的方法，完成了对表达式解析器算法的设计，并采用C#语言给予了实现，最后形成独立的表达式解析器组件完全可以将其扩展到现有的一些MIS系统中去。

[1]汪永好.表达式解析器在工作流管理系统中的应用[J].计算机工程与设计，2007，（06）.

[2]林勇.一款表达式解析器在电力统计系统中的应用[J].计算机应用，2002，（08）.

[3]何云东.复杂表达式解析和计算的研究实现[J].中国科技信息，2009，（04）.

[4]叶晓彤等.基于唯一二叉树的XML函数表达式标识转换[J].计算机工程，2009，（05）.

[5]AndersHejlsberg.C#编程语言详解[M].北京：电子工业出版社，2004.

[6]李维.面向对象开发实践之路[M].北京：电子工业出版社，2005.

[7]Ted feison.VisualC#基于组件的开发[M].北京：清华大学出版社，2005.

[责任编辑：郭一鹤]

ErrorInfo属性:获取表达式验证后的错误信息，正确返回为空串；

Result属性:获取表达式计算结果，表达式错误为空串。

3.Operator类:操作符抽象类，所有运算操作符的基类

int GetDimension（） :此方法返回operator操作符的元数；

G642

：B

：1671-6531（2010）06-0125-02

2010—09—19

肖巍，男，吉林长春人，长春师范学院传媒科学学院教师，研究方向为图像处理与模式识别、自动识别技术、嵌入式系统研究。