肖 巍
(長(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á)式的常見方式,而前綴和后綴表示法主要用于計(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)換成用后綴表示法表示的等價(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é)果字符串。
對(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)該為空。
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í)的類型。
本文通過對(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)研究。