實驗三算符優(yōu)先算法

1、實驗三：算符優(yōu)先算法一、 實驗?zāi)康模?使用算符優(yōu)先算法將輸入的正則表達式轉(zhuǎn)化位NFA；2加強對算法優(yōu)先算法的理解，加強將正則表達式轉(zhuǎn)化為NFA方法的理解；3強化對系統(tǒng)軟件綜合工程實現(xiàn)能力的訓練。二、 實驗內(nèi)容：用 C 語言或者其他的高級語言開發(fā)完成將輸入的正則表達式轉(zhuǎn)化為NFA的程序。三、 實驗要求：編寫一個程序，能將輸入的正則表達式轉(zhuǎn)化為 NFA，源程序并調(diào)試通過。通過測試程序的驗收；提交實驗報告，報告必須包含以下內(nèi)容：（1）程序功能描述；（2）程序數(shù)據(jù)結(jié)構(gòu)描述；（3）函數(shù)或模塊描述：函數(shù)功能、流程圖，函數(shù)參數(shù)含義、返回值描述；（4）函數(shù)之間的調(diào)用關(guān)系描述和程序總體執(zhí)行流程圖；（5）實驗總結(jié)

2、：你在編程過程中花時多少？多少時間在紙上設(shè)計？多少時間上機輸入和調(diào)試？多少時間在思考問題？遇到了哪些難題？你是怎么克服的？你對你的程序的評價？你的收獲有哪些？（6）手寫實驗報告使用學校要求的實驗稿紙，打印實驗報告使用B5紙打印。四、 評判標準：輸出正確的實驗結(jié)果；代碼清晰，格式良好；提交報告，報告闡述清楚。五、 程序工作說明：程序接受文本文件中輸入的正則表達式，生成該正則表達式對應(yīng)的NFA，在屏幕上顯示出這個 NFA。統(tǒng)計并輸出該 NFA中的節(jié)點個數(shù)和邊的個數(shù)；輸入的正則表達式中包含的運算符包括：連接運算符 ”.”,閉包運算符 “*”,邏輯或運算符 “|”,左括號“(“,右括號 “)”。運算符

3、的運算優(yōu)先級從高到低位(* .|)(4) 輸入的正則表達式中的字符限于大寫英文字母，小寫英文字母，數(shù)字09；(5)NFA使用圖的鄰接鏈表或者鄰接矩陣存儲；程序的調(diào)試者和執(zhí)行者保證輸入的正則表達式正確，程序不檢查正則表達式的正確性。六、結(jié)構(gòu)體和算法流程如果 NFA使用圖的鄰接鏈表存儲，鄰接鏈表中存儲邊信息的結(jié)構(gòu)體：struct Arrowint nEndStateID; /箭弧終點的節(jié)點狀態(tài)IDchar chLetter; /箭弧上標注的字符struct Arrow * pNextArrow; /與當前邊有相同開始接點的下條箭弧;鄰接鏈表中存儲節(jié)點信息的結(jié)構(gòu)體：struct Stateint n

4、StateID; /頂點編號，在整個NFA中定點編號是唯一的struct Arrow *pFirstArrow; /當前頂點的連接的第一條箭弧的指針;NFA 中的狀態(tài)在圖中用圖的節(jié)點表示，NFA 的所有狀態(tài)保存在鄰接鏈表的節(jié)點結(jié)點結(jié)構(gòu)體數(shù)組中，結(jié)構(gòu)體定義：struct NFAstruct State StateListMAX; /int stateCount; /有效的狀態(tài)個數(shù)int arrowCount; /箭弧的個數(shù)表示頭結(jié)點的數(shù)組（就是NFA的狀態(tài)）;每個輸入符號都要生成一個NFA （就是一對開始結(jié)束節(jié)點和中間連著的箭?。?，輸入符號生成的NFA 要進棧，輸入符號對應(yīng)的 NFA 的棧結(jié)構(gòu)體

5、：struct stateStackstruct State * pStateListMAX; /?？臻gint top; /棧頂，棧頂元素在數(shù)組中的下標;正則表達式的運算符棧struct operatorStackchar chOperatorListMAX; /?？臻ginttop; /棧頂，棧頂元素在數(shù)組中的下標;算符優(yōu)先算法初始化狀態(tài)棧；初始化運算符棧；壓進入運算符棧；在正則表達式末尾添加 # 運算符；產(chǎn)生一個初始 0號節(jié)點讀取正則表達式的首符；while( 正則表達式?jīng)]有結(jié)束)if( 當前字符是正則表達式的字符)產(chǎn)生一對新開始和結(jié)束節(jié)點；在開始節(jié)點和結(jié)束節(jié)點之間拉一條標注為當前字符的箭弧

6、；將開始節(jié)點和結(jié)束節(jié)點壓入狀態(tài)棧；讀取下一個字符；elseif( 當前操作符運算優(yōu)先級別比 棧頂運算符優(yōu)先級別高)當前操作符壓入符號棧；讀取下一個字符；else if （當前操作符運算優(yōu)先級別比棧頂運算符優(yōu)先級別低）運算符棧的棧頂運算符出棧；if （出棧運算符是連接符）從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點A ；從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點B ；從 B的結(jié)束節(jié)點拉一條 指示的箭弧到A 的開始節(jié)點；B 的開始節(jié)點和 A 的結(jié)束節(jié)點作為一對開始結(jié)束節(jié)點入狀態(tài)棧；else if( 出棧運算符是邏輯或)從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點A ；從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點B ；生成一對新的開始結(jié)束節(jié)點C；從 C

7、的開始節(jié)點拉一條 指示的箭弧到 A 的開始節(jié)點；從 C的開始節(jié)點拉一條 指示的箭弧到 B的開始節(jié)點；從 A 的結(jié)束節(jié)點拉一條 指示的箭弧到 C的結(jié)束節(jié)點；從 B的結(jié)束節(jié)點拉一條 指示的箭弧到 C的結(jié)束節(jié)點；C的開始節(jié)點和結(jié)束節(jié)點作為一對節(jié)點入狀態(tài)棧；else if（出棧運算符是閉包運算符）從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點A ；生成一對新的開始結(jié)束節(jié)點C；從 C的開始節(jié)點拉一條 指示的箭弧到 A 的開始節(jié)點；從 A 的結(jié)束節(jié)點拉一條 指示的箭弧到 C的結(jié)束節(jié)點；從 A 的結(jié)束節(jié)點拉一條 指示的箭弧到 A 的開始節(jié)點從 C的開始節(jié)點拉一條 指示的箭弧到 C的結(jié)束節(jié)點C的開始節(jié)點和結(jié)束節(jié)點作為一對開始

8、結(jié)束節(jié)點入狀態(tài)棧；else if( 當前操作符運算優(yōu)先級別比棧頂運算符優(yōu)先級別相等)if （棧頂運算符是左括號，當前運算符是右括號）左括號出運算符棧；掃描下個字符；else if（棧頂運算符是#，當前運算符是#）正則表達式處理完成，退出循環(huán)；從狀態(tài)棧中彈出一對開始結(jié)束節(jié)點A ；從 0號節(jié)點拉一條 指示的箭弧到A 的開始節(jié)點；操作說明：產(chǎn)生一對新開始和結(jié)束節(jié)點：就是在結(jié)構(gòu)體 struct NFA 的結(jié)構(gòu)體成員 stateCount 的值增加 2，表示結(jié)構(gòu)體中的成員StateList 數(shù)組中的有效元素增加2 個，數(shù)組的成員是結(jié)構(gòu)體struct State，該結(jié)構(gòu)體有 2個數(shù)據(jù)成員： nStateI

9、D（表示節(jié)點 ID ）和 pFirstArrow （表示這個節(jié)點上出發(fā)的箭弧鏈表） ；設(shè)置新增的2 個數(shù)組成員的StateListstateCount-1 和 StateListstateCount-2 的 nStateID 的值為唯一的狀態(tài) ID ，第一條箭弧的指針pFirstArrow賦值為空；在開始節(jié)點和結(jié)束節(jié)點之間拉一條標注為當前字符的箭弧：在結(jié)構(gòu)體 NFA 的成員 StateList 數(shù)組中查找到開始節(jié)點（找到開始節(jié)點對應(yīng)的下標），該數(shù)組元素是個 struct State 類型的結(jié)構(gòu)體，結(jié)構(gòu)體 struct State 中有個指針成員pFirstArrow ，該指針成員指示的鏈表是所有從這個頂點出發(fā)的箭弧，在這個鏈表中增加一個鏈表元素（可以用頭插法或者尾插法插入） ，表示新增加的邊。 該新增的鏈表元素是個結(jié)構(gòu)體structArrow ，設(shè)置該結(jié)構(gòu)體中的箭弧終點的節(jié)點狀態(tài)nEndStateID 的值為結(jié)束節(jié)點的ID ，箭弧上標注的字符 chLetter 的值為當前字符，箭弧的下一個指針pNextArrow 的值根據(jù)頭使用插入還是尾插法進行不同的設(shè)置；的開始節(jié)點和結(jié)束節(jié)點作為一對開始結(jié)束節(jié)點入狀態(tài)棧：C 實際是結(jié)構(gòu)體NFA 中的成員StateList 數(shù)組中的2 個數(shù)組成員，結(jié)構(gòu)體的str