數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計說明書-算術(shù)表達(dá)式求值演算

PAGEPAGE1數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計說明書

學(xué)院、系：軟件學(xué)院專業(yè)軟件工程班級學(xué)生姓名：學(xué)號：設(shè)計題目：算術(shù)表達(dá)式求值演算起迄日期:指導(dǎo)教師:

1需求分析用戶需要實現(xiàn)基本算術(shù)表達(dá)式的求解1.在程序中分別設(shè)計運(yùn)算符棧OPTR和運(yùn)算數(shù)棧OPND。2.用戶以字符串的形式輸入算術(shù)表達(dá)式。3.在讀入表達(dá)式的字符序列的同時，完成運(yùn)算符合運(yùn)算數(shù)的識別處理，以及相應(yīng)的運(yùn)算。4.在識別出運(yùn)算數(shù)的同時，通過sscasnf將其字符序列形式轉(zhuǎn)換為浮點(diǎn)數(shù)序列形式。5.通過分析算符的優(yōu)先關(guān)系，實現(xiàn)對運(yùn)算符棧的操作。6.在程序的適當(dāng)位置輸出運(yùn)算符、運(yùn)算數(shù)、輸入字符和主要操作的內(nèi)容。7.本程序可連續(xù)求解算術(shù)表達(dá)式。8.測試數(shù)據(jù)：9.8+6.916.7008+715.0008/0分母為零不能實現(xiàn)8/24.0003+3-r輸入錯誤，請檢查后重新輸入9.程序執(zhí)行的命令為：1）輸入算術(shù)表達(dá)式；2）求解算術(shù)表達(dá)式；3）輸出表達(dá)式的解。2概要設(shè)計1.設(shè)定棧的抽象數(shù)據(jù)類型定義：ADTStack{數(shù)據(jù)對象：D={ai|aiCharSet,i=1,2,…,n,n>=0}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>|ai-1,aiD,i=2,…,n}基本操作：SElemTypeInitStack(SqStack*S)操作結(jié)果：構(gòu)造一個空棧S。SElemTypeGetTop(SqStack*S)初始條件：棧S已存在。操作結(jié)果：若棧S不空，返回棧頂元素。SElemTypePush(SqStack*S,SElemTypee)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素。SElemTypePop(SqStack*S)初始條件：棧S已存在。操作結(jié)果：若棧不空，刪除S的的棧頂元素；否則，返回ERROR。}ADTStack2.設(shè)定算術(shù)表達(dá)式算法的抽象數(shù)據(jù)類型為：ADTEvaluateExpression{數(shù)據(jù)對象：D={ai,j|ai,j{0,1,2,3,4,5,6,7,8,9,+,-,*,/,#}}數(shù)據(jù)關(guān)系:R=｛<ai,aj>|ai-1,aiD｝基本操作：intIn(charc)操作結(jié)果：若是運(yùn)算符，返回OK；否則，返回ERROR。intshuzhi(charc)操作結(jié)果：返回運(yùn)算符所對應(yīng)的數(shù)字。charPrecede(charOP,charc)操作結(jié)果：比較運(yùn)算符的優(yōu)先級，若OP優(yōu)先級大于c，返回’>’;若OP優(yōu)先級等于c，返回’=’;否則返回’<’。SElemTypeOperate(SElemTypea,charOP,SElemTypeb)操作結(jié)果：返回a和b的運(yùn)算結(jié)果。}ADTEvaluateExpression3.本程序模塊：1）主程序模塊：voidmain(){初始化；While（1）｛接受命令；處理命令；｝2）棧模塊——實現(xiàn)棧抽象收據(jù)類型3）算術(shù)表達(dá)式算法模塊——實現(xiàn)其抽象數(shù)據(jù)類型各模塊之間的調(diào)用關(guān)系如下：主程序模塊▼算術(shù)表達(dá)式模塊▼棧模塊3詳細(xì)設(shè)計1.棧類型typedefstruct{ SElemType*base; inttop; intstacksize;//棧的初始容量}SqStack;棧的基本操作設(shè)置如下：SElemTypeInitStack(SqStack*S)//初始化，設(shè)S為空棧SElemTypeGetTop(SqStack*S)//若棧S不空，返回棧頂元素。否則返回ERROR。SElemTypePush(SqStack*S,SElemTypee)//在棧S的棧頂插入新的棧頂元素。SElemTypePop(SqStack*S)若棧不空，刪除S的的棧頂元素；否則，返回ERROR。其中部分操作的算法:SElemTypePush(SqStack*S,SElemTypee){ if(S->top+1>=S->stacksize) { //棧滿，追加存儲空間 S->base=(SElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)* sizeof(SElemType)); if(!S->base) returnOVERFLOW; S->stacksize+=STACKINCREMENT; } S->base[S->top++]=e; returnOK;}SElemTypePop(SqStack*S){ //若棧不空，則刪除S的棧頂元素，用e返回其值，否則返回ERROR if(S->top==0)returnERROR; returnS->base[--S->top];}SElemTypeGetTop(SqStack*S){ //若棧不空，則用e返回棧頂元素，否則返回ERROR SElemTypee; if(S->top==0)returnERROR; e=S->base[S->top-1]; returne;}2.求算術(shù)表達(dá)式的算法：intEvaluateExpression(){ //算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運(yùn)算符棧 //和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。charOP,e; char*S,C1[20],C[100],buf[100],f;//C[100]存儲輸入的字符串；C1[10]存儲數(shù)據(jù)chari=0,j=0; intd=0,theta; floata,b,w; SqStackp,q; SqStack*OPTR,*OPND;OPTR=&p; OPND=&q; InitStack(OPTR); Push(OPTR,'#'); InitStack(OPND); printf("輸入算術(shù)表達(dá)式:\n");scanf("%s",&buf); sprintf(C,"%s#",buf);//在字符串的結(jié)尾加# while(C[i]!='#'||GetTop(OPTR)!='#') { if(!(C[i]=='+'||C[i]=='-'||C[i]=='*'||C[i]=='/'||C[i]=='('||C[i]==')'||C[i]=='#'||C[i]=='^'||C[i]=='&'||(C[i]>='0'&&C[i]<='9')||C[i]=='.')) { printf("出現(xiàn)非法字符"); printf("%c\n",C[i]); return0; } elseif(!In(C[i]))//如果輸入的不是運(yùn)算符 {C1[j]=C[i];if((C[i+1]>='0'&&C[i+1]<='9')||C[i+1]=='.')//獲取數(shù)據(jù) { if(C[i+1]=='.') { d++; if(d>1) { printf("表達(dá)式錯誤，一個數(shù)據(jù)出現(xiàn)兩個小數(shù)點(diǎn)\n"); return0; } } i++; j++; continue; } i++; j++; /*C1[j]='\0';*/sscanf(C1,"%f",&w);//將其字符序列形式轉(zhuǎn)換為整數(shù)序列形式將字符串c1以整數(shù)形式輸出到w中 j=0; d=0; Push(OPND,w); } elseif(Precede(GetTop(OPTR),C[i])==2)//輸入的是運(yùn)算符 { // 表達(dá)式錯誤 return0; } else { switch(Precede(GetTop(OPTR),C[i])) { case'<'://棧頂元素優(yōu)先權(quán)低 f=C[i]; Push(OPTR,f); i++; break;case'='://脫括號并接受下一字符 Pop(OPTR); i++; break;case'>'://退棧并將運(yùn)算結(jié)果入棧 theta=Pop(OPTR); b=Pop(OPND); a=Pop(OPND); Push(OPND,Operate(a,theta,b)); break; default:break; }//switch } }//while3.函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：主程序▼EvaluateExpression▼InitStackPushInPrecedeGetTopPop▼▼OperateDate▼GetTop4調(diào)試分析1.本程序只有一個核心算法，即求算術(shù)表達(dá)式。在調(diào)試這個算法時，遇到的問題有：其一是，不能將字符串中數(shù)據(jù)的字符序列形式轉(zhuǎn)換為整數(shù)序列形式，后將查找資料可用sscanf簡化之。其二是，由于存儲運(yùn)算符和運(yùn)算數(shù)使用的是同一個棧，在壓棧過程中會發(fā)生錯誤，后經(jīng)調(diào)試分析可將運(yùn)算符字符當(dāng)作浮點(diǎn)型數(shù)據(jù)統(tǒng)一處理。本程序的核心算法——算術(shù)表達(dá)式的時間復(fù)雜度為O(n)。3測試數(shù)據(jù)：測試結(jié)果：9.8+6.916.7008+715.0008/0分母為零不能實現(xiàn)8/24.0003+3-r輸入錯誤，請檢查后重新輸入4測試結(jié)果圖（1）小數(shù)點(diǎn)加法運(yùn)算：整數(shù)加法運(yùn)算：（3）除法分母不能為零（4）正常除法運(yùn)算運(yùn)算錯誤5課程設(shè)計總結(jié)1.在程序中起初不能將字符串中數(shù)據(jù)的字符序列形式轉(zhuǎn)換為整數(shù)序列形式，后將查找資料可用sscanf解決之2.在程序中由于存儲運(yùn)算符和運(yùn)算數(shù)使用的是同一個棧，在壓棧