數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---括號匹配問題

1、<p><b>　　計算機(jī)工程學(xué)院</b></p><p><b>　　課程設(shè)計報告</b></p><p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</p><p>　　設(shè)計題目： 括號匹配問題 </p><p>　　院 系：

2、 計算機(jī)工程學(xué)院 </p><p>　　專 業(yè)： </p><p>　　組 別： </p><p>　　學(xué)生姓名: 學(xué) 號: <

3、/p><p>　　起止日期: 年月日 ~年月日 </p><p>　　指導(dǎo)教師: </p><p><b>　　目錄</b></p><p><b>　　1.需求分析2</b></p><p>　　1.1課程設(shè)計題目2</p>&

4、lt;p>　　1.2 課程設(shè)計任務(wù)及要求2</p><p>　　1.3 課程設(shè)計思想2</p><p>　　1.4軟硬件運行環(huán)境及開發(fā)工具2</p><p><b>　　1.概要設(shè)計2</b></p><p>　　2.1課題設(shè)計的流程圖2</p><p>　　2.2主要的數(shù)據(jù)結(jié)構(gòu)

5、3</p><p><b>　　3.詳細(xì)設(shè)計4</b></p><p>　　3.1課題設(shè)計的方法及原理4</p><p>　　3.2主要代碼實現(xiàn)4</p><p>　　4.調(diào)試與操作說明5</p><p><b>　　5.總結(jié)與體會6</b></p>

6、<p><b>　　6.致謝7</b></p><p><b>　　7．參考文獻(xiàn)7</b></p><p><b>　　1.需求分析</b></p><p><b>　　1.1課程設(shè)計題目</b></p><p><b>　　括號匹

7、配問題</b></p><p>　　1.2 課程設(shè)計任務(wù)及要求</p><p>　　假設(shè)一個算術(shù)表達(dá)式中可包含三種括號：圓括號，方括號和花括號且這三種括號可按任意次序嵌套使用。試?yán)脳５倪\算，編寫判別給定表達(dá)式中所含括號是否正確配對出現(xiàn)的算法。</p><p>　　1.3 課程設(shè)計思想</p><p>　　利用棧來判斷括號是否匹配

8、時，遇到左括號就進(jìn)棧，遇到右括號則左括號出棧，代表這對括號匹配，如果右括號進(jìn)棧時，棧為空，則說明缺少左括號，若表達(dá)式掃描完棧為空，則說明表達(dá)式的括號匹配，否則說明表達(dá)式缺少左括號。</p><p>　　1.4軟硬件運行環(huán)境及開發(fā)工具</p><p>　　Microsoft visual C++ 6.0</p><p><b>　　1.概要設(shè)計</b&

9、gt;</p><p>　　2.1課題設(shè)計的流程圖</p><p>　　2.2主要的數(shù)據(jù)結(jié)構(gòu)</p><p>　　棧類包括如下數(shù)據(jù)成員和成員函數(shù)</p><p>　　top; //指向棧頂?shù)闹羔?LinkStack();

10、 //構(gòu)造函數(shù)</p><p>　　bool isEmpty(); //判斷棧是否為空</p><p>　　void Push(T x);//x進(jìn)棧，top指向x</p><p>　　T Pop();//棧頂元素出棧</p><p>　　T GetPop(); / /讀取棧頂元素 bo

11、ol Search(T x); //搜素棧中是否有x這個元素 void OutPut(); //輸出棧內(nèi)所有元素</p><p><b>　　3.詳細(xì)設(shè)計</b></p><p>　　3.1課題設(shè)計的方法及原理</p><p>　　1）定義三個棧 s1,s2,s3分別用來判斷

12、圓括號，方括號和花括號是否匹配</p><p>　　2）對s1,s2,s3均有如下操作：</p><p>　　a.利用動態(tài)指針p依次對輸入的（字符串）表達(dá)式進(jìn)行掃描</p><p>　　I.若為左括號，則進(jìn)棧</p><p>　　II若為右括號，則先取棧頂元素。若棧頂元素為空，則缺少左括號；若不為空，則棧頂元素出棧</p>&l

13、t;p>　　b.當(dāng)字符串掃描完，檢驗棧是否為空。若為空，則括號正確匹配。否則表示缺少右括號</p><p><b>　　3.2主要代碼實現(xiàn)</b></p><p>　　sign1 ,sign2 ,sign3是分別用來標(biāo)記棧是否為空</p><p>　　while(*p!='#')</p><p>&

14、lt;b>　　{</b></p><p>　　switch(*p)</p><p><b>　　{</b></p><p><b>　　case'(':</b></p><p>　　s1.Push(*p);</p><p><b>

15、　　break;</b></p><p><b>　　case')':</b></p><p>　　if(s1.isEmpty())</p><p><b>　　{</b></p><p>　　sign1=false;</p><p>　　cout

16、<<"缺少'('"<<endl;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　s1.Pop();</b></p><p><b>　　br

17、eak;</b></p><p><b>　　case'[':</b></p><p>　　s2.Push(*p);</p><p><b>　　break;</b></p><p><b>　　case']':</b></p&

18、gt;<p>　　if(s2.isEmpty())</p><p><b>　　{</b></p><p>　　sign2=false;</p><p>　　cout<<"缺少'['"<<endl;</p><p><b>　　}<

19、/b></p><p><b>　　else</b></p><p><b>　　s2.Pop();</b></p><p><b>　　break;</b></p><p><b>　　case'{':</b></p>

20、<p>　　s3.Push(*p);</p><p><b>　　break;</b></p><p><b>　　case'}':</b></p><p>　　if(s3.isEmpty())</p><p><b>　　{</b></p&g

21、t;<p>　　sign3=false;</p><p>　　cout<<"缺少'{'"<<endl;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　

22、　s3.Pop();</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>

23、<p><b>　　p++;</b></p><p><b>　　}</b></p><p><b>　　4.調(diào)試與操作說明</b></p><p>　　檢驗圓括號是否正確匹配</p><p>　　檢驗方括號是否正確匹配</p><p>　　

24、綜合檢驗三種括號是否正確匹配</p><p><b>　　5.總結(jié)與體會</b></p><p>　　通過本次課程設(shè)計，我對棧有了更加深入的了解。雖然本次實驗只是利用棧解決了括號匹配問題，但是查閱關(guān)于棧的資料知道了利用棧的后進(jìn)先出特點還能解決很多問題。例如利用?？蓪⑦f歸算法轉(zhuǎn)化為非遞歸算法。此外棧還是系統(tǒng)實現(xiàn)嵌套調(diào)用機(jī)制的基礎(chǔ)。本實驗只解決了表達(dá)式中括號匹配問題，應(yīng)再

25、改進(jìn)判斷算數(shù)表達(dá)式是否合法。</p><p><b>　　6.致謝</b></p><p><b>　　。。。。。。</b></p><p><b>　　7．參考文獻(xiàn)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)（C++版）葉核亞 主編 機(jī)械工業(yè)出版社</p><p