北京理工大學數(shù)據(jù)結(jié)構(gòu)與算法設計實驗二VIP

1、數(shù)據(jù)結(jié)構(gòu)與算法設計實驗報告實驗二學院：自動化學院班級： 06111001 學號： 1120100001姓名： 寶競宇 一、 實驗目的 掌握棧的建立，輸入，刪除，出棧等基本操作。應用棧解決實際問題。二、實驗內(nèi)容 實現(xiàn)簡單計算器的功能,請按照四則運算加、減、乘、除、冪（）和括號的優(yōu)先關(guān)系和慣例，編寫計算器程序。要求支持運算符：+、-、*、/、%、（）和=： 從鍵盤輸入一個完整的表達式，以回車作為表達式輸入結(jié)束的標志； 輸入表達式中的數(shù)值均為大于等于零的整數(shù)，如果中間計算過程中出現(xiàn)小數(shù)也只取整進行計算。例如，輸入：4+2*5=輸出：14 輸入：(4+2)*(2-10)=輸出：-48三、程序設計 1、

2、概要設計 抽象數(shù)據(jù)類型定義：兩個棧結(jié)構(gòu)，分別用來儲存數(shù)據(jù)和計算符號 宏定義：函數(shù)“成功”，“失敗的返回值” 在主程序程序中先依次輸入各表達式，存入相應各棧，然后 ，調(diào)用“判斷函數(shù)”來判斷計算符的優(yōu)先次序，然后再利用計算函數(shù)來計算，表達式值。其中還有，取棧頂元素函數(shù)，存入棧函數(shù)。 2、詳細設計數(shù)據(jù)類型實現(xiàn)：struct tchar dat200; int top;prt;入棧函數(shù)：存入數(shù)組，棧頂指針上移void pushd(long int a)prd.datprd.top+=a;出棧：取出對應值，棧頂指針下移 long int popd( )return prd.dat-prd.top;比較優(yōu)

3、先級：建立數(shù)組，比較返回大于小于號。計算函數(shù)：以字符型輸入，運算符號，用switch來分支計算判斷，返回計算數(shù)值 long int operation ( long int x, long int y, char a) switch(a)case +: return x+y;case -: return x-y;case *: return x*y;case /: if ( y ) return x/y; else printf(Divide 0.n); return 0; case %: return (long int) fmod(x,y);case : if (y=0 ) return

4、(long int) pow(x,y); else return (0);default: printf(Error No. 3n); return 0; 主程序：在主程序內(nèi)，以字符串的形式輸入表達式，然后分別調(diào)用函數(shù)存入各相應棧，然后用數(shù)組判斷，比較運算符的優(yōu)先順序。依次輸入，當要輸入的算符優(yōu)先級比已經(jīng)在棧頂?shù)膬?yōu)先級低，則取出運算。while ( *p!=# | prt.datprt.top-1!=# )以#號作為結(jié)束的標志。switch ( refusal(prt.datprt.top-1, *p ) )用來比較優(yōu)先級主函數(shù)流程圖： 開 始 循環(huán)模塊輸入表達式各項 存入模塊存入 判斷模塊是

5、否計算 輸出棧頂值結(jié) 束四、程序調(diào)試分析 在程序調(diào)試過程中，對實驗的步驟并不是非常熟悉，導致實驗的過程中對基本的計算器棧的應用不好。其原理是依次讀入表達式的每一個字符，把數(shù)字和運算符分別存在兩個不同的棧中，當要讀入的運算符比已經(jīng)在棧中的運算符優(yōu)先級低時，則取出運算，然后把結(jié)果存入數(shù)棧。優(yōu)先級的關(guān)系一開始不知道怎么建立，后來想到了二維數(shù)組，然后在計算操作函數(shù)的編寫上，出現(xiàn)了問題，最后想到了應用switch。棧的進出和鏈表的區(qū)別還是很大的，在這次實驗中我學會掌握了，棧的創(chuàng)立，和存入，出棧等操作，掌握了有關(guān)知識。同時比較了，鏈表與棧之間的區(qū)別和聯(lián)系。五、用戶使用說明 運行程序，程序?qū)υ捒驎@示“Ex

6、pression=”然后輸入表達式，按回車得出結(jié)果，然后按任意鍵退出程序。六、程序運行結(jié)果 七、程序清單#include #include #include #define W 0x00char chinput200, *p; /* 運算式存儲字符串 */* 運算式當前讀取位置 */struct FUHAO/* 建符號棧 */char dat200;int top;prt;struct SHU/* 建數(shù)字棧 */long int dat200;int top;prd;char PRI99=,W, , ,=0 & *p=0 ) return (long int) pow(x,y); else r

7、eturn (0);default: printf(Error No. 3n); return 0;int signswitch ( char a )/* 符號轉(zhuǎn)換 */char signs= +, -, *, /, %, , (, ), #, 0 ;int k;k = 0;while ( signsk!=0 & signsk != a )k+;if ( signsk = a ) return k;else return -1;char refusal ( char a,char b ) /* 判定優(yōu)先級 */return PRIsignswitch(a)signswitch(b);int m

8、ain( )int j, k, l, flag=0; /* flag=0前一個符號不是) */char b;prt.dat0=#;prt.top=1;prd.top=0;printf (Enter Expression=);scanf(%s, chinput); /* 接收運算式 */strcat( chinput, # ); /* 在運算式結(jié)尾加#號 */p = chinput;while ( *p!=# | prt.datprt.top-1!=# )if ( *p=0 & *p=9) j = numble();/* 如果是數(shù)字進行整理并入棧 */pushd(j);else /* 如果是符號與棧頂?shù)姆柋容^并運算 */ if ( flag=1 & *p=( ) printf(Error No.1:%sn, p); return 0;else if ( *p=) flag=1; else flag=0;switch ( refusal(prt.datprt.top-1, *p ) )case : b=popt( ); /* 當前運算符優(yōu)先級低則進行棧頂計算 */ k=popd(); /* 第二操作數(shù)出棧 */ l=popd(); /* 第一操作數(shù)出棧 */ k=operation(l,k,b); /* 計算