算數(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)行各種運算時的實現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論。進(jìn)行數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要達(dá)到以下目的：了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程

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

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

4、語法正確、不含變量的算術(shù)表達(dá)式算法優(yōu)先級別：3.3 需求規(guī)格3.3.1 系統(tǒng)總功能1) 系統(tǒng)功能模塊圖7算術(shù)運算式的求解運 算 模 塊判 斷 輸 入 字 符 類 型判斷符號優(yōu)先級基 礎(chǔ) 運 算 函（圖一：系統(tǒng)功能模塊圖 ）2）系統(tǒng)流程圖結(jié)束表達(dá)式計算系統(tǒng)（圖二：系統(tǒng)流程圖）3）數(shù)據(jù)流圖(圖三：數(shù)據(jù)流圖)3.4 功能需求：接受正確表達(dá)是后進(jìn)行計算并輸出結(jié)果。3.5 可靠性和可用性需求：接收錯誤表達(dá)式后反饋提示信息；退出程序時進(jìn)行詢問選擇。3.6 約束 : 僅能輸入規(guī)定字符。如：數(shù)字、運算符號、小數(shù)點、括號、Q、 C、 E。3.7 尚未解決的問題：無法記錄計算過的數(shù)據(jù)。4. 測試用例(2+16)/

5、9 ， 13*3 ， -5+3， -5*21 ， -2/8 ， 2-3 ， 1.0000000*5 ， 0.975000/0.015. 本設(shè)計所采用的數(shù)據(jù)結(jié)構(gòu)/* 操作數(shù)堆棧*/typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆棧*/typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;6. 功能模塊詳細(xì)設(shè)計6.1 棧結(jié)構(gòu)功能功能模塊設(shè)計（段冰倩完成）6.1.1 流程圖（圖四：棧的初始化）結(jié)束（圖五:棧的判空）N（圖六：入棧操作）出棧操作1，9判空

6、返回棧頂下一位（圖七：出棧操作）6.1.2 源代碼/操作數(shù)棧與界符棧初始化Stackl *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->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=

7、0) return 1;else return 0;13/ 界符棧判空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+;numStack->datanumStack->numTop=x;return 1;/ 出棧(操作數(shù))double Pop_num

8、Stack(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+;opStack->dataopStack->opTop=x;return 1;/ 出棧(界符)int Pop_opStack(Stack2 *

9、opStack,char*x)if(Empty_opStack(opStack) return 0;else return(opStack->dataopStack->-opTop);6.2 算術(shù)表達(dá)式計算模塊設(shè)計(王東鵬完成)6.2.1 函數(shù)功能說明:Computer 函數(shù)在本程序的功能是實現(xiàn)數(shù)與運算符號輸入時的判定numResult 函數(shù)在本程序中的功能是通過在computer 函數(shù)中對該函數(shù)的調(diào)用實現(xiàn)存儲在中的數(shù)值運算函數(shù)設(shè)計思路(1 )通過建立一個字符串?dāng)?shù)組存放輸入的數(shù)字字符和運算字符( 2)通過強(qiáng)制轉(zhuǎn)換把字符串類型數(shù)據(jù)轉(zhuǎn)換成雙精度浮點型數(shù)據(jù)( 3)把數(shù)據(jù)和運算界符分別壓棧

10、在兩個棧中，然后通過判斷進(jìn)行比較和出棧運算6.2.2 流程圖 (另附 )6.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='/') return num1/num2;return 0;利用棧結(jié)構(gòu)對算術(shù)表達(dá)式進(jìn)行求解, 分析表達(dá)式*/int compute(char str) /

11、* Init_numStack();Init_opStack();double num=0;17int i=0,j=1,k=1; /*j代表小數(shù)點后位數(shù)，k 代表數(shù)字符號(正負(fù))*/int Flag=0; /*Flag=0表示不是小數(shù)位，1 表示是小數(shù)位*/while(stri!='0'|opStack->opTop>0) /*if(stri>='0'&&stri<='9')/*if(Flag=0)num=num*10+stri-'0'/*elsenum+=(stri-'0'

12、)/(j*10.0);/*如果算術(shù)表達(dá)式不為空*/如果當(dāng)前字符是阿拉伯?dāng)?shù)字字符*/多位數(shù)計算*/小數(shù)計算*/j*=10;else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符*/if(stri='.')/*那么它是否小數(shù)點*/Flag=1; /*設(shè)置標(biāo)志, 表明下一個應(yīng)該是小數(shù)位, 如果下一個不是小數(shù)位 , 應(yīng)該歸零*/else /*如果當(dāng)前字符不是阿拉伯?dāng)?shù)字字符, 也不是小數(shù)點*/if(k=1&&stri='-'&&(i=0|op(stri-1) /* 如果當(dāng)前字符是'-', 符號標(biāo)志為1, 當(dāng)前是第一個字符或前一個字符為

13、'+','-','*','/','('這些字符*/k=-1;elseif(i>0&&!op(stri-1)&&stri!='('&&stri-1!=')')/*i>0且前一字符不是'+','-','*','/','(',')'這些字符, 且當(dāng)前字符不是'('*/*壓num*k入操numStack->datan

14、umStack->numTop+=num*k;作數(shù)堆棧*/num=0; j=1; Flag=0; k=1;if( opStack->opTop=0|stri='(') opStack->dataopStack->opTop+=stri;/*如界符堆棧為空或當(dāng)前字符為'(', 將當(dāng)前字符壓入界符堆棧*/elseif(stri=')') /*若當(dāng)前字符為')'*/while(opStack->opTop>0&&opStack->data-opStack->opTop!=&

15、#39;(')numStack->data numStack->numTop-2=result(numStack->datanumStack->numTop-2,opStack->dataopStack->opTop,numStack->datanumStack->numTop-1);numStack->numTop-; /* 分別從操作數(shù)堆棧, 界符堆棧出棧響應(yīng)元素執(zhí)行計算,結(jié)果送入操作數(shù)堆棧*/* 直到遇到界符'(', 這是正常情況, 或者界符堆棧為空, 這表明表達(dá)式是有錯誤的*/if(opStack->d

16、ataopStack->opTop!='(') return 0;else /*界符堆棧非空, 當(dāng)前字符不是'(', 也不是 ')'*/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-

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

18、ck->numTop!=1|!Empty_opStack(opStack)return 0;return 1;6.3 輸出模塊、優(yōu)先級選擇模塊（宋超峰完成）6.3.1 流程圖（圖九：主函數(shù)流程圖）6.3.2 源代碼int op（char ch） /*將運算符映射為數(shù)字, 表示優(yōu)先級*/if(ch='+'|ch='-') return 2;if(ch='*'|ch=7') return 3;if(ch='(') return -1;return 0;)/*程序主界面*/void view()(system("

19、cls");printf("n");printf("(>n");printf("I算數(shù)表達(dá)式求解I n");printf("< 、n")；printf("II 清除(C)等于(E) 退出(Q) |IIn");printf("'7IIn");printf("(、n");printf("'1 制作： 段冰倩宋超峰楊建波王東鵬 I)n");printf("'7n");) voi

20、d main() (char ch;system("color 03");view();printf（"n請輸入一個長度小于d的算術(shù)表達(dá)式,按'E'得到結(jié)果n",N）;ch=getch();select（ch）;6.4 選擇功能模塊（楊建波完成）6.4.1 流程圖37(圖十：選擇模塊)6.4.2 源代碼void select(char ch) int compute(char str);int i=0,j=0;char strN="0"char numN="0"double temp;while(

21、1 )if(ch='.'|ch=')'|op(ch)|ch>='0'&&ch<='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' )n

22、umj+=ch;numj='0'else j=0; if(ch='C'|ch='c')/*清除數(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",num

23、Stack->data0);j=0; temp=numStack->data0;elseview();printf("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

24、();if(ch='Y'|ch='y') break;else /*否定退出，程序繼續(xù)運行*/view();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 <s

25、tring.h>#define N 100/double numStackN=0;/int numTop; /* 操作數(shù)堆棧棧頂相對棧底的偏移量, 可以用來判斷堆棧是否為空*/char opStackN;/int opTop; /* 界符堆棧棧頂相對棧底的偏移量, 可以用來判斷堆棧是否為空*/* 操作數(shù)堆棧*/typedef structdouble dataN;int numTop;Stack1;Stack1 *numStack;/* 界符堆棧*/typedef structchar dataN;int opTop;Stack2;Stack2 *opStack;/ 操作數(shù)棧與界符棧初始

26、化Stack1 *Init_numStack()numStack=(Stack1*)malloc(sizeof(Stack1);numStack->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;/ 界符棧判空in

27、t 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+;numStack->datanumStack->numTop=x;return 1;/ 出棧(操作數(shù))double Pop_numStack(Stack1 *numStack,char*x)if(Empt

28、y_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+;opStack->dataopStack->opTop=x;return 1;/ 出棧(界符)int Pop_opStack(Stack2 *opStack,char*x)if(Empty_opStack(opSta

29、ck) return 0;else return(opStack->dataopStack->opTop);int op(char ch) /*將運算符映射為數(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) /*if(op='+') return num1+

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

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

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

33、#39;&&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|stri='(') opStack->dataopStack-&

34、gt;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->datanumStack->numTop-2,o pStack->dataopStack-

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

36、;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-opStack->opTop,numStack->datanumStack-&g

37、t;numTop-1);numStack->numTop-; /* 分別從操作數(shù)堆棧, 界符堆棧出棧響應(yīng)元素執(zhí)行計算結(jié)果送操作數(shù)堆棧*/* 直到當(dāng)前運算符的優(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"

38、;);printf("(、n");printf("I算數(shù)表達(dá)式求解I n");printf("( I、n");printf("III 清除(C)等于(E) 退出(Q)|n");printf("''n");printf("(>n");printf("'1 制作： 段冰倩宋超峰楊建波王東鵬 In");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=')'110P(ch)11ch>='0'&