基于C#的表達(dá)式解析器設(shè)計(jì)方法

肖 巍

（長(zhǎng)春師范學(xué)院 傳媒科學(xué)學(xué)院，吉林 長(zhǎng)春130032）

基于C#的表達(dá)式解析器設(shè)計(jì)方法

肖 巍

（長(zhǎng)春師范學(xué)院 傳媒科學(xué)學(xué)院，吉林 長(zhǎng)春130032）

在MIS系統(tǒng)開發(fā)和報(bào)表系統(tǒng)的設(shè)計(jì)中，經(jīng)常會(huì)用到通用的表達(dá)式解析器。為此，本文給出了一種采用后綴表達(dá)式實(shí)現(xiàn)的表達(dá)式解析和計(jì)算方法，并用C#語言給予實(shí)現(xiàn)。

后綴表達(dá)式；表達(dá)式解析；C#

開發(fā)MIS系統(tǒng)時(shí)，報(bào)表設(shè)計(jì)中經(jīng)常會(huì)碰到表達(dá)式解析器，完成用戶自定義的公式運(yùn)算，使得報(bào)表系統(tǒng)顯示的數(shù)據(jù)更加完善和靈活，因此開發(fā)一個(gè)相對(duì)獨(dú)立的表達(dá)式解析器組件顯得尤為重要。

一、表達(dá)式表示法

表達(dá)式中最常見的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書寫表達(dá)式的常見方式，而前綴和后綴表示法主要用于計(jì)算機(jī)科學(xué)領(lǐng)域。

中綴表示法是表達(dá)式的常規(guī)表示法，稱它為中綴表示法，是因?yàn)槊總€(gè)操作符都位于其操作數(shù)的中間，這種表示法只適用于操作符恰好對(duì)應(yīng)兩個(gè)操作數(shù)時(shí)（在操作符是二元操作符，如加、減、乘、除以及取模的情況下）。對(duì)以中綴表示法書寫的表達(dá)式進(jìn)行語法分析時(shí)，需要用括號(hào)和優(yōu)先規(guī)則排除多義性。

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

前綴表示法中，操作符寫在操作數(shù)的前面。這種表示法經(jīng)常用于計(jì)算機(jī)科學(xué)特別是編譯器設(shè)計(jì)方面，為紀(jì)念其發(fā)明者波蘭科學(xué)家Jan Lukasiewicz，這種表示法也稱為“波蘭表示法”。

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

后綴表示法中，操作符位于操作數(shù)后面，后綴表示法也稱為“逆波蘭表示法”（RPN）。

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

中綴表達(dá)式的計(jì)算比較復(fù)雜，它必須遵守以下三條規(guī)則：（1） 先計(jì)算括號(hào)內(nèi)，后計(jì)算括號(hào)外；（2） 在無括號(hào)或同層括號(hào)內(nèi)，先進(jìn)行乘除運(yùn)算，后進(jìn)行加減運(yùn)算，即乘除運(yùn)算的優(yōu)先級(jí)高于加減運(yùn)算的優(yōu)先級(jí)；（3）同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。從這三條規(guī)則中可以看出，在中綴表達(dá)式的計(jì)算過程中，既要考慮括號(hào)的作用，又要考慮運(yùn)算符的優(yōu)先級(jí)，還要考慮運(yùn)算符出現(xiàn)的先后次序。因此，各運(yùn)算符實(shí)際的運(yùn)算次序往往同它們?cè)诒磉_(dá)式中出現(xiàn)的先后次序是不一致的，是不可預(yù)測(cè)的。當(dāng)然，憑直觀判別一個(gè)中綴表達(dá)式中哪個(gè)運(yùn)算符最先算，哪個(gè)次之……，哪個(gè)最后算并不困難，但通過計(jì)算機(jī)處理就比較困難了。因?yàn)橛?jì)算機(jī)只能一個(gè)字符一個(gè)字符地掃描，要想得到哪一個(gè)運(yùn)算符先算，就必須對(duì)整個(gè)中綴表達(dá)式掃描一遍，一個(gè)中綴表達(dá)式中有多少個(gè)運(yùn)算符，原則上就得掃描多少遍才能計(jì)算完畢，這樣十分浪費(fèi)時(shí)間，顯然是不可取的。

前綴和后綴表示法主要有三條特征：（1）操作數(shù)的順序與等價(jià)的中綴表達(dá)式中操作數(shù)的順序一致；（2） 不需要括號(hào)；（3）操作符的優(yōu)先級(jí)不相關(guān)。在后綴表達(dá)式中，因?yàn)槠洳淮嬖诶ㄌ?hào)，也不存在優(yōu)先級(jí)的差別，計(jì)算過程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個(gè)計(jì)算過程僅需要一遍掃描即可完成，顯然比中綴表達(dá)式的計(jì)算要簡(jiǎn)單得多，因此我們采用后綴表達(dá)式來實(shí)現(xiàn)表達(dá)式解析器的解析和計(jì)算。

二、從中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換

要把表達(dá)式從中綴表達(dá)式的形式轉(zhuǎn)換成用后綴表示法表示的等價(jià)表達(dá)式，必須了解操作符的優(yōu)先級(jí)和結(jié)合性。優(yōu)先級(jí)或者說操作符的強(qiáng)度決定求值順序；優(yōu)先級(jí)高的操作符比優(yōu)先級(jí)低的操作符先求值。如果所有操作符優(yōu)先級(jí)一樣，那么求值順序就取決于它們的結(jié)合性。操作符的結(jié)合性定義了相同優(yōu)先級(jí)操作符組合的順序（從右至左或從左至右）。

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

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

轉(zhuǎn)換過程包括用下面的算法讀入中綴表達(dá)式的操作數(shù)、操作符和括號(hào)：（1）初始化一個(gè)空堆棧，將結(jié)果字符串變量置空；（2）從左到右讀入中綴表達(dá)式，每次一個(gè)字符；（3）如果字符是操作數(shù)，將它添加到結(jié)果字符串；（4）如果字符是個(gè)操作符，彈出（pop）操作符，直至遇見開括號(hào)（opening parenthesis）、優(yōu)先級(jí)較低的操作符或者同一優(yōu)先級(jí)的右結(jié)合符號(hào)，把這個(gè)操作符壓入（push）堆棧；（5）如果字符是個(gè)開括號(hào)，把它壓入堆棧；（6）如果字符是個(gè)閉括號(hào)（closing parenthesis），在遇見開括號(hào)前，彈出所有操作符，然后把它們添加到結(jié)果字符串；（7）如果到達(dá)輸入字符串的末尾，彈出所有操作符并添加到結(jié)果字符串。

三、后綴表達(dá)式求值

對(duì)后綴表達(dá)式求值比直接對(duì)中綴表達(dá)式求值簡(jiǎn)單。在后綴表達(dá)式中不需要括號(hào)，而且操作符的優(yōu)先級(jí)也不再起作用，可以用如下算法對(duì)后綴表達(dá)式求值：（1）初始化一個(gè)空堆棧；（2）從左到右讀入后綴表達(dá)式；（3）如果字符是一個(gè)操作數(shù)，把它壓入堆棧；（4）如果字符是個(gè)操作符，彈出兩個(gè)操作數(shù)，執(zhí)行恰當(dāng)操作，然后把結(jié)果壓入堆棧，如果您不能夠彈出兩個(gè)操作數(shù)，后綴表達(dá)式的語法就不正確；（5）到后綴表達(dá)式末尾，從堆棧中彈出結(jié)果，若后綴表達(dá)式格式正確，那么堆棧應(yīng)該為空。

四、解析器組件中的幾個(gè)重要類

1.Formula類：該類包含了表達(dá)式的驗(yàn)證屬性和計(jì)算方法

Formula（string name） :構(gòu)造方法，應(yīng)用表達(dá)式字符串初始化此類；

Varible屬性:Ivariable接口屬性，用來設(shè)置表達(dá)式計(jì)算時(shí)所需要的自定義變量對(duì)象，如不設(shè)置，則采用默認(rèn)的自定義變量對(duì)象；

Valid屬性:Error結(jié)構(gòu)體屬性，獲取表達(dá)式的驗(yàn)證信息Error，no為錯(cuò)誤編號(hào)，location為錯(cuò)誤位置，info為錯(cuò)誤信息，表達(dá)式驗(yàn)證正確no為0，location為0，info為空串；

ExpResult Eva（） :計(jì)算表達(dá)式的方法，返回ExpResult類型。

2.ExpResult類:該類包含了表達(dá)式計(jì)算后返回的結(jié)果，應(yīng)用Formula類的Eva方法實(shí)例化

IsRight屬性:表達(dá)式是否計(jì)算出結(jié)果；

ErrorNo屬性:獲取表達(dá)式驗(yàn)證后的錯(cuò)誤號(hào)，正確返回為0；

ErrorLocation屬性:獲取表達(dá)式驗(yàn)證后的位置，正確返回為0；

abstract double Eval（ArrayList oprands）:此方法根據(jù)oprands進(jìn)行計(jì)算，operands個(gè)數(shù)為operator元數(shù)。

4.Ivariable接口:自定義變量類實(shí)現(xiàn)此接口

Double GetValue（string str） :此方法返回變量計(jì)算時(shí)對(duì)應(yīng)的值；

String GetType（string） :此方法返回變量計(jì)算時(shí)的類型。

五、結(jié) 語

本文通過對(duì)幾種表達(dá)式表示法特點(diǎn)的分析，采用了先把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式，再對(duì)后綴表達(dá)式進(jìn)行求值的方法，完成了對(duì)表達(dá)式解析器算法的設(shè)計(jì)，并采用C#語言給予了實(shí)現(xiàn)，最后形成獨(dú)立的表達(dá)式解析器組件完全可以將其擴(kuò)展到現(xiàn)有的一些MIS系統(tǒng)中去。

[1]汪永好.表達(dá)式解析器在工作流管理系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，（06）.

[2]林勇.一款表達(dá)式解析器在電力統(tǒng)計(jì)系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2002，（08）.

[3]何云東.復(fù)雜表達(dá)式解析和計(jì)算的研究實(shí)現(xiàn)[J].中國(guó)科技信息，2009，（04）.

[4]葉曉彤等.基于唯一二叉樹的XML函數(shù)表達(dá)式標(biāo)識(shí)轉(zhuǎn)換[J].計(jì)算機(jī)工程，2009，（05）.

[5]AndersHejlsberg.C#編程語言詳解[M].北京：電子工業(yè)出版社，2004.

[6]李維.面向?qū)ο箝_發(fā)實(shí)踐之路[M].北京：電子工業(yè)出版社，2005.

[7]Ted feison.VisualC#基于組件的開發(fā)[M].北京：清華大學(xué)出版社，2005.

[責(zé)任編輯：郭一鶴]

ErrorInfo屬性:獲取表達(dá)式驗(yàn)證后的錯(cuò)誤信息，正確返回為空串；

Result屬性:獲取表達(dá)式計(jì)算結(jié)果，表達(dá)式錯(cuò)誤為空串。

3.Operator類:操作符抽象類，所有運(yùn)算操作符的基類

int GetDimension（） :此方法返回operator操作符的元數(shù)；

G642

：B

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

2010—09—19

肖巍，男，吉林長(zhǎng)春人，長(zhǎng)春師范學(xué)院傳媒科學(xué)學(xué)院教師，研究方向?yàn)閳D像處理與模式識(shí)別、自動(dòng)識(shí)別技術(shù)、嵌入式系統(tǒng)研究。