數(shù)據結構課程設計算術表達式求值的實現(xiàn)

1、課課 程程 設設 計計 報報 告告 課程設計名稱：數(shù)據結構課程設計 課程設計題目：算術表達式求值的實現(xiàn) 院（系）：* 專 業(yè)：* 班 級：* 學 號：* 姓 名：* 指導教師：* 目目 錄錄 1 1 課程設計介紹課程設計介紹.1 1.1 課程設計內容.1 1.2 課程設計要求.1 2 2 課程設計原理課程設計原理.2 2.1 課設題目粗略分析.2 2.2 原理圖介紹.2 2.2.1 功能模塊圖.2 2.2.2 流程圖分析.3 3 數(shù)據結構分析數(shù)據結構分析.5 3.1 存儲結構.5 3.2 算法描述.5 4 4 調試與分析調試與分析.7 4.1 調試過程.7 4.2 程序執(zhí)行過程.7 參考文獻參

2、考文獻.8 附附 錄（關鍵部分程序清單）錄（關鍵部分程序清單）.9 1 1 課程設計介紹課程設計介紹 1.11.1 課程設計內容課程設計內容 編寫算法能夠進行整型和實型數(shù)的表達式求值，能夠根據運算的數(shù)據選 擇正確的運算結果的數(shù)據類型，表達式的運算符為：+，*，/， （， ） ，且 括號可以嵌套。 1.21.2 課程設計要求課程設計要求 1.給出必要的輸入、輸出信息和提示信息。 2.參考相應的資料，獨立完成課程設計任務。 3.交規(guī)范課程設計報告和軟件代碼。 2 2 課程設計原理課程設計原理 2.12.1 課設題目粗略分析課設題目粗略分析 根據課設題目要求，擬將整體程序分為三大模塊。此三個模塊相互

3、獨立，沒 有嵌套調用的情況，以下是三個模塊的大體分析： 1.首先依次定義字符類型棧、整型棧、運算符棧和操作數(shù)棧，構造運算符棧 和操作數(shù)棧，然后運算符、操作數(shù)依次入棧。 2. 依次讀入表達式，若是操作符即進 opnd 棧，若是運算符即進 optr 棧。 順序棧的存儲結構是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據元素， 同時附設指針 top 指示棧頂元素在順序棧中的位置，base 為棧底指針，在順序棧 中，它始終指向棧底，即 top=base 可作為?？盏臉擞洠慨敳迦胄碌臈ｍ斣?時，指針 top 增 1，刪除棧頂元素時，指針 top 減 1。 3. 按照運算符的優(yōu)先級別對表達式進行求值

4、運算。 2.22.2 原理圖介紹原理圖介紹 該功能模塊圖介紹了這個程序的主要功能。 2.2.12.2.1 功能模塊圖功能模塊圖 算術表達式求值 存儲 讀取 計算 操 作 數(shù) 入 棧 操 作 符 入 棧 操 作 數(shù) 出 棧 操 作 數(shù) 出 棧 字符 轉換 成浮 點數(shù) + - * / 計 算 圖 2.1 功能模塊圖 如圖 2.1 所示, 要實現(xiàn)表達式的求值，即必須要實現(xiàn)存儲、讀取和計算三項 功能。存儲即運算符、操作數(shù)的入棧；讀取即運算符、操作數(shù)的出棧；計算即 +、*、/的運算。 2.2.22.2.2 流程圖分析流程圖分析 1precede(char c1,char c2) 判斷運算符優(yōu)先權，返回優(yōu)

5、先權高的。 算符間的優(yōu)先關系如下： 表 2.1 運算符優(yōu)先關系列表 +-*/()# + - * / ( #= 2int evalexpr()主要操作函數(shù)。算法概要流程圖： 開始 char c=表達是首字符 n c!=#|gettop(optr)!=# !in(c) 進操作數(shù)棧c=*ptr+ returngettop(opnd) 結束 y case: 操作數(shù)棧頭2個數(shù)進行運算 圖 2.2 主要操作函數(shù)流程圖 3.入棧出棧主要流程。 開始 運算符棧插入ch為新的棧頂元素 操作數(shù)棧插入ch為新的棧頂元素 刪除運算符棧s的棧頂元素，用p返回其值 刪除操作數(shù)棧s的棧頂元素，用p返回其值 用p返回運算符棧

6、s的棧頂元素 用p返回運算符棧s的棧頂元素 結束 圖 2.3 入棧出棧主要流程圖 3 數(shù)據結構分析數(shù)據結構分析 3.13.1 存儲結構存儲結構 因為表達式是由操作符，運算符和界限符組成的。如果只用一個 char 類型 棧，不能滿足 2 位以上的整數(shù)，所以還需要定義一個 int 類型的棧用來寄存操作 數(shù)。 /* 定義字符類型棧 */ typedef struct int stacksize; char *base; char *top; stack; /* 定義整型棧 */ typedef struct int stacksize; int *base; int *top; stack2; 3.

7、23.2 算法描述算法描述 1.棧的基本功能。 initstack(stack *s) 和 initstack2(stack2 *s)分別構造運算符棧與構造 操作數(shù)棧，push(stack *s,char ch) 運算符棧插入 ch 為新的棧頂元素， push2(stack2 *s,int ch) 操作數(shù)棧插入 ch 為新的棧頂元素，pop(stack *s) 刪除運算符棧 s 的棧頂元素，用 p 返回其值，pop2(stack2 *s)刪除操作數(shù)棧 s 的棧頂元素，用 p 返回其值，gettop(stack s)用 p 返回運算符棧 s 的棧頂元素， gettop2(stack2 s) 用

8、p 返回操作數(shù)棧 s 的棧頂元素。 2.其它功能分析。 (1)in(char ch) 判斷字符是否是運算符功能，如果該字符是運算符返回 1， 實現(xiàn)該功能的算法 return(ch=+|ch=-|ch =*|ch=/|ch= (|ch =)|ch=#)。 (2) precede(char c1,char c2) 判斷運算符優(yōu)先權功能，該函數(shù)判斷運算符 c1,c2 的優(yōu)先權，具體優(yōu)先關系參照表 1。 (3) operate(int a,char op,int b)操作數(shù)用對應的運算符進行運算功能。運算結果 直接返回。 (4) num(int n) 求操作數(shù)的長度功能，需要用 itoa 函數(shù)把 in

9、t 型轉換成字符串 型，strlen 函數(shù)可求字符長度。 (5) evalexpr()主要操作函數(shù)運算功能。 4 4 調試與分析調試與分析 4.14.1 調試過程調試過程 在調試程序是主要遇到一下幾類問題： 1.在括號，分號，引號，或者數(shù)據類型上總發(fā)生錯誤。 2.在寫 evalexpr()函數(shù)時，忘了指針的地址符值不用加*號。 3.運行程序時由于忘記更改中英文輸入法，導致輸入中文（） ，程序無法正 cha 常執(zhí)行。 4.程序開始編寫時我僅僅編寫了整型數(shù)的計算，通過修改后改成浮點類型的 運算，使程序可操作性更強。 4.2 程序執(zhí)行過程程序執(zhí)行過程 1.請輸入正確的表達式以#結尾：4*（7-2）#

10、 表達式結果為：20.000000 press any key to continue 2.請輸入正確的表達式以#結尾：11+123*4# 表達式結果為：503.000000 press any key to continue 3.請輸入正確的表達式以#結尾：4.2*(5+1.2)# 表達式結果為：26.040000 press any key to continue 4.請輸入正確的表達式以#結尾：42.6/(3.2+2.8)# 表達式結果為：7.100000 press any key to continue 參考文獻參考文獻 1 嚴蔚敏，吳偉民. .數(shù)據結構m.北京：清華大學出版社，20

11、07. 2 張長海，陳娟. .c 程序設計m.北京：高等教育出版社，2004. 3 譚浩強. .c 程序設計m.北京：清華大學出版社，2005. . 4 丁峻嶺.c 語言程序設計m.北京：中國鐵道出版社，2006. 5 徐孝凱.數(shù)據結構實用教程m.清華大學出版社，2006. 附附 錄（關鍵部分程序清單）錄（關鍵部分程序清單） 程序代碼程序代碼 #include #include #include #define null 0 #define ok 1 #define error -1 #define stack_init_size 100 #define stackincrement 20 /

12、* 定義字符類型棧 */ typedef struct int stacksize; char *base; char *top; stack; /* 定義整型棧 */ typedef struct int stacksize; float *base; float *top; stack2; /* - 全局變量- */ stack optr;/* 定義運算符棧*/ stack2 opnd; /* 定義操作數(shù)棧 */ char expr255 = ; /* 存放表達式串 */ char *ptr = expr; int initstack(stack *s) /構造運算符棧 s-base=(c

13、har *)malloc(stack_init_size*sizeof(char); if(!s-base) return error; s-top=s-base; s-stacksize=stack_init_size; return ok; int initstack2(stack2 *s) /構造操作數(shù)棧 s-base=(float *)malloc(stack_init_size*sizeof(float); if(!s-base) return error; s-stacksize=stack_init_size; s-top=s-base; return ok; int in(ch

14、ar ch) /判斷字符是否是運算符，運算符即返回 1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int push(stack *s,char ch) /運算符棧插入 ch 為新的棧頂元素 *s-top=ch; s-top+; return 0; int push2(stack2 *s,float ch)/操作數(shù)棧插入 ch 為新的棧頂元素 *s-top=ch; s-top+; return 0; char pop(stack *s) /刪除運算符棧 s 的棧頂元素，用 p 返回其值 char p; s-top-; p=*s-top; return

15、 p; float pop2(stack2 *s)/刪除操作數(shù)棧 s 的棧頂元素，用 p 返回其值 float p; s-top-; p=*s-top; return p; char gettop(stack s)/用 p 返回運算符棧 s 的棧頂元素 char p=*(s.top-1); return p; float gettop2(stack2 s) /用 p 返回操作數(shù)棧 s 的棧頂元素 float p=*(s.top-1); return p; /* 判斷運算符優(yōu)先權，返回優(yōu)先權高的 */ char precede(char c1,char c2) int i=0,j=0; stat

16、ic char array49= , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i 為下面 array 的橫標 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j 為下面 arr

17、ay 的縱標 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回運算符 */ /*操作函數(shù) */ float operate(float a,char op,float b) switch(op) case + : return (a+b); case - : return (a-b); case * : re

18、turn (a*b); case / : return (a/b); return 0; int num(float n)/返回操作數(shù)的長度 char p10; int pl; itoa(int)n,p,10);/把整型轉換成字符串型 pl=2*strlen(p); return pl; float evalexpr()/主要操作函數(shù) char c,theta,x; int n; float m; float a,b; c = *ptr+; while(c!=#|gettop(optr)!=#) if(!in(c) if(!in(*(ptr-1) ptr=ptr-1; m=atoi(ptr);/取字符串前面的數(shù)字段 n=num(m); push2( ptr=ptr+n; c=*ptr+; else switch(precede(gettop(optr),c) case : theta=pop( b=pop2( a=pop2( push2( break; return gettop2(opnd); int main( ) printf(請輸入正確的表達式