括號匹配的檢驗

1、湖南工學院計算機與信息科學系課程設計報告20102010學年第一學期課程名稱 數(shù)據(jù)結構設計題目 括號匹配的檢驗 姓名 專業(yè)班級 2 學號 2010 年 12 月 31 日 目錄 1 設計任務書 1.1 題目與要求 1.2 設計中涉及的知識點2 功能設計 2.1抽象數(shù)據(jù)類型的定義 2.2 模塊流程圖3 程序代碼設計與說明 3.1 子程序設計與其功能 3.2 主函數(shù)設計與其功能4 程序設計總結 4.1 程序調(diào)試情況4.2 個人經(jīng)驗及體會5 用戶使用說明6測試結果7 附錄（源程序）1 設計任務書 1.1 題目與要求 問題描述假設表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即（） ）或（

2、 ）等為正確格式，（ ）或（均為不正確的格式。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：()12345678當計算機接受了第1個括號以后，他期待著與其匹配的第8個括號的出現(xiàn)，然而等來的卻是第2個括號，此時第1個括號“”只能暫時靠邊，而迫切等待與第2個括號相匹配的 第7個括號“）”的出現(xiàn)，類似的，因只等來了第3個括號“”，此時，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待緊迫程度高于第2個括號，而第2個括號的期待緊迫程度高于第1個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2

3、個括號的期待匹配就成了最急迫的任務了， ，依次類推。可見這個處理過程正好和棧的特點相吻合。基本要求讀入圓括號和方括號的任意序列，輸出“匹配”或“此串括號匹配不合法”。1.2 設計中涉及的知識點 編譯預處理（文件包含）、選擇結構、循環(huán)結構、堆棧、函數(shù)2 功能設計 2.1抽象數(shù)據(jù)類型的定義 包括堆棧的定義2.2模塊流程圖n 開始輸入括號序列輸出結果輸出結果判斷括號是否匹配y3 程序代碼設計 3.1子程序設計及其功能 （1）函數(shù)原型： stackinitiate(seqstack *s) 功能：初始化堆棧代碼：void stackinitiate(seqstack *s) s-top=0; （2）函

4、數(shù)原型： stacknotempty(seqstack s) 功能： 判斷堆棧是否為空 代碼：int stacknotempty(seqstack s) if(s.toptop=maxstack) printf(堆棧已滿無法插入！n);return 0;elses-stacks-top=x;s-top+;return 1;（4）函數(shù)原型：stackpop(seqstack *s , datatype *d) 功能：堆棧中數(shù)據(jù)元素出棧 代碼：int stackpop(seqstack *s , datatype *d) if(s-toptop-;*d=s-stacks-top;return 1;

5、（5）函數(shù)原型：stacktop(seqstack s , datatype *d) 功能：取堆棧中棧頂元素 代碼：int stacktop(seqstack s , datatype *d)if(s.toptop=0;int stacknotempty(seqstack s) /*判斷非空否*/if(s.toptop=maxstack) printf(堆棧已滿無法插入！n);return 0;elses-stacks-top=x;s-top+;return 1;int stackpop(seqstack *s , datatype *d) /*出棧*/if(s-toptop-;*d=s-st

6、acks-top;return 1;int stacktop(seqstack s , datatype *d)if(s.top=0)printf(堆棧已空！n);return 0;else*d = s.stacks.top-1;return 1;void expiscorrect(char expmaxstack ) /*判斷有n個字符的的字符串exp左、右括號是否配對正確*/seqstack mystack;int i;char c;stackinitiate(&mystack); for (i=0 ; expi != 0 ; i+)if ( ( expi = ( ) | ( expi =

7、 ) )stackpush(&mystack , expi ); /*入棧*/else if ( expi = ) & stacknotempty(mystack) & stacktop(mystack , &c) & c = ()stackpop ( &mystack , &c );else if ( expi = ) & stacknotempty(mystack) & stacktop(mystack , &c) & c != ( )printf(此串括號匹配不合法！n);return;else if ( expi = & stacknotempty(mystack) & stacktop(mystack , &c)& c =)stackpop(&mystack , &c);else if ( expi = & stacknotempty(mystack) & stacktop(mystack , &c)& c != )printf(此串括號匹配不合法！n);return;else if( ( expi =) ) | ( expi = ) & !stacknotempty(mystack) )printf(此串括號匹配不合法！n);return; if ( stacknotempty(my