1、中北大學數(shù)據(jù)結構課程設計說明書學院：電子與計算機科學技術學院班級：1121010F02題目：算術表達式的求解指導教師陳夠喜學生學號1121010705112101071411210110171121011016學生姓名段冰倩宋超峰王東鵬楊建波成績2013 年 1 月 17 日1 . 設計目的數(shù)據(jù)結構 課程主要介紹最常用的數(shù)據(jù)結構， 闡明各種數(shù)據(jù)結構內(nèi)在的邏輯關系， 討 論其在計算機中的存儲表示， 以及在其上進行各種運算時的實現(xiàn)算法， 并對算法的效率進行 簡單的分析和討論。進行數(shù)據(jù)結構課程設計要達到以下目的：了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力； 初步掌握軟件開發(fā)過程

2、的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能； 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科 學的工作方法和作風。2. 設計內(nèi)容和要求2.1 設計內(nèi)容：（ 1）本案例要求從鍵盤中輸入一串四則運算表達式， 由計算機求出表達式的運算結果。（2）要求能夠判斷公式的正確性，如括號是否匹配，有沒有算術表達式之外的字符（ 3 ）對于有錯的表達式，要提示出錯信息（4）對于正確的表達式，能夠正確求出值2.2 設計要求：（1） 符合課題要求，實現(xiàn)相應功能；（2） 要求界面友好美觀，操作方便易行；（3） 注意程序的實用

3、性、安全性；3. 需求分析3.1 系統(tǒng)概述表達式求值運算式實現(xiàn)程序設計語言基本問題之一，也是棧的應用的典型例子。深入了解棧和隊列的特性，學會在實際應用中靈活運用。3.2 需求概述3.2.1 目標a. 軟件開發(fā)意圖、目標及范圍 : 本案例要求從鍵盤中輸入一串四則運算表達式， 由計算機求出表達式的運算結果 ; 要求能夠判斷公式的正確性，如括號是否匹 配，有沒有算術表達式之外的字符 ; 對于有錯的表達式，要提示出錯信息。b. 主要功能、處理流程、數(shù)據(jù)流程 :3.2.2 運行環(huán)境PC 微機DOS 操作系統(tǒng)或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(huán)境3.2

4、.3 約束條件 以字符序列的形式從終端輸入語法正確、不含變量的算術表達式 算法優(yōu)先級別：3.3 需求規(guī)格3.3.1 系統(tǒng)總功能1）系統(tǒng)功能模塊圖11算術運算式的求解疋初義始棧化結棧構1片f主 函 數(shù) 模 塊mai nr判 棧 空運 算 模 塊判 斷 輸 入 字 符 類 型判斷符號優(yōu)先級基 礎 運 算 函 數(shù)運 算 函 數(shù)（圖一：系統(tǒng)功能模塊圖 ）2）系統(tǒng)流程圖（圖二：系統(tǒng)流程圖）3）數(shù)據(jù)流圖(圖三：數(shù)據(jù)流圖)3.4 功能需求：接受正確表達是后進行計算并輸出結果。3.5 可靠性和可用性需求：接收錯誤表達式后反饋提示信息；退出程序時進行詢問選擇。3.6 約束 : 僅能輸入規(guī)定字符。如：數(shù)字、運算符

5、號、小數(shù)點、括號、Q、C、E。3.7 尚未解決的問題：無法記錄計算過的數(shù)據(jù)。4. 測試用例(2+16)/9 ，13*3 ， -5+3 ， -5*21 ，-2/8 ，2-3 ，1.0000000*5 ，0.975000/0.014. 本設計所采用的數(shù)據(jù)結構/* 操作數(shù)堆棧 */typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆棧 */typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;5.功能模塊詳細設計5.1棧結構功能功能模塊設計（段冰倩完成）5

6、.1.2流程圖初始化棧結構開辟內(nèi)存空間棧頂賦初值結束（圖四：棧的初始化）返回0結束（圖五：棧的判空）（圖六：入棧操作）出棧操作N（圖七：出棧操作）返回棧頂下一位155.1.3源代碼/操作數(shù)棧與界符棧初始化Stackl *lnit_nu mStack()nu mStack=(Stack1*)malloc(sizeof(Stack1);nu mStack->nu mTop=0;return nu mStack;Stack2 *ln it_opStack()opStack=(Stack2*)malloc(sizeof(Stack2);opStack->opTop=0;return opS

7、tack;/操作數(shù)棧判空int Empty_ numStack(Stack1 *n umStack)if(numStack->numTop=0) return 1;else return 0;/ 界符棧判空int Empty_opStack(Stack2 *opStack)if(opStack->opTop=0) return 1;else return 0;/ 入棧(操作數(shù))int Push_numStack(Stack1 *numStack,char x)if(numStack->numTop=N-1) return 0;elsenumStack->numTop+;

8、numStack->datanumStack->numTop=x;return 1;/ 出棧(操作數(shù))double Pop_numStack(Stack1 *numStack,char*x)if(Empty_numStack(numStack) return 0;else return(numStack->datanumStack->numTop);/ 入棧(界符)int Push_opStack(Stack2 *opStack,char x)if(opStack->opTop=N-1) return 0;elseopStack->opTop+;opStac

9、k->dataopStack->opTop=x;return 1;/ 出棧(界符)int Pop_opStack(Stack2 *opStack,char*x)if(Empty_opStack(opStack) return 0;else return(opStack->dataopStack->-opTop);5.2 算術表達式計算模塊設計(王東鵬完成)5.2.1 函數(shù)功能說明 :Computer 函數(shù)在本程序的功能是實現(xiàn)數(shù)與運算符號輸入時的判定numResult 函數(shù)在本程序中的功能是通過在 computer 函數(shù)中對該函數(shù)的調(diào)用實現(xiàn)存儲在 中的數(shù)值運算函數(shù)設計思路

10、( 1)通過建立一個字符串數(shù)組存放輸入的數(shù)字字符和運算字符 (2)通過強制轉(zhuǎn)換把字符串類型數(shù)據(jù)轉(zhuǎn)換成雙精度浮點型數(shù)據(jù) (3)把數(shù)據(jù)和運算界符分別壓棧在兩個棧中，然后通過判斷進行比較和出棧 運算5.2.2 流程圖 (另附 )5.2.3 源代碼double result(double num1,char op,double num2) /* 執(zhí)行運算 */if(op='+') return num1+num2;if(op='-') return num1-num2;if(op='*') return num1*num2;if(op='/

11、9;) return num1/num2;return 0;int compute(char str)/* 利用棧結構對算術表達式進行求解, 分析表達式 */ Init_numStack();Init_opStack();double num=0;int i=0,j=1,k=1; /*j代表小數(shù)點后位數(shù)，k 代表數(shù)字符號(正負)*/int Flag=0; /*Flag=0表示不是小數(shù)位，1 表示是小數(shù)位 */如果算術表達式不為空 */while(stri!='0'|opStack->opTop>0) /*if(stri>='0'&&am

12、p;stri<='9') /*if(Flag=0)num=num*10+stri-'0' /*elsenum+=(stri-'0')/(j*10.0); /*如果當前字符是阿拉伯數(shù)字字符 */多位數(shù)計算 */小數(shù)計算 */j*=10;else /* 如果當前字符不是阿拉伯數(shù)字字符 */ if(stri='.') /* 那么它是否小數(shù)點 */Flag=1; /* 設置標志 , 表明下一個應該是小數(shù)位 , 如果下一個不是小 數(shù)位 ,應該歸零 */else /* 如果當前字符不是阿拉伯數(shù)字字符 , 也不是小數(shù)點 */if( k=1

13、&&stri='-'&&(i=0|op(stri-1) ) /* 如果當前字符是 '-', 符號標志為 1, 當前是第一個字符或前一個字符為 '+','-','*','/','(' 這些字符 */ k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是 '+','

14、;-','*','/','(',')' 這些字符 , 且當前字符不是 '('*/numStack->datanumStack->numTop+=num*k;/* 壓 num*k 入操作數(shù)堆棧 */num=0; j=1; Flag=0; k=1;if( opStack->opTop=0|stri='(')opStack->dataopStack->opTop+=stri;/* 如界符堆棧為空 或當前字符為 '(', 將當前字符壓入界符堆棧 */el

15、seif(stri=')') /* 若當前字符為 ')'*/while(opStack->opTop>0&&opStack->data-opStack->opTop!='(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,o pStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStac

16、k->numTop-; /* 分別從操作數(shù)堆棧 , 界符堆棧出棧響應元素執(zhí)行計算,結果送入操作數(shù)堆棧 */* 直到遇到界符 '(', 這是正常情況 , 或者界符堆棧為空 , 這表明表達式是有錯誤的 */ if(opStack->dataopStack->opTop!='(') return 0;else /* 界符堆棧非空 , 當前字符不是 '(', 也不是 ')'*/if(stri='0'&&numStack->numTop=0) return 0; /* 如果表達式結束

17、, 或操作數(shù)堆棧已空 , 返回調(diào)用處 */ while(opStack->opTop>0&&op(stri)<=op(opStack->dataopStack->opTop-1) numStack->datanumStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->data-opStack->opTop,numStack->datanumStack->numTop-1); numStack->numTop-; /* 分

18、別從操作數(shù)堆棧 , 界符堆棧出棧響應元素執(zhí)行計算 結果送操作數(shù)堆棧 */* 直到當前運算符的優(yōu)先級低于棧元素的優(yōu)先級, 把當前字符壓棧 */if(stri!='0')opStackopTop+=stri; if(stri!='0') i+;if( numStack->numTop!=1|!Empty_opStack(opStack)return 0;return 1;5.3 輸出模塊、優(yōu)先級選擇模塊(宋超峰完成)5.3.1 流程圖(圖九 ：主函數(shù)流程圖)5.3.2 源代碼int op(char ch) /* 將運算符映射為數(shù)字 , 表示優(yōu)先級 */if(c

19、h='+'|ch='-') return 2;if(ch='*'|ch='/') return 3;if(ch='(') return -1;return 0;/* 程序主界面 */ void view()system("cls");n");n");printf("printf("printf("II算數(shù)表達式求解n");printf("n");printf("II清除 (C) 等于 (E) 退出 (Q)I

20、IIIn");printf("IIIIn");printf("IIIIn");printf("制作： 段冰倩 宋超峰 楊建波 王東鵬n");printf("n");void main()char ch;system("color 03");view();printf("n請輸入一個長度小于d的算術表達式，按'E'得到結果n",N);ch=getch();select(ch);5.4 選擇功能模塊(楊建波完成)5.4.1 流程圖25(圖十：選擇模塊)5

21、.4.2 源代碼void select(char ch) int compute(char str);int i=0,j=0;char strN="0"char numN="0"double temp;while( 1 )if(ch='.'|ch=')'|op(ch)|ch>='0'&&ch<='9')stri+=ch;stri='0'view();printf("n請輸入一個長度小于d的算術表達式，按'E'得到結果n&q

22、uot;,N);printf("%s",str);if( ch='-'&&(i=1|op(stri-2)|ch>='0'&&ch<='9' )numj+=ch;numj='0'else j=0;if(ch='C'|ch='c') /* 清除數(shù)據(jù) */if(strlen(str)str-i='0'view();printf("n 請輸入一個長度小于 %d 的 算 術 表 達 式 , 按 'E' 得

23、 到 結 果 n",N);printf("%s",str);if(ch='E'|ch='e') /* 求算術表達式的值 */if(compute(str)printf("n=%gn",numStack->data0);j=0; temp=numStack->data0;elseview();printf("n 請輸入一個長度小于 %d 的 算 術 表 達 式 , 按 'E' 得 到 結 果 n",N);printf("%s",str);print

24、f("n 輸入的算術表達式有誤 !");i=0; j=0; str0='0'if(ch='Q'|ch='q') /* 退出程序 */printf("n退出？(是 Y/否 N) n");ch=getch();if(ch='Y'|ch='y') break;else /*否定退出，程序繼續(xù)運行 */view();printf("n請輸入一個長度小于 %d 的 算 術 表 達 式 , 按 'E' 得 到 結 果n",N);printf("

25、;%s",str);ch=getch();6. 源代碼#include <stdio.h>#include <conio.h>#include <stdlib.h>#include <process.h> #include <string.h>#define N 100/double numStackN=0;, 可以用來判斷堆棧是否為空 */, 可以用來判斷堆棧是否為空 */int numTop; /* 操作數(shù)堆棧棧頂相對棧底的偏移量/char opStackN;/int opTop; /* 界符堆棧棧頂相對棧底的偏移量/*

26、 操作數(shù)堆棧 */typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆棧 */typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;/ 操作數(shù)棧與界符棧初始化Stack1 *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->numTop=0;return numStack;Stack2 *Init_opStack()opStack=(Stack2*)malloc(s

27、izeof(Stack2);opStack->opTop=0;return opStack;/ 操作數(shù)棧判空int Empty_numStack(Stack1 *numStack)if(numStack->numTop=0) return 1;else return 0;/ 界符棧判空int Empty_opStack(Stack2 *opStack)if(opStack->opTop=0) return 1;else return 0;/ 入棧(操作數(shù))int Push_numStack(Stack1 *numStack,char x)if(numStack->num

28、Top=N-1) return 0;elsenumStack->numTop+; numStack->datanumStack->numTop=x; return 1;/ 出棧(操作數(shù))double Pop_numStack(Stack1 *numStack,char*x)if(Empty_numStack(numStack) return 0;else return(numStack->datanumStack->numTop);/ 入棧(界符)int Push_opStack(Stack2 *opStack,char x)if(opStack->opTo

29、p=N-1) return 0;elseopStack->opTop+; opStack->dataopStack->opTop=x;return 1;/ 出棧(界符)int Pop_opStack(Stack2 *opStack,char*x)if(Empty_opStack(opStack) return 0;else return(opStack->dataopStack->opTop);int op(char ch) /* 將運算符映射為數(shù)字 , 表示優(yōu)先級 */ if(ch='+'|ch='-') return 2;if(

30、ch='*'|ch='/') return 3;if(ch='(') return -1;return 0;執(zhí)行運算 */double result(double num1,char op,double num2) /* if(op='+') return num1+num2; if(op='-') return num1-num2;if(op='*') return num1*num2;if(op='/') return num1/num2; return 0;int comput

31、e(char str)/* 利用棧結構對算術表達式進行求解, 分析表達式 */ Init_numStack();Init_opStack();double num=0;int i=0,j=1,k=1; /*j代表小數(shù)點后位數(shù)，k 代表數(shù)字符號（正負）*/int Flag=0; /*Flag=0表示不是小數(shù)位，1 表示是小數(shù)位 */如果算術表達式不為空 */while(stri!='0'|opStack->opTop>0) /* if(stri>='0'&&stri<='9') /*if(Flag=0)num

32、=num*10+stri-'0' /*elsenum+=(stri-'0')/(j*10.0); /*如果當前字符是阿拉伯數(shù)字字符 */多位數(shù)計算 */小數(shù)計算 */37j*=10;else /* 如果當前字符不是阿拉伯數(shù)字字符 */if(stri='.') /*那么它是否小數(shù)點 */Flag=1;/*設置標志 , 表明下一個應該是小數(shù)位 , 如果下一個不是小數(shù)位 ,應該歸零 */else /*如果當前字符不是阿拉伯數(shù)字字符 , 也不是小數(shù)點*/if(k=1&&stri='-'&&(i=0|op(s

33、tri-1) /*如果當前字符是符號標志為 1, 當前是第一個字符或前一個字符為 '+','-','*','/','這些字符 */k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是 '+','-','*','/','(',')'這些字符 , 且當前字符不是&

34、#39;('*/numStack->datanumStack->numTop+=num*k;/* 壓 num*k 入操作數(shù)堆棧 */num=0; j=1; Flag=0; k=1;if( opStack->opTop=0|stri='(')opStack->dataopStack->opTop+=stri;/*如界符堆棧為空或當前字符為 '(', 將當前字符壓入界符堆棧 */elseif(stri=')') /*若當前字符為 ')'*/while(opStack->opTop>0&

35、amp;&opStack->data-opStack->opTop!='(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分別從操作數(shù)堆棧 , 界符堆棧出棧響應元素執(zhí)行計算結果送入操作數(shù)堆棧 */* 直到遇到界符 '(',

36、 這是正常情況 , 或者界符堆棧為空 , 這表明表達式是有錯誤的 */if(opStack->dataopStack->opTop!='(') return 0;else /* 界符堆棧非空 , 當前字符不是 '(', 也不是 ')'*/if(stri='0'&&numStack->numTop=0) return 0; /*如果表達式結束 , 或操作數(shù)堆棧已空 , 返回調(diào)用處 */ while(opStack->opTop>0&&op(stri)<=op(opS

37、tack->dataopStack->opTop-1)numStack->datanumStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->data-opStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分別從操作數(shù)堆棧 , 界符堆棧出棧響應元素執(zhí)行計算 結果送操作數(shù)堆棧 */* 直到當前運算符的優(yōu)先級低于棧元素的優(yōu)先級 , 把當前字符壓棧 */if(stri!=&

38、#39;0')opStackopTop+=stri;if(stri!='0')i+;if( numStack->numTop!=1|!Empty_opStack(opStack)return 0;return 1;/* 程序主界面 */void view()system("cls");n");printf("printf("printf("printf(" n");printf(" n");printf(" n");printf(" n

39、");printf(" n");printf("IIIIIIn");II算數(shù)表達式求解n");清除 (C) 等于 (E) 退出 (Q)IIIIIIII制作： 段冰倩 宋超峰 楊建波 王東鵬n");void select(char ch) int compute(char str);int i=0,j=0;char strN="0"char numN="0"double temp;while( 1 )if(ch='.'|ch=')'|op(ch)|ch>='0'&&ch<='9')stri+=ch;stri='0'view();pr