北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)實(shí)驗(yàn)二

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

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

3、先級(jí)：建立數(shù)組，比較返回大于小于號(hào)。計(jì)算函數(shù)：以字符型輸入，運(yùn)算符號(hào)，用switch來(lái)分支計(jì)算判斷，返回計(jì)算數(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 

4、9;%': return (long int) fmod(x,y);case '': if (y>=0 ) return (long int) pow(x,y); else return (0);default: printf("Error No. 3n"); return 0; 主程序：在主程序內(nèi)，以字符串的形式輸入表達(dá)式，然后分別調(diào)用函數(shù)存入各相應(yīng)棧，然后用數(shù)組判斷，比較運(yùn)算符的優(yōu)先順序。依次輸入，當(dāng)要輸入的算符優(yōu)先級(jí)比已經(jīng)在棧頂?shù)膬?yōu)先級(jí)低，則取出運(yùn)算。while ( *p!='#' | prt.datprt.top-1!=

5、'#' )以#號(hào)作為結(jié)束的標(biāo)志。switch ( refusal(prt.datprt.top-1, *p ) )用來(lái)比較優(yōu)先級(jí)主函數(shù)流程圖： 開 始 循環(huán)模塊輸入表達(dá)式各項(xiàng) 存入模塊存入 判斷模塊是否計(jì)算 輸出棧頂值結(jié) 束四、程序調(diào)試分析 在程序調(diào)試過(guò)程中，對(duì)實(shí)驗(yàn)的步驟并不是非常熟悉，導(dǎo)致實(shí)驗(yàn)的過(guò)程中對(duì)基本的計(jì)算器棧的應(yīng)用不好。其原理是依次讀入表達(dá)式的每一個(gè)字符，把數(shù)字和運(yùn)算符分別存在兩個(gè)不同的棧中，當(dāng)要讀入的運(yùn)算符比已經(jīng)在棧中的運(yùn)算符優(yōu)先級(jí)低時(shí)，則取出運(yùn)算，然后把結(jié)果存入數(shù)棧。優(yōu)先級(jí)的關(guān)系一開始不知道怎么建立，后來(lái)想到了二維數(shù)組，然后在計(jì)算操作函數(shù)的編寫上，出現(xiàn)了問(wèn)題，最后

6、想到了應(yīng)用switch。棧的進(jìn)出和鏈表的區(qū)別還是很大的，在這次實(shí)驗(yàn)中我學(xué)會(huì)掌握了，棧的創(chuàng)立，和存入，出棧等操作，掌握了有關(guān)知識(shí)。同時(shí)比較了，鏈表與棧之間的區(qū)別和聯(lián)系。五、用戶使用說(shuō)明 運(yùn)行程序，程序?qū)υ捒驎?huì)顯示“Expression=”然后輸入表達(dá)式，按回車得出結(jié)果，然后按任意鍵退出程序。六、程序運(yùn)行結(jié)果 七、程序清單#include <stdio.h>#include <math.h>#include <string.h>#define W 0x00char chinput200, *p; /* 運(yùn)算式存儲(chǔ)字符串 */* 運(yùn)算式當(dāng)前讀取位置 */struc

7、t FUHAO/* 建符號(hào)棧 */char dat200;int top;prt;struct SHU/* 建數(shù)字棧 */long int dat200;int top;prd;char PRI99='>','>','<','<','<','<','<','>','>','>','>','<','<','

8、<','<','<','>','>','>','>','>','>','<','<','<','>','>','>','>','>','>','<','<','

9、<','>','>','>','>','>','>','>','<','<','>','>','>','>','>','>','>','<','<','>','

10、>','<','<','<','<','<','<','<','=', W ,'>','>','>','>','>','>',W, '>','>' ,'<','<','<',

11、'<','<','<','<', W ,'=' ;/*優(yōu)先級(jí)列表*/void pushd(long int a)/* 數(shù)字入棧 */prd.datprd.top+=a;void pusht(char a)/* 符號(hào)入棧 */prt.datprt.top+=a;long int popd( )/* 數(shù)字出棧 */return prd.dat-prd.top;char popt( )/* 符號(hào)出棧 */return prt.dat-prt.top;long int numble ( )/* 數(shù)字

12、整理 */long int b=0;dob = b*10 + *p -'0'p+;while ( *p>='0' && *p<='9' ) ;return b;long int operation ( long int x, long int y, char a) /* 數(shù)學(xué)運(yùn)算 */switch(a)case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if (

13、y ) return x/y; else printf("Divide 0.n"); return 0; case '%': return (long int) fmod(x,y);case '': if (y>=0 ) return (long int) pow(x,y); else return (0);default: printf("Error No. 3n"); return 0;int signswitch ( char a )/* 符號(hào)轉(zhuǎn)換 */char signs= '+', '

14、;-', '*', '/', '%', '', '(', ')', '#', '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)先級(jí) */return PRIsignswitch(a)signswitch(b);

15、int main( )int j, k, l, flag=0; /* flag=0前一個(gè)符號(hào)不是) */char b;prt.dat0='#'prt.top=1;prd.top=0;printf ("Enter Expression=");scanf("%s", chinput); /* 接收運(yùn)算式 */strcat( chinput, "#" ); /* 在運(yùn)算式結(jié)尾加#號(hào) */p = chinput;while ( *p!='#' | prt.datprt.top-1!='#' )i

16、f ( *p>='0' && *p<='9') j = numble();/* 如果是數(shù)字進(jìn)行整理并入棧 */pushd(j);else /* 如果是符號(hào)與棧頂?shù)姆?hào)比較并運(yùn)算 */ 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 '<': pusht ( *p+ ); /* 當(dāng)前運(yùn)算符優(yōu)先級(jí)高則運(yùn)算符入棧 */break; /*處理下一個(gè)字符*/case '=': popt( ); /* 脫括號(hào) */ p+; break;case '>': b=popt( ); /* 當(dāng)前運(yùn)算符優(yōu)先級(jí)低