C++課件+案例二十一+括號(hào)嵌套匹配分析器

1、目錄目錄退出退出目錄目錄1頁(yè) 共28頁(yè)案例二十一 括號(hào)嵌套匹配分析器本案例知識(shí)要點(diǎn)字符棧的使用類(lèi)的設(shè)計(jì)和使用目錄目錄退出退出目錄目錄2頁(yè) 共28頁(yè)一、案例需求案例描述本案例通過(guò)編程實(shí)現(xiàn)一個(gè)括號(hào)嵌套匹配分析器。對(duì)文本文件中的代碼按照括號(hào)匹配原則進(jìn)行分析，并對(duì)分析結(jié)果進(jìn)行顯示。與數(shù)學(xué)領(lǐng)域的概念一樣，括號(hào)運(yùn)算先運(yùn)算里層，再運(yùn)算外層。下面是一個(gè)樹(shù)形結(jié)構(gòu)的例子：uRootBranch 00(Leaf 00)Branch 01(Leaf 01)(Leaf 03)Branch 02(Leaf 04)(Leaf 05)這種代碼的規(guī)則是：Root是代碼根節(jié)點(diǎn)；其下有各個(gè)分枝代碼段Branch；Branch下可以

2、是分枝代碼段Branch，也可以是代碼的葉節(jié)點(diǎn)Leaf。這種代碼的特點(diǎn)是：當(dāng)一個(gè)Branch之下的所有Branch和Leaf都執(zhí)行完之后，這個(gè)Branch代碼段才算執(zhí)行完畢；所有Branch的代碼節(jié)點(diǎn)執(zhí)行完畢之后，全部Root代碼才執(zhí)行完畢。目錄目錄退出退出目錄目錄3頁(yè) 共28頁(yè)案例效果圖括號(hào)匹配案例效果如圖所示。括號(hào)匹配案例效果圖 目錄目錄退出退出目錄目錄4頁(yè) 共28頁(yè)功能說(shuō)明利用文件提供的原始代碼。例如：RootBranch 00(Leaf 00)Branch 01(Leaf 01)(Leaf 03)Branch 02(Leaf 04)(Leaf 05)首先按照同類(lèi)括號(hào)匹配的原則檢驗(yàn)上面的

3、代碼，如果不符合要求則提示錯(cuò)誤。如果正確，則按照樹(shù)狀代碼的順序打印出每對(duì)匹配括號(hào)中的字符串。目錄目錄退出退出目錄目錄5頁(yè) 共28頁(yè)二、案例分析本案例的核心思想是利用數(shù)據(jù)結(jié)構(gòu)中棧的工作方式，從代碼數(shù)據(jù)文件中讀取字符，并放入字符棧中。當(dāng)讀到結(jié)束括號(hào)），時(shí)，與棧中最后一個(gè)起始括號(hào)進(jìn)行比較，若匹配則將兩個(gè)括號(hào)區(qū)間中的內(nèi)容從棧中彈出；若括號(hào)不匹配，則報(bào)告錯(cuò)誤；若讀取文件結(jié)束而棧不為空，則報(bào)告錯(cuò)誤；當(dāng)棧為空而試圖讀入結(jié)束括號(hào)時(shí)，報(bào)告錯(cuò)誤。本案例設(shè)計(jì)了兩個(gè)棧，一個(gè)棧charArrayMAXCHAR用于存儲(chǔ)樹(shù)狀代碼中的全部字符，另一個(gè)棧indexMAXSTACK配合第一個(gè)棧記錄其中的全部起始括號(hào)（包括(、 在

4、第一個(gè)棧中的位置，以便將來(lái)讀到結(jié)束括號(hào)（包括）、）時(shí)輸出每個(gè)獨(dú)立的匹配串，例如、Branch 01等。棧charArrayMAXCHAR提供了入棧、出棧、判斷?？盏葪５牟僮?，但是棧indexMAXSTACK只是提供了入棧操作，并未提供出棧操作，程序憑借棧頂元素指針即取出了待匹配的起始括號(hào)在charArrayMAXCHAR 棧中的位置。目錄目錄退出退出目錄目錄6頁(yè) 共28頁(yè)程序運(yùn)行時(shí)，從文件中每讀出一個(gè)字符即壓入棧charArrayMAXCHAR中，如果該字符是起始括號(hào)之一，則立即將其在charArrayMAXCHAR棧的位置壓入第二個(gè)棧index MAXSTACK中。出棧時(shí)借助第二個(gè)棧inde

5、xMAXSTACK對(duì)字符和indexMAXSTACK棧的棧頂元素進(jìn)行比較，如果匹配，則輸出其中的字符串，同時(shí)修改兩個(gè)棧的指針，直至文件和棧都為空為止。案例用到的樹(shù)狀代碼存放在data.txt中，如圖所示，程序使用標(biāo)準(zhǔn)輸入輸出文件流對(duì)數(shù)據(jù)文件進(jìn)行操作。目錄目錄退出退出目錄目錄7頁(yè) 共28頁(yè)data.txt文件內(nèi)容 目錄目錄退出退出目錄目錄8頁(yè) 共28頁(yè)三、案例設(shè)計(jì) 1類(lèi)的設(shè)計(jì) 基于上述分析，本案例需要自定義枚舉類(lèi)型Symbol，并需要設(shè)計(jì)一個(gè)CharStack類(lèi)。 （1）枚舉類(lèi)型Symbol 枚舉類(lèi)型Symbol的結(jié)構(gòu)如圖所示。 （2）CharStack類(lèi)的設(shè)計(jì) CharStack類(lèi)的設(shè)計(jì)如圖所

6、示。目錄目錄退出退出目錄目錄9頁(yè) 共28頁(yè)+0 = common+1 = opening+2 = closeSymbol枚舉類(lèi)型Symbol CharStack 類(lèi)圖 目錄目錄退出退出目錄目錄10頁(yè) 共28頁(yè) 數(shù)據(jù)成員 char charArrayMAXCHAR; 字符棧。 int top; charArrayMAXCHAR棧的棧頂標(biāo)記。 int indexMAXSTACK; 記錄全部起始括號(hào)在字符棧charArrayMAXCHAR中的位置。 int indextop; indexMAXSTACK 棧的棧頂標(biāo)記。目錄目錄退出退出目錄目錄11頁(yè) 共28頁(yè) 函數(shù)成員 CharStack(); 構(gòu)造

7、函數(shù)。 int Push(char ch); 將字符壓入棧。 char* Pop(char *str); 彈出字符串。 bool IsEmpty(void); 測(cè)試是否為空。 bool IsMatch(char ch1, char ch2); 測(cè)試?yán)ㄌ?hào)是否匹配。目錄目錄退出退出目錄目錄12頁(yè) 共28頁(yè) 2主程序設(shè)計(jì) 主程序首先循環(huán)讀入文件中的字符，然后壓棧，判斷括號(hào)是否匹配并作相應(yīng)的處理，如圖所示。目錄目錄退出退出目錄目錄13頁(yè) 共28頁(yè)主程序調(diào)用流程圖 目錄目錄退出退出目錄目錄14頁(yè) 共28頁(yè)四、案例實(shí)現(xiàn)目錄目錄退出退出目錄目錄15頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄16頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄17頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄18頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄19頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄20頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄21頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄22頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄23頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄24頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄25頁(yè) 共28頁(yè)目錄目錄退出退出目錄目錄26頁(yè) 共28