英昌盛

(吉林師范大學(xué) 計算機(jī)學(xué)院，吉林 四平 136000)

0 引言

表達(dá)式的分析、求值等運(yùn)算是編譯程序中的一個關(guān)鍵部分。研究翻譯程序的工作原理和工作流程，對于教師的教學(xué)和研究，對于學(xué)生理論聯(lián)系實際都具有較為實用的意義和價值。

1 系統(tǒng)設(shè)計及概要設(shè)計

1.1 運(yùn)算符和數(shù)據(jù)類型的支持

系統(tǒng)支持算術(shù)運(yùn)算、關(guān)系運(yùn)算和邏輯運(yùn)算。算術(shù)運(yùn)算符有包括:()、+、-、*、/、^(乘方)，其中^為新增運(yùn)算符。邏輯運(yùn)算符包括:!、＆(邏輯與為化簡運(yùn)算符)、|(邏輯或為化簡運(yùn)算符)。關(guān)系運(yùn)算符包括:＞、＞=、==、_(負(fù)號)。

系統(tǒng)支持整數(shù)及浮點數(shù)。在進(jìn)行算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算時運(yùn)算規(guī)則和結(jié)合性基本同C語言中相應(yīng)的規(guī)則一致。

1.2 數(shù)據(jù)結(jié)構(gòu)

用戶輸入的數(shù)據(jù)是隨機(jī)的，同時程序處理數(shù)據(jù)時用棧這種結(jié)構(gòu)實現(xiàn)較好，所以系統(tǒng)采用兩個鏈棧［1］來保存運(yùn)算量和運(yùn)算符。因輸入的變量個數(shù)無法確定，系統(tǒng)采用動態(tài)生成鏈表［2］來存儲。

2 系統(tǒng)實現(xiàn)

2.1 算符優(yōu)先級及數(shù)據(jù)結(jié)構(gòu)

系統(tǒng)使用結(jié)構(gòu)體數(shù)組charindex［］和OPTable［］保存運(yùn)算符及其對應(yīng)的優(yōu)先級。charindex［］用來存放運(yùn)算符和該運(yùn)算符的棧外、內(nèi)優(yōu)先級在OPTable［］中的下標(biāo)。charindex［］結(jié)構(gòu)體數(shù)組的op域用來保存第i個運(yùn)算符，index域用來存放第i個運(yùn)算符在OPTable［］結(jié)構(gòu)體數(shù)組相應(yīng)元素中的下標(biāo)，如表1［3］所示。

表1 運(yùn)算符及其棧內(nèi)、外優(yōu)先級

OPTable［］的opri域和ipri域分別表示charindex［］數(shù)組中第i個運(yùn)算符對應(yīng)的棧外、棧內(nèi)優(yōu)先級。為方便運(yùn)算和節(jié)省棧的域，OPTable［］的元素個數(shù)較charindex［］的元素個數(shù)多三項。系統(tǒng)只用一個整數(shù)表示一個運(yùn)算符，而＞=，==，＜=等運(yùn)算符都是兩個字符組成的字符串，不便于統(tǒng)一處理，經(jīng)研究發(fā)現(xiàn)完全可以用＜、=、＞三個運(yùn)算符的在OPTable［］中的下標(biāo)值分別加1來表示＜=、==、＞=在OPTable［］中的下標(biāo)值，因而＜、=、＞三者之間的索引值按2遞增。具體定義如下:

2.2 處理規(guī)則

(1)初始化時在運(yùn)算棧內(nèi)壓入一個#;同時#作為表達(dá)式結(jié)束標(biāo)記。

(2)若棧外運(yùn)算符的棧外優(yōu)先級比棧頂運(yùn)算符的棧內(nèi)優(yōu)先級高，則棧外運(yùn)算符入棧;否則棧頂運(yùn)算符退棧，并取出相應(yīng)個數(shù)的運(yùn)算量進(jìn)行運(yùn)算，把運(yùn)算結(jié)果壓回運(yùn)算量棧，直到棧外運(yùn)算符的棧外優(yōu)先級比棧頂運(yùn)算符的棧內(nèi)優(yōu)先級高為止，將棧外運(yùn)算符入棧;若棧外運(yùn)算符的棧外優(yōu)先級和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級相等，則棧頂運(yùn)算符一定為’(’，此時為()的情況，作出錯處理。

(3)運(yùn)算符退棧時，若遇到棧外運(yùn)算符的棧外優(yōu)先級和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級相等情況(此時一定是括號)，則彈出棧頂運(yùn)算符，拋棄棧外運(yùn)算符。

(4)若運(yùn)算完畢運(yùn)算量棧只剩一個運(yùn)算量、符號?？?，則運(yùn)算結(jié)果正確，其他情況則為錯誤。

(5)若 a＞0，則 -a=a*(-1)。

(6)程序中不支持在表達(dá)式中有賦值運(yùn)算。即若遇到‘=’而其后的第一個字符不是‘=’則認(rèn)為出錯。

2.3 核心實現(xiàn)

函數(shù)evaluate用于求解經(jīng)過規(guī)范化的用戶輸入表達(dá)式，有四個參數(shù):s為經(jīng)過規(guī)范化后的用戶輸入表達(dá)式;s1為運(yùn)算量棧指針;s2為運(yùn)算符棧指針;s3為變量鏈表指針。程序中首先定義了一些臨時變量，然后在運(yùn)算符棧內(nèi)壓入#的索引及其棧外、棧內(nèi)優(yōu)先級作為標(biāo)記如下:

s2=pushstack(s2，0，1，1);/*#的索引、棧內(nèi)外級入棧*/

在表達(dá)式未結(jié)束且已掃描過的部分表達(dá)式合法的情況下循環(huán)處理。若是數(shù)字或小數(shù)點則進(jìn)入數(shù)值處理分支并繼續(xù)讀取，并將運(yùn)算量壓入運(yùn)算量棧中。若讀到的是字母，則進(jìn)入變量分支，并在變量表中進(jìn)行查找變量值并壓入運(yùn)算量棧之中。

對于運(yùn)算符首先查找運(yùn)算符表，然后在OPTable［］表中找到其對應(yīng)的棧內(nèi)、外優(yōu)先級，并對棧外運(yùn)算符的棧外優(yōu)先級和棧頂運(yùn)算符的棧內(nèi)優(yōu)先級作相應(yīng)的比較，根據(jù)比較結(jié)果進(jìn)行相應(yīng)的運(yùn)算。

［1］嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社出版，2009.

［2］譚浩強(qiáng).C語言程序設(shè)計教程［M］.4版.北京:清華大學(xué)出版社出版，2010.

［3］唐策善.數(shù)據(jù)結(jié)構(gòu)—用C語言描述.［M］.北京:高等教育出版社，2003.