算術表達式求值課設報告

數(shù)據(jù)結構課程設計設計說明書表達式求值算法的實現(xiàn)（（（）（）（（學生姓名學號班級成績指導教師數(shù)學與計算機科學學院2012年9月7日數(shù)據(jù)結構課程設計評閱書題目表達式求值算法的實現(xiàn)學生姓名學號指導教師評語及成績成績：教師簽名：年月日答辯教師評語及成績成績：教師簽名：年月日教研室意見總成績：室主任簽名：年月日注：指導教師成績60%，答辯成績40%，總成績合成后按五級制記入課程設計任務書2023—2023學年第2學期專業(yè)學號：姓名：課程設計名稱：數(shù)據(jù)結構課程設計設計題目：表達式求值算法的實現(xiàn)完成期限：自2023年8月28日至2023年9月7日共2周棧的存儲和相關運算是數(shù)據(jù)結構中數(shù)組部分的重點知識和技能。表達式求值算法可借助棧來完成，它的存儲可以使用順序結構也可以使用鏈式結構，這要根據(jù)具體的應用來決定。本課程設計按以下的要求運用C/C++結構體、指針、數(shù)據(jù)結構等基知識編程實現(xiàn)。任務要求：1）闡述設計思想,畫出流程圖;2）任意輸入一個表達式（算術、邏輯、關系表達式）；3）建立棧；4）借助棧的相關運算完成表達式求值過程;5）將表達式及其運算結果按照其數(shù)學形式打印輸出;6）說明測試方法,寫出完整的運行結果,較好的界面設計；7）按照格式要求完成課程設計說明書。設計要求:1）問題分析和任務定義：根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？確定問題的輸入數(shù)據(jù)集合。2）邏輯設計：對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結構為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設計的結果應寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結構的描述和每個基本操作的功能說明），各個主要模塊的算法，并畫出模塊之間的調用關系圖；3）詳細設計：定義相應的存儲結構并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設計的結果是對數(shù)據(jù)結構和基本操作做出進一步的求精，寫出數(shù)據(jù)存儲結構的類型定義，寫出函數(shù)形式的算法框架；4）程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；5）程序調試與測試：能夠熟練掌握調試工具的各種功能，設計測試數(shù)據(jù)確保程序正確。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果；6）結果分析：程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法的時間、空間復雜性分析；7）編寫課程設計報告；指導教師（簽字）：教研室主任（簽字）：批準日期：年月日摘要本次課程設計利用visualc++6.0編程軟件，運用c語言、指針、結構體、數(shù)據(jù)結構中棧的相關知識編寫了表達式求值算法的程序。為了實現(xiàn)算符優(yōu)先算法使用兩個工作棧，一個稱為OPTR，用以寄存運算符；另一個稱做OPND，用以寄存操作數(shù)或運算結果。依次讀入表達式，若是操作符即進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應的操作，直至整個表達式求值完畢，最終實現(xiàn)了任意表達式求值的簡單運算。關鍵詞：指針;結構體;棧目錄1課題描述12設計要求22.1設計具體要求22.2總體規(guī)劃23邏輯設計與分析33.1舉例分析33.2算法核心34算法流程圖44.1主算法流程圖44.2主要算法流程代碼55詳細設計65.1順序棧的建立65.2函數(shù)及對應程序76程序測試106.1合法數(shù)據(jù)輸入106.2非法數(shù)據(jù)輸入11總結12查考文獻131課題描述隨著現(xiàn)代科學技術的迅猛發(fā)展，計算機技術已經滲透到各個領域，成為各行業(yè)必不可少的工具.借助現(xiàn)從識經濟時代的特點，對國民經濟建設提出了“用信息化帶動工業(yè)化”的指導思想。對常用算法的實現(xiàn)與比較操作而言，全面開發(fā)和應用計算機操作系統(tǒng)就是近期不能回避的問題。由于計算機技術的發(fā)展，許多復雜的數(shù)值問題才得以解決。一個數(shù)學問題，乃至一個數(shù)值計算公式，如何在計算機上實現(xiàn)，而在計算機處理計算的過程中又會產生哪些新問題，這是在實際應用算法操作中經常會遇到的課題。在計算機中，算術表達式由常量、變量、運算符和括號組成。由于不同的運算符具有不同的優(yōu)先級，又要考慮括號，因此，算術表達式的求值不可能嚴格地從左到右進行。因而在程序設計時，借助棧實現(xiàn)。算法輸入：一個算術表達式，由常量、變量、運算符和括號組成（以字符串形式輸入）。為簡化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為+、-*、/，用#表示結束。算法輸出：表達式運算結果。算法要點：設置運算符棧和運算數(shù)棧輔助分析算符優(yōu)先關系。在讀入表達式的字符序列的同時，完成運算符和運算數(shù)的識別處理，以及相應運算。開發(fā)工具：VisualC++2設計要求2.1設計具體要求運用c/c++、指針、結構體、數(shù)據(jù)結構中棧的相關知識編寫任意表達式求值算法的實現(xiàn)。2.2總體規(guī)劃主函數(shù)只要是表達式的輸入再通過調用EvaluateExpression()函數(shù)進行運算數(shù)、運算符等相關處理，最后輸出結果。如圖2.1結果輸出結果輸出主函數(shù)main（）表達式輸入調用EvaluateExpression()圖2.1總體規(guī)劃圖3邏輯設計與分析3.1舉例分析如下表3.1是對3*(7-2)的求值分析步驟。特別說明當在計算除法運算時如果分母為’0’步驟OPTR棧OPND棧輸入字符主要操作1#3*(7-2)#Push(OPND,’3’2#3*(7-2)#Push(OPTR,’*’)3#*3(7-2)#Push(OPNR,’(’)4#*(37-2)#Push(OPND,’7’5#*(37-2)#Push(OPNR,’-’)6#*(-372)#Push(OPND,’2’7#*(-372)#Operate(‘7’,’-’,’28#*(35)#Pop(OPTR)9#*35#Operate(‘3’,’*’,510#15#Return(GetTop2(OPND))表3.1例子分析3.2算法核心為了實現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€工作棧。一個稱為OPTR，用以寄存運算符，另一個稱做OPND，用以寄存操作數(shù)或運算結果。（1）首先置操作數(shù)棧為空棧，表達式起始符”#”為運算符棧的棧底元素；（2）依次讀入表達式，若是操作符即進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應的操作，直至整個表達式求值完畢（即OPTR棧的棧頂元素和當前讀入的字符均為”#”）。4算法流程圖4.1主算法流程圖如下圖4.1給出了主要算法控制流程圖：結束結束輸入表達式進操作數(shù)棧OPND,同時棧頂上移YYN判斷棧頂優(yōu)先級Case’<’:棧頂元素優(yōu)先權低Case’=’:脫括號接受下一個字符Case’>’:退棧并將運算結果入棧N開始是運算符？判斷字符不是#?同時棧頂字符不是#？“#”結束運算操作數(shù)出棧計算結果，棧頂上移并把結果返回Y圖4.1主算法流程圖4.2主要算法流程代碼/**************************************算術表達式求值的算符優(yōu)先算法。設OPTR和OPND分別為運算符棧和運算數(shù)棧，OPSET為運算符集合。***************************************/SqStack<char>OPTR;//運算符棧，字符元素SqStack<float>OPND;//運算數(shù)棧，實數(shù)元素charTempData[20];floatData,a,b;chartheta,c,x,Dr[2];InitStack<SqStack<char>,char>(OPTR);Push(OPTR,'#');InitStack<SqStack<float>,float>(OPND);strcpy(TempData,"\0");//將TempData置為空c=getchar();while(c!='#'||GetTop<SqStack<char>,char>(OPTR)!='#'){if(!In(c,OPSET)){Dr[0]=c;Dr[1]='\0';//存放單個數(shù)strcat(TempData,Dr);//將單個數(shù)連到TempData中，形成字符串c=getchar();if(In(c,OPSET))//如果遇到運算符，則將字符串TempData轉換成實數(shù)，入棧，并重新置空{Data=(float)atof(TempData);Push(OPND,Data);strcpy(TempData,"\0");}}else{//不是運算符則進棧switch(precede(GetTop<SqStack<char>,char>(OPTR),c)){case'<'://棧頂元素優(yōu)先權低Push(OPTR,c);c=getchar();break;case'='://脫括號并接收下一字符Pop(OPTR,x);c=getchar();break;case'>'://退棧并將運算結果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}}//whilereturnGetTop<SqStack<float>,float>(OPND)}5詳細設計5.1順序棧的建立任何一個表達式都是由操作符，運算符和界限符組成的。分別用順序棧來寄存表達式的操作數(shù)和運算符。棧是限定于緊僅在表尾進行插入或刪除操作的線性表。順序棧的存儲結構是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設指針top指示棧頂元素在順序棧中的位置，base為棧底指針，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉擞?，每當插入新的棧頂元素時，指針top增1，刪除棧頂元素時，指針top減1。typedefintStatus;template<typenameT>structSqStack{T*top;T*base;intstacksize;};順序棧結構template<typenameT1,typenameT2>StatusInitStack(T1&S){S.base=(T2*)malloc(STACK_INIT_SIZE*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnok;}初始化棧函數(shù)template<typenameT1,typenameT2>StatusPush(T1&S,T2e){if(S.top-S.base>=S.stacksize){S.base=(T2*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnok;}入棧函數(shù)template<typenameT1,typenameT2>StatusPop(T1&S,T2&e){if(S.top==S.base)returnerror;e=*--S.top;returnok;}出棧函數(shù)template<typenameT1,typenameT2>T2GetTop(T1S){if(S.top==S.base)returnerror;elsereturn*(S.top-1);}獲取棧頂元素5.2函數(shù)及對應程序(1)In(charTest,char*TestOp)判斷字符是否是運算符功能，運算符即返回ture。StatusIn(charTest,char*TestOp){boolFind=false;for(inti=0;i<OPSETSIZE;i++){if(Test==TestOp[i])Find=true;}returnFind;}//判斷是否為運算符(2)ReturnOpOrd(charop,char*TestOp)判斷運算符優(yōu)先權功能，該函數(shù)判斷運算符Aop,Bop的優(yōu)先權。判斷運算符優(yōu)先權，返回優(yōu)先權高的。intReturnOpOrd(charop,char*TestOp){inti;for(i=0;i<OPSETSIZE;i++){if(op==TestOp[i])returni;}return0;}charprecede(charAop,charBop){returnPrior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];}//ReturnOpOrd和precede組合，判斷運算符優(yōu)先級算符間的優(yōu)先關系如下表5.1：表5.1優(yōu)先級關系表+-*/()#+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=(3)Operate(floata,unsignedchartheta,floatb)操作數(shù)用對應的運算符進行運算功能。運算結果直接返回。floatOperate(floata,unsignedchartheta,floatb){switch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':{if(b!=0)returna/b; elseprintf("輸入錯誤請重輸");}//判斷分母是否為零為零則重新輸入default:return0;}}//運算(4)EvaluateExpression()主要操作函數(shù)，功能主要實現(xiàn)表達式的整體計算floatEvaluateExpression(){算術表達式求值的算符優(yōu)先算法，設OPTR和OPND分別為運算符棧和運算數(shù)棧，OPSET為運算符集合。SqStack<char>OPTR;//運算符棧，字符元素SqStack<float>OPND;//運算數(shù)棧，實數(shù)元素charTempData[20];floatData,a,b;chartheta,c,x,Dr[2];InitStack<SqStack<char>,char>(OPTR);Push(OPTR,'#');InitStack<SqStack<float>,float>(OPND);strcpy(TempData,"\0");//將TempData置為空c=getchar();while(c!='#'||GetTop<SqStack<char>,char>(OPTR)!='#'){if(!In(c,OPSET)){Dr[0]=c;Dr[1]='\0';//存放單個數(shù)strcat(TempData,Dr);//將單個數(shù)連到TempData中，形成字符串c=getchar();if(In(c,OPSET))//如果遇到運算符，則將字符串TempData轉換成實數(shù)，入棧，//并重新置空{Data=(float)atof(TempData);Push(OPND,Data);strcpy(TempData,"\0");}}else{//不是運算符則進棧switch(precede(GetTop<SqStack<char>,char>(OPTR),c)){case'<'://棧頂元素優(yōu)先權低Push(OPTR,c);c=getchar();break;case'='://脫括號并接收下一字符Pop(OPTR,x);c=getchar();break;case'>'://退棧并將運算結果入棧Pop(OPTR,theta);Po