算數(shù)表達(dá)式求解課程設(shè)計說明書

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

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

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

4、序集成環(huán)境或 Visual C+ 程序集成環(huán)境 3.2.3 約束條件 以字符序列的形式從終端輸入語法正確、不含變量的算術(shù)表達(dá)式 算法優(yōu)先級別： 3.3需求規(guī)格3.3.1系統(tǒng)總功能1)系統(tǒng)功能模塊圖算術(shù)運(yùn)算式的求解棧模塊主函數(shù)模塊main運(yùn)算模塊初始化棧定義棧結(jié)構(gòu)出棧入棧判?？张袛噍斎胱址愋团袛喾杻?yōu)先級基礎(chǔ)運(yùn)算函數(shù)運(yùn)算函數(shù) （ 圖一：系統(tǒng)功能模塊圖 ）2） 系統(tǒng)流程圖算數(shù)表達(dá)式求解系統(tǒng) 輸入表達(dá)式輸出“表達(dá)式錯誤”表達(dá)式是否正確 N Y求解運(yùn)算輸出計算結(jié)果是否退出 N Y結(jié)束表達(dá)式計算系統(tǒng) （圖二：系統(tǒng)流程圖）3)數(shù)據(jù)流圖 （圖三：數(shù)據(jù)流圖）3.4功能需求：接受正確表達(dá)是后進(jìn)行計算并輸出結(jié)果

5、。3.5可靠性和可用性需求：接收錯誤表達(dá)式后反饋提示信息；退出程序時進(jìn)行詢問選擇。3.6約束:僅能輸入規(guī)定字符。如：數(shù)字、運(yùn)算符號、小數(shù)點(diǎn)、括號、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.01 4.本設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)/*操作數(shù)堆棧*/typedef struct double dataN; int numTop;Stack1;Stack1 *numStack;/*界符堆棧*/typedef struct char dataN; int opTop;

6、Stack2;Stack2 *opStack;5.功能模塊詳細(xì)設(shè)計5.1 棧結(jié)構(gòu)功能功能模塊設(shè)計（段冰倩完成）5.1.2流程圖初始化棧結(jié)構(gòu) 開辟內(nèi)存空間棧頂賦初值結(jié)束 （圖四：棧的初始化）棧的判空函數(shù)棧頂是否為0 N Y返回0返回1結(jié)束 （圖五：棧的判空）入棧函數(shù) 棧滿判斷 N棧頂上移一位 Y返回0賦值返回1結(jié)束 （圖六：入棧操作） 出棧操作判空 N Y返回棧頂下一位結(jié)束 （圖七：出棧操作）5.1.3源代碼/操作數(shù)棧與界符棧初始化Stack1 *Init_numStack() numStack=(Stack1*)malloc(sizeof(Stack1); numStack->numTo

7、p=0; return numStack;Stack2 *Init_opStack() opStack=(Stack2*)malloc(sizeof(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

8、 0;/入棧（操作數(shù)）int Push_numStack(Stack1 *numStack,char x) if(numStack->numTop=N-1) return 0; else numStack->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-&g

9、t;numTop);/入棧（界符）int Push_opStack(Stack2 *opStack,char x) if(opStack->opTop=N-1) return 0; else opStack->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);5.2

10、 算術(shù)表達(dá)式計算模塊設(shè)計（王東鵬完成）5.2.1函數(shù)功能說明:Computer函數(shù)在本程序的功能是實(shí)現(xiàn)數(shù)與運(yùn)算符號輸入時的判定Result函數(shù)在本程序中的功能是通過在computer函數(shù)中對該函數(shù)的調(diào)用實(shí)現(xiàn)存儲在num 中的數(shù)值運(yùn)算函數(shù)設(shè)計思路（1）通過建立一個字符串?dāng)?shù)組存放輸入的數(shù)字字符和運(yùn)算字符 （2）通過強(qiáng)制轉(zhuǎn)換把字符串類型數(shù)據(jù)轉(zhuǎn)換成雙精度浮點(diǎn)型數(shù)據(jù) （3）把數(shù)據(jù)和運(yùn)算界符分別壓棧在兩個棧中，然后通過判斷進(jìn)行比較和出棧 運(yùn)算5.2.2 流程圖(另附) 5.2.3源代碼double result(double num1,char op,double num2) /*執(zhí)行運(yùn)算*/ if(op

11、='+') return num1+num2; if(op='-') return num1-num2; if(op='*') return num1*num2; if(op='/') return num1/num2; return 0; int compute(char str) /*利用棧結(jié)構(gòu)對算術(shù)表達(dá)式進(jìn)行求解,分析表達(dá)式*/ Init_numStack(); Init_opStack(); double num=0; int i=0,j=1,k=1; /*j代表小數(shù)點(diǎn)后位數(shù)，k代表數(shù)字符號（正負(fù)）*/ int Flag=

12、0; /*Flag=0表示不是小數(shù)位，1表示是小數(shù)位*/ while(stri!='0'|opStack->opTop>0) /*如果算術(shù)表達(dá)式不為空*/ if(stri>='0'&&stri<='9') /*如果當(dāng)前字符是阿拉伯?dāng)?shù)字字符*/ if(Flag=0) num=num*10+stri-'0' /*多位數(shù)計算*/ else num+=(stri-'0')/(j*10.0); /*小數(shù)計算*/ j*=10; else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符*/ if(st

13、ri='.') /*那么它是否小數(shù)點(diǎn)*/ Flag=1; /*設(shè)置標(biāo)志,表明下一個應(yīng)該是小數(shù)位,如果下一個不是小數(shù)位,應(yīng)該歸零*/ else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符,也不是小數(shù)點(diǎn)*/ if( k=1&&stri='-'&&(i=0|op(stri-1) ) /*如果當(dāng)前字符是'-',符號標(biāo)志為1,當(dāng)前是第一個字符或前一個字符為'+','-','*','/','('這些字符*/ k=-1; else if(i>0&

14、;&!op(stri-1)&&stri!='('&&stri-1!=')') /*i>0且前一字符不是'+','-','*','/','(',')'這些字符,且當(dāng)前字符不是'('*/ numStack->datanumStack->numTop+=num*k; /*壓num*k入操作數(shù)堆棧*/ num=0; j=1; Flag=0; k=1; if( opStack->opTop=0|st

15、ri='(') opStack->dataopStack->opTop+=stri;/*如界符堆棧為空或當(dāng)前字符為'(',將當(dāng)前字符壓入界符堆棧*/ else if(stri=')') /*若當(dāng)前字符為')'*/ while(opStack->opTop>0&&opStack->data-opStack->opTop!='(') numStack->data numStack->numTop-2=result(numStack->datanumS

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

17、#39;)'*/ if(stri='0'&&numStack->numTop=0) return 0; /*如果表達(dá)式結(jié)束,或操作數(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-opStac

18、k->opTop,numStack->datanumStack->numTop-1); numStack->numTop-; /*分別從操作數(shù)堆棧,界符堆棧出棧響應(yīng)元素執(zhí)行計算,結(jié)果送操作數(shù)堆棧*/ /*直到當(dāng)前運(yùn)算符的優(yōu)先級低于棧元素的優(yōu)先級,把當(dāng)前字符壓棧*/ if(stri!='0') opStackopTop+=stri; if(stri!='0') i+; if( numStack->numTop!=1|!Empty_opStack(opStack) return 0; return 1; 5.3 輸出模塊、優(yōu)先級選擇模塊

19、（宋超峰完成）5.3.1流程圖 （圖九 ：主函數(shù)流程圖）5.3.2源代碼int op(char ch) /*將運(yùn)算符映射為數(shù)字,表示優(yōu)先級*/ if(ch='+'|ch='-') return 2; if(ch='*'|ch='/') return 3; if(ch='(') return -1; return 0; /*程序主界面*/void view() system("cls"); printf(" n"); printf(" n"); printf

20、(" 算數(shù)表達(dá)式求解 n"); printf(" n"); printf(" 清除 (C) 等于 (E) 退出 (Q) n"); printf(" n"); printf(" n"); printf(" 制作： 段冰倩 宋超峰 楊建波 王東鵬 n"); printf(" n"); void main() char ch; system("color 03"); view(); printf("n請輸入一個長度小于%d的算術(shù)表達(dá)

21、式,按'E'得到結(jié)果 n",N); ch=getch(); select(ch);5.4 選擇功能模塊（楊建波完成）5.4.1流程圖 （圖十：選擇模塊）5.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<=

22、'9') stri+=ch; stri='0' view(); printf("n請輸入一個長度小于%d的算術(shù)表達(dá)式,按'E'得到結(jié)果 n",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')

23、 /*清除數(shù)據(jù)*/ if(strlen(str) str-i='0' view(); printf("n請輸入一個長度小于%d的算術(shù)表達(dá)式,按'E'得到結(jié)果 n",N); printf("%s",str); if(ch='E'|ch='e') /*求算術(shù)表達(dá)式的值*/ if(compute(str) printf("n=%gn",numStack->data0); j=0; temp=numStack->data0; else view(); printf(&

24、quot;n請輸入一個長度小于%d的算術(shù)表達(dá)式,按'E'得到結(jié)果 n",N); printf("%s",str); printf("n輸入的算術(shù)表達(dá)式有誤!"); 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ù)運(yùn)行*/ view();

25、 printf("n請輸入一個長度小于%d的算術(shù)表達(dá)式,按'E'得到結(jié)果 n",N); printf("%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ù)堆棧棧頂相對棧底的偏移量

26、,可以用來判斷堆棧是否為空*/char opStackN; /int opTop; /*界符堆棧棧頂相對棧底的偏移量,可以用來判斷堆棧是否為空*/*操作數(shù)堆棧*/typedef struct double dataN; int numTop;Stack1;Stack1 *numStack;/*界符堆棧*/typedef struct char dataN; int opTop;Stack2;Stack2 *opStack;/操作數(shù)棧與界符棧初始化Stack1 *Init_numStack() numStack=(Stack1*)malloc(sizeof(Stack1); numStack-&

27、gt;numTop=0; return numStack;Stack2 *Init_opStack() opStack=(Stack2*)malloc(sizeof(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; els

28、e return 0;/入棧（操作數(shù)）int Push_numStack(Stack1 *numStack,char x) if(numStack->numTop=N-1) return 0; else numStack->numTop+; numStack->datanumStack->numTop=x; return 1; /出棧（操作數(shù)）double Pop_numStack(Stack1 *numStack,char*x) if(Empty_numStack(numStack) return 0; else return(numStack->datanum

29、Stack->numTop);/入棧（界符）int Push_opStack(Stack2 *opStack,char x) if(opStack->opTop=N-1) return 0; else opStack->opTop+; opStack->dataopStack->opTop=x; return 1; /出棧（界符）int Pop_opStack(Stack2 *opStack,char*x) if(Empty_opStack(opStack) return 0; else return(opStack->dataopStack->opT

30、op);int op(char ch) /*將運(yùn)算符映射為數(shù)字,表示優(yōu)先級*/ if(ch='+'|ch='-') return 2; if(ch='*'|ch='/') return 3; if(ch='(') return -1; return 0; double result(double num1,char op,double num2) /*執(zhí)行運(yùn)算*/ if(op='+') return num1+num2; if(op='-') return num1-num2; if

31、(op='*') return num1*num2; if(op='/') return num1/num2; return 0; int compute(char str) /*利用棧結(jié)構(gòu)對算術(shù)表達(dá)式進(jìn)行求解,分析表達(dá)式*/ Init_numStack(); Init_opStack(); double num=0; int i=0,j=1,k=1; /*j代表小數(shù)點(diǎn)后位數(shù)，k代表數(shù)字符號（正負(fù)）*/ int Flag=0; /*Flag=0表示不是小數(shù)位，1表示是小數(shù)位*/ while(stri!='0'|opStack->opTop&

32、gt;0) /*如果算術(shù)表達(dá)式不為空*/ if(stri>='0'&&stri<='9') /*如果當(dāng)前字符是阿拉伯?dāng)?shù)字字符*/ if(Flag=0) num=num*10+stri-'0' /*多位數(shù)計算*/ else num+=(stri-'0')/(j*10.0); /*小數(shù)計算*/ j*=10; else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符*/ if(stri='.') /*那么它是否小數(shù)點(diǎn)*/ Flag=1; /*設(shè)置標(biāo)志,表明下一個應(yīng)該是小數(shù)位,如果下一個不是小數(shù)位,應(yīng)該歸零

33、*/ else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符,也不是小數(shù)點(diǎn)*/ if( k=1&&stri='-'&&(i=0|op(stri-1) ) /*如果當(dāng)前字符是'-',符號標(biāo)志為1,當(dāng)前是第一個字符或前一個字符為'+','-','*','/','('這些字符*/ k=-1; else if(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')

34、9;) /*i>0且前一字符不是'+','-','*','/','(',')'這些字符,且當(dāng)前字符不是'('*/ 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;/*如界符堆棧為空或當(dāng)前字符為

35、'(',將當(dāng)前字符壓入界符堆棧*/ else if(stri=')') /*若當(dāng)前字符為')'*/ while(opStack->opTop>0&&opStack->data-opStack->opTop!='(') numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanu

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

37、 0; /*如果表達(dá)式結(jié)束,或操作數(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->numTo

38、p-; /*分別從操作數(shù)堆棧,界符堆棧出棧響應(yīng)元素執(zhí)行計算,結(jié)果送操作數(shù)堆棧*/ /*直到當(dāng)前運(yùn)算符的優(yōu)先級低于棧元素的優(yōu)先級,把當(dāng)前字符壓棧*/ if(stri!='0') opStackopTop+=stri; if(stri!='0') i+; if( numStack->numTop!=1|!Empty_opStack(opStack) return 0; return 1; /*程序主界面*/void view() system("cls"); printf(" n"); printf(" n&q

39、uot;); printf(" 算數(shù)表達(dá)式求解 n"); printf(" n"); printf(" 清除 (C) 等于 (E) 退出 (Q) n"); printf(" n"); printf(" n"); printf(" 制作： 段冰倩 宋超峰 楊建波 王東鵬 n"); printf(" 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>=