算術(shù)表達(dá)式求值問題z數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20212021學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱算術(shù)表達(dá)式求值問題學(xué)生姓名版也學(xué)號01專業(yè)班級08計(jì)科(2)指導(dǎo)教師王昆侖張貫虹20212021 年 6 6 月題目：(算術(shù)表達(dá)式求值問題)一個算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的.假設(shè)操作數(shù)是正整數(shù),運(yùn)算符只含加減乘除四種運(yùn)算符,界限符有左右括號和表達(dá)式起始、結(jié)束符#,如：#(7+15)*(23-28/4)#.引入表達(dá)式起始、結(jié)束符是為了方便.編程利用“算符優(yōu)先法求算術(shù)表達(dá)式的值.要求：(1)從鍵盤讀入一個合法的算術(shù)表達(dá)式,輸出正確

2、的結(jié)果.(2)顯示輸入序列和棧的變化過程.選作內(nèi)容：操作數(shù)類型擴(kuò)充到實(shí)數(shù).一、問題分析和任務(wù)定義要對一個含有加減乘除四那么運(yùn)算的合法的算術(shù)表達(dá)式進(jìn)行求值,首先,應(yīng)了解算術(shù)表達(dá)式的四那么運(yùn)算的規(guī)那么：(1)從左向右計(jì)算(2)先乘除,后加減(3)先括號內(nèi),后括號外由此可知,比方算術(shù)表達(dá)式(7+15)*(23-28/4)的計(jì)算順序,即為(7+15)*(23-28/4)=22*(23-28/4)=22*(23-7)=22*16=352其次,應(yīng)明確“算符優(yōu)先法的內(nèi)容：算符優(yōu)先法就是根據(jù)上述四那么運(yùn)算規(guī)那么確定的優(yōu)先關(guān)系來實(shí)現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行的.一個簡單的四那么運(yùn)算表達(dá)式由操作數(shù)(operand)

3、、運(yùn)算符(operator)和界限符(delimiter)組成,其中操作數(shù)是正整數(shù),運(yùn)算符只含加、減、乘、除四種,界限符有左右括號和表達(dá)式起始、結(jié)束符#；而且,為了統(tǒng)一算法的描述,將運(yùn)算符和界限符通稱為算符.算符集OP=+,-,*,/,(,),#.根據(jù)上述3條運(yùn)算規(guī)那么,在具體的運(yùn)算的每一步中,任意兩個相繼出現(xiàn)的算符.1和.2之間的優(yōu)先關(guān)系只能是如下3中關(guān)系之一：010201的優(yōu)先級高于02下表定義了算符之間的這種優(yōu)先關(guān)系.表 1 算符之間的優(yōu)先關(guān)系!T1Q2+-*/()#+-*/(#,=;由于算術(shù)表達(dá)式涉及到兩個數(shù)的四那么運(yùn)算,所以要設(shè)計(jì)一個兩個數(shù)四那么運(yùn)算的函數(shù),即函數(shù)doubleOper

4、ate(doublea,chartheta,doubleb),定義了兩個數(shù)的(加)+、(減)-、(乘)*、(除)/四種運(yùn)算,并返回兩個數(shù)的運(yùn)算結(jié)果.然后,當(dāng)依次讀入算術(shù)表達(dá)式的各個字符時(shí),要同時(shí)判斷字符的合法性,包括算符的合法性和操作數(shù)的合法性,所以應(yīng)設(shè)計(jì)算符合法性的判斷函數(shù),即intIn(charTest,char*TestOp),將依次讀入的字符與算符數(shù)組中的所有算符依次比擬,假設(shè)算符合法,那么返回該算符在算符數(shù)組中的位置m,假設(shè)算符不合法,那么均返回0.在判斷算符的合法性之后,那么應(yīng)該對相鄰的兩個算符的優(yōu)先級進(jìn)行比擬,以便于算術(shù)表達(dá)式的相關(guān)運(yùn)算,所以應(yīng)設(shè)計(jì)函數(shù)charPrecede(ch

5、arAop,charBop)比擬兩個算符Aop和Bop的優(yōu)先級,返回值即為兩個算符對應(yīng)在算符優(yōu)先級二維數(shù)組Prior77中的值.經(jīng)過上述兩個步驟,確定了的算符的合法性與否以及兩個算符的優(yōu)先級,然后即要判斷算術(shù)表達(dá)式的合法性與否,并同時(shí)對該算術(shù)表達(dá)式進(jìn)行一系列的計(jì)算,設(shè)計(jì)函數(shù)doubleEvaluateExpression(char*MyExpression).該函數(shù)需要的所有變量為：OPTR,為算符棧；OPND,為操作數(shù)棧；TempData40,為輔助字符數(shù)組,其中所有的字符均為滿足合法性的算術(shù)表達(dá)式的操作數(shù)；theta,為算符；a,b,為運(yùn)算的兩個操作數(shù)；Data,為兩個數(shù)的運(yùn)算結(jié)果；c,為

6、當(dāng)前讀入的字符；Dr2,為當(dāng)前讀入的字符和結(jié)束符0構(gòu)成的字符串；其中變量TempData40和Dr2是由于考慮到操作數(shù)有可能不止一位數(shù),那么Dr2起到字符銜接的作用,只要讀入的字符是操作數(shù),就將該字符銜接到字符數(shù)組TempData40中,那么TempData40中除了結(jié)束符0之外的所有字符就是算術(shù)表達(dá)式中的一個完整的操作數(shù),即TempData40中存放的操作數(shù)或者是一位數(shù),或者是多位數(shù).算術(shù)表達(dá)式的詳細(xì)計(jì)算過程：首先,將所需的變量初始化：初始化算符棧和操作數(shù)棧,OPTR_InitStack(OPTR),OPND_InitStack(OPND);將算術(shù)表達(dá)式的起始字符#,入算符棧； 變量c保存當(dāng)

7、前表達(dá)式MyExpression的地址；禾U用strcpy()函數(shù)將結(jié)束符0銜接至數(shù)組TempData40中.然后,利用while循環(huán),開始計(jì)算.當(dāng)OPTR棧的棧頂元素OPTR_GetTop(OPTR)和當(dāng)前讀入的字符*c同時(shí)為#時(shí),整個表達(dá)式求值完畢；假設(shè)不滿足表達(dá)式結(jié)束的該條件,那么進(jìn)行計(jì)算.讀入當(dāng)前字符*c：假設(shè)*c是操作數(shù),那么首先將*c給Dr2,利用strcat()函數(shù)將Dr2銜接至TempData40中,然后c+,判斷下一個字符*c是否是算符,假設(shè)不是,說明當(dāng)前操作數(shù)是多位數(shù),然后再將該操作數(shù)字符銜接至TempData40中,然后再c+,重復(fù)上述過程,將當(dāng)前操作數(shù)的所有字符完整的保

8、存至TempData40中,利用強(qiáng)制轉(zhuǎn)換函數(shù)atof()將TempData40中的字符轉(zhuǎn)換為double型的數(shù)據(jù),同時(shí)賦給Data,那么Data即為當(dāng)前的完整的double型操作數(shù)(Data或?yàn)橐晃粩?shù),或?yàn)槎辔粩?shù)),然后Data入操作數(shù)棧,即OPND_Push(OPND,Data)；假設(shè)*c是算符,那么將*c與當(dāng)前算符棧的棧頂元素進(jìn)行優(yōu)先級的比較,即Precede(OPTR_GetTop(OPTR),*c);比擬的結(jié)果假設(shè)為,說明當(dāng)前算符棧的棧頂算符的優(yōu)先級高于比當(dāng)前讀入的字符*c的優(yōu)先級,那么首先將當(dāng)前算符棧的棧頂算符出棧,即OPTR_Pop(OPTR,theta)；然后,將當(dāng)前操作數(shù)棧的棧

9、頂操作數(shù)和次棧頂操作數(shù)依次出棧,即OPND_Pop(OPND,b),OPND_Pop(OPND,a),將該兩個操作數(shù)a和b進(jìn)行theta運(yùn)算,將運(yùn)算結(jié)果入操作數(shù)棧,即OPND_Push(OPND,Operate(a,theta,b)；while循環(huán)重復(fù)上述兩個過程,直至當(dāng)前算符棧的棧頂元素OPTR_GetTop(OPTR)和當(dāng)前讀入的字符*c同時(shí)為#時(shí),整個算術(shù)表達(dá)式的計(jì)算全過程結(jié)束.四、上機(jī)調(diào)試1、語法問題及解決由于本程序牽扯到四個方面的內(nèi)容,首先是OPTR棧的相關(guān)功能函數(shù)的設(shè)計(jì)；其次是OPND棧的相關(guān)功能函數(shù)的設(shè)計(jì)；再次是算術(shù)表達(dá)式的具體計(jì)算涉及到的相關(guān)功能函數(shù)的設(shè)計(jì),最后是主函數(shù)的設(shè)計(jì)；

10、前兩個方面均為對順序棧的根本操作,具有通用性,根本無語法錯誤；主要是在設(shè)計(jì)算術(shù)表達(dá)式的具體計(jì)算的函數(shù)時(shí),調(diào)用相關(guān)棧的函數(shù)以及其它語句時(shí),出現(xiàn)了語法編輯的錯誤,還有在設(shè)計(jì)主函數(shù)的時(shí)候,由于要考慮到用戶的使用方便,也出現(xiàn)了一些編輯語法錯誤,在反復(fù)使用加注釋和單步運(yùn)行兩種方法對于具體錯誤分析、調(diào)試后,所有語法錯誤均得到解決.2、邏輯問題及解決在編輯本程序時(shí),一個最關(guān)鍵的方面就是在設(shè)計(jì)本程序的中央算法即算術(shù)表達(dá)式的具體計(jì)算函數(shù)EvaluateExpressionchar*MyExpression時(shí),出現(xiàn)多處邏輯錯誤；其中最關(guān)鍵的兩個問題就是,如何解決操作數(shù)是實(shí)數(shù)范圍內(nèi)的多位數(shù)處理問題,和讀入的非法字符

11、包括非法算符和非法操作數(shù)的處理問題；經(jīng)反復(fù)思考和屢次查閱資料,解決方法：一方面,利用在程序的詳細(xì)設(shè)計(jì)過程中提到的TempData40和Dr2,將依次讀入的字符滿足操作數(shù)的條件時(shí),就利用Dr2將該字符銜接至TempData40中,這樣直到讀入的字符是算符時(shí),TempData40中存放的所有字符組成的字符串就是一個完整的操作數(shù)或是實(shí)數(shù)范圍內(nèi)的一位數(shù),或是實(shí)數(shù)范圍內(nèi)的多位數(shù)；或是實(shí)數(shù)范圍內(nèi)的整數(shù),或是實(shí)數(shù)范圍內(nèi)的浮點(diǎn)數(shù),這樣就解決了操作數(shù)是實(shí)數(shù)范圍內(nèi)的多位數(shù)處理問題；另一方面,利用強(qiáng)制轉(zhuǎn)換函數(shù)atof,將TempData40中所有字符構(gòu)成的字符串強(qiáng)制轉(zhuǎn)換為double型浮點(diǎn)數(shù)據(jù),就將讀入字符過程中出

12、現(xiàn)的非法字符非法算符和非法操作數(shù)全部轉(zhuǎn)換為實(shí)數(shù)0.000,它們就不會影響到合法的數(shù)據(jù),更不會影響到后繼讀入的字符的處理,這樣就解決了讀入的非法字符的處理問題.3、時(shí)間、空間復(fù)雜度的分析由于本程序的算法只涉及到2個循環(huán)語句,分別為：forinti=0;iOPSETSIZE;i+,此循環(huán)語句是用于判斷當(dāng)前讀入字符是否是算符的功能,OPSETSIZE=7,它的時(shí)間復(fù)雜度是OOPSETSIZ；while*c!=#|OPTR_GetTopOPTR!=#,此循環(huán)語句是用于算術(shù)表達(dá)式的具體計(jì)算,它的時(shí)間復(fù)雜度取決于用戶輸入的算術(shù)表達(dá)式MyExpression的長度length,length=strlenMy

13、Expression,即該語句的時(shí)間復(fù)雜度為Olength=OstrlenMyExpression；所以,本程序的算法的時(shí)間復(fù)雜度為OOPSETSIZE+strlenMyExpression.由于在本程序中,在為算符棧OPTR和操作數(shù)棧OPND涉及到兩種情況時(shí)申請空間,一方面分別為OPTR棧和OPND棧申請了初始的存儲單元,均為STACK_INITSIZE=100個；另一方面,考慮到兩個棧在處理具體的算術(shù)表達(dá)式時(shí),有可能會出現(xiàn)溢出的情況,即棧的初始的存儲空間不夠用,這時(shí)需要為其申請額外的存儲空間,每溢出一次,就為其申請存儲單元STACKINCREMENT=10個；所以,本程序的算法的空間復(fù)雜度

14、一方面取決于算術(shù)表達(dá)式的長度,另一方面取決于本程序的所有代碼所占用的存儲空間大小.五、測試結(jié)果及其分析調(diào)試菜單：第一組測試數(shù)據(jù)：2.34+11.456=13.796該算術(shù)表達(dá)式為單純的加法運(yùn)算,參與運(yùn)算的兩個數(shù)據(jù)均為實(shí)數(shù),算術(shù)表達(dá)式的結(jié)果為13.796,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確；第二組測試數(shù)據(jù)：999.567-10.43=989.137該算術(shù)表達(dá)式為單純的減法運(yùn)算,參與運(yùn)算的兩個數(shù)據(jù)均為實(shí)數(shù),算術(shù)表達(dá)式的結(jié)果為989.137,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確；

15、第三組測試數(shù)據(jù)：23.24*34.5=801.780該算術(shù)表達(dá)式為單純的乘法運(yùn)算,參與運(yùn)算的兩個數(shù)據(jù)均為實(shí)數(shù),算術(shù)表達(dá)式的結(jié)果為801.780,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確；第四組測試數(shù)據(jù)：1000.46/10.2=98.084該算術(shù)表達(dá)式為單純的除法運(yùn)算,參與運(yùn)算的兩個數(shù)據(jù)均為實(shí)數(shù),算術(shù)表達(dá)式的結(jié)果為98.084,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確；第五組測試數(shù)據(jù)：1.21+12.3/3-4*2=-1.410該算術(shù)表達(dá)式為加減乘除的復(fù)合運(yùn)算,參與運(yùn)算的所有數(shù)據(jù)均在

16、實(shí)數(shù)范圍內(nèi),算術(shù)表達(dá)式的結(jié)果為1.410,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確；第六組測試數(shù)據(jù)：7+15*23-28/4=352該算術(shù)表達(dá)式為加減乘除的復(fù)合運(yùn)算,參與運(yùn)算的所有數(shù)據(jù)均在實(shí)數(shù)范圍內(nèi),并且均是正整數(shù),算術(shù)表達(dá)式的結(jié)果為352.000,正確；而且算術(shù)表達(dá)式的具體計(jì)算過程即算符棧OPTR和操作數(shù)棧OPND的入棧和出棧的遍歷過程均正確.六、用戶使用說明1、本課程設(shè)計(jì)源代碼重要語句均有相應(yīng)的注釋,用戶可根據(jù)注釋加以使用、閱讀和理解；2、本課程設(shè)計(jì)源程序適用于實(shí)數(shù)范圍內(nèi)double浮點(diǎn)型數(shù)據(jù)的四那么運(yùn)算,非常方便用戶使用；3、本課程

17、設(shè)計(jì)考慮到了多種特殊情況的處理和意外錯誤的處理；同時(shí)在調(diào)試菜單過程中也進(jìn)行了特殊處理,可便于用戶參考,詳細(xì)情況見“詳細(xì)設(shè)計(jì)和編碼.七、參考文獻(xiàn)1王昆侖,李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：中國鐵道出版社,2006年5月.2嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版.北京：清華大學(xué)出版社,2007年5月.八、附錄#include#include#include#defineSTACK_INITSIZE100/存儲空間初始分配量#defineSTACKINCREMENT10/存儲空間分配量#defineOPSETSIZE7/算符的長度/*算符棧的結(jié)構(gòu)體*/typedefstructchar*base;/算符棧的棧底

18、char*top;/算符棧的棧頂intstacksize;/算符棧的最大長度OPTR_STACK;/*操作數(shù)棧的結(jié)構(gòu)體*/typedefstructdouble*base;/操作數(shù)棧的棧底double*top;/操作數(shù)棧的棧頂intstacksize;/操作數(shù)棧的最大長度OPND_STACK;intOPTR_InitStack(OPTR_STACK&s)s.base=(char*)malloc(STACK_INITSIZE*sizeof(char);/if(!s.base)return0;s.top=s.base;s.stacksize=STACK_INITSIZE;return1;c

19、harOPTR_GetTop(OPTR_STACK&s)chare;if(s.top=s.base)return0;e=*(s.top-1);returne;intOPTR_Push(OPTR_STACK&s,chare)if(s.top-s.base=s.stacksize)/當(dāng)棧的長度超過規(guī)定的最大長度s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char);if(!s.base)return0;/假設(shè)申請空間失敗,那么返回0s.top=s.base+s.stacksize;/申請額外空間之

20、前的棧頂位置s.top為s.base+s.stacksizes.stacksize+=STACKINCREMENT;/申請額外空間之后的棧的長度增加了STACKINCREMENT*s.top+=e;/假設(shè)棧的長度未超過規(guī)定的最大長度s.stacksize,將元素e入棧頂return1;intOPTR_Pop(OPTR_STACK&s,char&e)/算符棧頂元素出棧函數(shù)if(s.top=s.base)return0;/假設(shè)為空棧,返回0e=*-s.top;/不為空棧,將棧頂元素出棧return1;intOPND_InitStack(OPND_STACK&s)/操作數(shù)棧的

21、初始化函數(shù)s.base=(double*)malloc(STACK_INITSIZE*sizeof(double);/操作數(shù)棧分配初始的存儲空間if(!s.base)return0;s.top=s.base;s.stacksize=STACK_INITSIZE;return1;doubleOPND_GetTop(OPND_STACK&s)doublee;if(s.top=s.base)return0;e=*(s.top-1);returne;/算符棧的初s.stacksize時(shí),需要申請額外的存儲空間算符棧分配初始的存儲空間/假設(shè)申請存儲空間失敗,返回0/棧頂?shù)扔跅５?為空棧/算符棧的

22、最大長度為100/取算符棧頂元素函數(shù)/算符棧為空,返回0/返回算符棧頂元素*(s.top-1)/算符棧插入元素函數(shù)/假設(shè)申請存儲空間失敗,返回0/棧頂?shù)扔跅５?為空棧/操作數(shù)棧的最大長度為100/取操作數(shù)棧頂元素函數(shù)/操作數(shù)棧為空,返回0/返回操作數(shù)棧頂元素*(s.top-1)intOPND_Push(OPND_STACK&s,doublee)/操作數(shù)棧插入元素函數(shù)if(s.top-s.base=s.stacksize)/當(dāng)棧的長度超過規(guī)定的最大長度s.stacksize時(shí),需要申請額外的存儲空間s.base=(double*)realloc(s.base,(s.stacksize+S

23、TACKINCREMENT)*sizeof(double);if(!s.base)return0;/假設(shè)申請空間失敗,那么返回0s.top=s.base+s.stacksize;/申請額外空間之前的棧頂位置s.top為s.base+s.stacksizes.stacksize+=STACKINCREMENT;/申請額外空間之后的棧的長度增加了STACKINCREMENT*s.top+=e;/假設(shè)棧的長度未超過規(guī)定的最大長度s.stacksize,將元素e入棧頂return1;intOPND_Pop(OPND_STACK&s,double&e)if(s.top=s.base)re

24、turn0;e=*-s.top;return1;/charOPSETOPSETSIZE=+,-,*,/,(,),#;charPrior77,doubleOperate(doublea,chartheta,switch(theta)case+:returna+b;case-:returna-b;case*:returna*b;case/:returna/b;default:return0;intIn(charTest,char*TestOp)intm=0;for(inti=0;i,=,doubleb)/兩個數(shù)之間的四那么運(yùn)/算符的/7種if(Test=TestOpi)m=1;returnm;in

25、tReturnOpOrd(charop,char*TestOp)inti;for(i=0;iOPSETSIZE;i+)if(op=TestOpi)returni;return0;charPrecede(charAop,charBop)returnPriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET);doubleEvaluateExpression(char*MyExpression)/*表達(dá)式的正確性判斷函數(shù),同時(shí)計(jì)算表達(dá)式*/OPTR_STACKOPTR;OPND_STACKOPND;charTempData40;doubleData,a,b;c

26、hartheta,*c,x,Dr2;/theta是算符,*c和x均為字符串的當(dāng)前字符,Dr2保存當(dāng)前字符和結(jié)束符/初始化算符棧/#入算符棧,作為表達(dá)式的第一個字符n);/初始化操作數(shù)棧/當(dāng)前c保存字符串MyExpression的首地址strcpy(TempData,0);while(*c!=#|OPTR_GetTop(OPTR)!=#)/當(dāng)字符串的首字符和尾字符同時(shí)為#時(shí),運(yùn)算結(jié)束if(In(*c,OPSET)=0)/假設(shè)當(dāng)前字符是操作數(shù)Dr0=*c;/Dr0保存當(dāng)前字符Dr1=0;/Dr1保存字符串的結(jié)束符0strcat(TempData,Dr);/將當(dāng)前字符*c和結(jié)束符0連接到字符串TempData中c+;if(In(*c,OPSET)=1)/考慮到操作數(shù)有可能不止一位數(shù)Data=(double)atof(TempData);/atof函數(shù)是將當(dāng)前字符串轉(zhuǎn)換成浮點(diǎn)型數(shù)據(jù)OPND_Push(OPND,Data);strcpy(TempData,0);printf(%.3f入棧n,Data);else/假設(shè)當(dāng)前字符是算符switch(Precede(OPTR_GetTop(OPTR),*c)/獲取當(dāng)前算符棧的棧頂字符,與*c比擬優(yōu)先級,進(jìn)行運(yùn)算case:/假設(shè)當(dāng)前棧頂算符優(yōu)先級大于*c,那么進(jìn)行運(yùn)算OPTR_Pop(OPTR,thet