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

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

2、序設(shè)計1、概要設(shè)計 抽象數(shù)據(jù)類型定義：兩個棧構(gòu)造，分別用來儲存數(shù)據(jù)和計算符號 宏定義：函數(shù)“成功，“失敗的返回值 在主程序程序中先依次輸入各表達式，存入相應各棧，然后 ，調(diào)用“判斷函數(shù)來判斷計算符的優(yōu)先次序，然后再利用計算函數(shù)來計算，表達式值。其中還有，取棧頂元素函數(shù)，存入棧函數(shù)。2、詳細設(shè)計數(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 '

4、%': 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)，以字符串的形式輸入表達式，然后分別調(diào)用函數(shù)存入各相應棧，然后用數(shù)組判斷，比擬運算符的優(yōu)先順序。依次輸入，當要輸入的算符優(yōu)先級比已經(jīng)在棧頂?shù)膬?yōu)先級低，那么取出運算。while ( *p!='*' | prt.datprt.top-1!=&#

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

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

7、* 建符號棧 */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)先級列表*/void pushd(long int a)/* 數(shù)字入棧 */prd.datprd.top+=a;void pusht(char a)/* 符號入棧 */prt.datprt.top+=a;long int popd( )/* 數(shù)字出棧 */return prd.dat-prd.top;char popt( )/* 符號出棧 */return prt.dat-prt.top;long int numble ( )/* 數(shù)字整理 */lon

12、g 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ù)學運算 */switch(a)case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y ) retu

13、rn 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 )/* 符號轉(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)先級 */return PRIsignswitch(a)signswitch(b);int main

15、( )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&g

16、t;='0' && *p<='9') j = numble();/* 如果是數(shù)字進展整理并入棧 */pushd(j);else /* 如果是符號與棧頂?shù)姆柋葦M并運算 */ 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+ ); /* 當前運算符優(yōu)先級高那么運算符入棧 */break; /*處理下一個字符*/case '=': popt( ); /* 脫括號 */ p+; break;case '>': b=popt( ); /* 當前運算符優(yōu)先級低那么進