《《大數(shù)據(jù)結(jié)構(gòu)》算術(shù)表達(dá)式求值》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》算術(shù)表達(dá)式求值（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word二 課程設(shè)計(jì)2算術(shù)表達(dá)式求值一、 需求分析二、 程序的主要功能三、 程序運(yùn)行平臺(tái)四、 數(shù)據(jù)結(jié)構(gòu)五、 算法與時(shí)間復(fù)雜度六、 測(cè)試用例七、 程序源代碼三 感想體會(huì)與總結(jié)算術(shù)表達(dá)式求值一、需求分析一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、完畢符“#，如：#7+15*23-28/4#。引入表達(dá)式起始、完畢符是為了方便。編程利用“算符優(yōu)先法求算術(shù)表達(dá)式的值。二、程序的主要功能1 從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。2 顯示輸入序列和棧的變

2、化過(guò)程。三、程序運(yùn)行平臺(tái)四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為棧。1運(yùn)算符棧局部：struct SqStack /定義棧 char *base; /棧底指針 char *top; /棧頂指針 int stacksize; /棧的長(zhǎng)度;int InitStack (SqStack &s) /建立一個(gè)空棧S if (!(s.base = (char *)malloc(50 * sizeof(char) exit(0); s.top=s.base; s.stacksize=50; return OK; char GetTop(SqStack s,char &e) /運(yùn)算符取棧頂元素 if (s.top=s.

3、base) /棧為空的時(shí)候返回ERROR printf(運(yùn)算符棧為空!n); return ERROR; else e=*(s.top-1); /棧不為空的時(shí)候用e做返回值，返回S的棧頂元素，并返回OK return OK; int Push(SqStack &s,char e) /運(yùn)算符入棧 if (s.top-s.base = s.stacksize) printf(運(yùn)算符棧滿(mǎn)!n); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /棧滿(mǎn)的時(shí)候，追加5個(gè)存儲(chǔ)空間 if(!s.base) exit (OVERFLO

4、W);s.top=s.base+s.stacksize; s.stacksize+=5;*(s.top)+=e; /把e入棧return OK; int Pop(SqStack &s,char &e) /運(yùn)算符出棧if (s.top=s.base) /棧為空棧的時(shí)候，返回ERROR printf(運(yùn)算符棧為空!n); return ERROR; elsee=*-s.top; /棧不為空的時(shí)候用e做返回值，刪除S的棧頂元素，并返回OKreturn OK; int StackTraverse(SqStack &s) /運(yùn)算符棧的遍歷 char *t;t=s.base ;if (s.top=s.ba

5、se) printf(運(yùn)算符棧為空!n); /棧為空棧的時(shí)候返回ERROR return ERROR;while(t!=s.top) printf( %c,*t); /棧不為空的時(shí)候依次取出棧內(nèi)元素 t+; return ERROR;（2） 數(shù)字棧局部： struct SqStackn /定義數(shù)棧 int *base; /棧底指針 int *top; /棧頂指針 int stacksize; /棧的長(zhǎng)度;int InitStackn (SqStackn &s) /建立一個(gè)空棧S s.base=(int*)malloc(50*sizeof(int); if(!s.base)exit(OVERFL

6、OW); /存儲(chǔ)分配失敗 s.top=s.base; s.stacksize=50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if (s.top=s.base) printf(運(yùn)算數(shù)棧為空!n); /棧為空的時(shí)候返回ERROR return ERROR; else e=*(s.top-1); /棧不為空的時(shí)候，用e作返回值，返回S的棧頂元素，并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if (s.top-s.base =s.stacksize)printf(運(yùn)算數(shù)棧滿(mǎn)!n)

7、; /棧滿(mǎn)的時(shí)候，追加5個(gè)存儲(chǔ)空間 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; /插入元素e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK; int Popn(SqStackn &s,int &e) /數(shù)棧出棧if (s.top=s.base) printf( 運(yùn)算符棧為空!n); /棧為空棧的視時(shí)候，返回ERROR return ERROR; elsee

8、=*-s.top; /棧不空的時(shí)候，如此刪除S的棧頂元素，用e返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /數(shù)棧遍歷 int *t;t=s.base ;if (s.top=s.base) printf( 運(yùn)算數(shù)棧為空!n); /棧為空棧的時(shí)候返回ERROR return ERROR;while(t!=s.top) printf( %d,*t); /棧不為空的時(shí)候依次輸出 t+; return ERROR;五、算法與時(shí)間復(fù)雜度1、算法：建立兩個(gè)不同類(lèi)型的空棧，先把一個(gè)# 壓入運(yùn)算符棧。輸入一個(gè)算術(shù)表達(dá)式的字符串以#完畢，從第一個(gè)字符依

9、次向后讀，把讀取的數(shù)字放入數(shù)字棧，運(yùn)算符放入運(yùn)算符棧。判斷新讀取的運(yùn)算符和運(yùn)算符棧頂?shù)眠\(yùn)算符號(hào)的優(yōu)先級(jí)，以便確定是運(yùn)算還是把運(yùn)算符壓入運(yùn)算符棧。最后兩個(gè)#遇到一起如此運(yùn)算完畢。數(shù)字棧頂?shù)臄?shù)字就是要求的結(jié)果。2、時(shí)間復(fù)雜度：O(n)數(shù)據(jù)壓縮存儲(chǔ)棧，其操作主要有：建立棧int Push(SeqStack *S, char x)入棧int Pop(SeqStack *S, char x)出棧。以上各操作運(yùn)算的平均時(shí)間復(fù)雜度為O(n)，其主要時(shí)間是消耗在輸入操作。六、 測(cè)試用例如下列圖。最終結(jié)果如下列圖：七、 源代碼/*第七題 算術(shù)表達(dá)式求值問(wèn)題描述一個(gè)算術(shù)表達(dá)式是由操作數(shù)(operand)、運(yùn)算符(

10、operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運(yùn)算符只含加減乘除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、完畢符“#，如：#7+15*23-28/4#。引入表達(dá)式起始、完畢符是為了方便。編程利用“算符優(yōu)先法求算術(shù)表達(dá)式的值。根本要求1 從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。2 顯示輸入序列和棧的變化過(guò)程。*/#include #include #include #include #include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 /#define STACKI

11、NCREMENT 10/=/ 以下定義兩種棧，分別存放運(yùn)算符和數(shù)字/=/*運(yùn)算符棧局部*struct SqStack /定義棧 char *base; /棧底指針 char *top; /棧頂指針 int stacksize; /棧的長(zhǎng)度;int InitStack (SqStack &s) /建立一個(gè)空棧S if (!(s.base = (char *)malloc(50 * sizeof(char) exit(0); s.top=s.base; s.stacksize=50; return OK; char GetTop(SqStack s,char &e) /運(yùn)算符取棧頂元素 if (s

12、.top=s.base) /棧為空的時(shí)候返回ERROR printf(運(yùn)算符棧為空!n); return ERROR; else e=*(s.top-1); /棧不為空的時(shí)候用e做返回值，返回S的棧頂元素，并返回OK return OK; int Push(SqStack &s,char e) /運(yùn)算符入棧 if (s.top-s.base = s.stacksize) printf(運(yùn)算符棧滿(mǎn)!n); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /棧滿(mǎn)的時(shí)候，追加5個(gè)存儲(chǔ)空間 if(!s.base) exit (

13、OVERFLOW);s.top=s.base+s.stacksize; s.stacksize+=5;*(s.top)+=e; /把e入棧return OK; int Pop(SqStack &s,char &e) /運(yùn)算符出棧if (s.top=s.base) /棧為空棧的時(shí)候，返回ERROR printf(運(yùn)算符棧為空!n); return ERROR; elsee=*-s.top; /棧不為空的時(shí)候用e做返回值，刪除S的棧頂元素，并返回OKreturn OK; int StackTraverse(SqStack &s) /運(yùn)算符棧的遍歷 char *t;t=s.base ;if (s.t

14、op=s.base) printf(運(yùn)算符棧為空!n); /棧為空棧的時(shí)候返回ERROR return ERROR;while(t!=s.top) printf( %c,*t); /棧不為空的時(shí)候依次取出棧內(nèi)元素 t+; return ERROR;/*數(shù)字棧局部* struct SqStackn /定義數(shù)棧 int *base; /棧底指針 int *top; /棧頂指針 int stacksize; /棧的長(zhǎng)度;int InitStackn (SqStackn &s) /建立一個(gè)空棧S s.base=(int*)malloc(50*sizeof(int); if(!s.base)exit(O

15、VERFLOW); /存儲(chǔ)分配失敗 s.top=s.base; s.stacksize=50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if (s.top=s.base) printf(運(yùn)算數(shù)棧為空!n); /棧為空的時(shí)候返回ERROR return ERROR; else e=*(s.top-1); /棧不為空的時(shí)候，用e作返回值，返回S的棧頂元素，并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if (s.top-s.base =s.stacksize)printf(運(yùn)算數(shù)

16、棧滿(mǎn)!n); /棧滿(mǎn)的時(shí)候，追加5個(gè)存儲(chǔ)空間 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; /插入元素e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK; int Popn(SqStackn &s,int &e) /數(shù)棧出棧if (s.top=s.base) printf( 運(yùn)算符棧為空!n); /棧為空棧的視時(shí)候，返回ERROR return ERROR;

17、elsee=*-s.top; /棧不空的時(shí)候，如此刪除S的棧頂元素，用e返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /數(shù)棧遍歷 int *t;t=s.base ;if (s.top=s.base) printf( 運(yùn)算數(shù)棧為空!n); /棧為空棧的時(shí)候返回ERROR return ERROR;while(t!=s.top) printf( %d,*t); /棧不為空的時(shí)候依次輸出 t+; return ERROR;/=/ 以下定義函數(shù)/=int Isoperator(char ch) /判斷是否為運(yùn)算符，分別將運(yùn)算符和數(shù)字進(jìn)入不同的

18、棧switch (ch)case +:case -:case *:case /:case (:case ):case #:return 1;default:return 0;int Operate(int a, char op, int b) /運(yùn)算操作int result;switch(op)case +:result=a+b;break;case -:result=a-b;break;case *:result=a*b;break;case /:result=a/b;break;return result;char Precede(char ch1, char ch2) /運(yùn)算符優(yōu)先級(jí)的比

19、擬 char p; switch(ch1) case +: case -: if (ch2=+|ch2=-|ch2=)|ch2=#) p = ; /ch1運(yùn)算符的優(yōu)先級(jí)小于ch2運(yùn)算符 else p = ; break; case *: case /: if (ch2 = () p = ; break; case (: if (ch2 = )p = =; else if (ch2 = #) printf( 表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!n) ;exit(0); elsep = ; break ; case #: if (ch2 = ) printf( 表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!n) ; exit(

20、0); else if (ch2 = #)p = =; elsep=; break; return p; /=/ 以下是求值過(guò)程/= int a, b, temp, answer; char ch,op,e; char *str; int j = 0; SqStackn OPND; /OPND為運(yùn)算數(shù)字棧 SqStack OPTR; /OPTR為運(yùn)算符棧 InitStack(OPTR); Push(OPTR,#); /,所以此棧底是#，因?yàn)檫\(yùn)算符棧以#作為完畢標(biāo)志 InitStackn(OPND); / printf(nn按任意鍵開(kāi)始求解:nn); / ch=getch(); printf(n

21、請(qǐng)輸入表達(dá)式并以#完畢:n); str =(char*)malloc(50*sizeof(char); gets(str); ch=strj; /ch是字符型的，而e是整型的整數(shù) j+; GetTop(OPTR,e); /e為棧頂元素返回值 while (ch!=# | e!=#) if (!Isoperator(ch) /遇到數(shù)字,轉(zhuǎn)換成十進(jìn)制并計(jì)算 temp=ch-0; /將字符轉(zhuǎn)換為十進(jìn)制數(shù) ch=strj; j+; while(!Isoperator(ch) temp=temp*10 + ch-0; /將逐個(gè)讀入運(yùn)算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù) ch=strj; j+; Pushn(OPND

22、,temp); else if (Isoperator(ch) /判斷是否是運(yùn)算符,不是運(yùn)算符如此進(jìn)棧 switch (Precede(e,ch) case : Pop(OPTR,op); /彈出最上面兩個(gè)，并運(yùn)算，把結(jié)果進(jìn)棧 Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf(nn 運(yùn)算符棧為：n);StackTraverse(OPTR);printf(n 數(shù)棧為：n);StackTraversen(OPND); else printf(您的輸入有問(wèn)題，請(qǐng)檢查重新輸入!); exit(0); GetTop(OPTR,e);

23、/取出運(yùn)算符棧最上面元素是否是# /while GetTopn(OPND,answer); /已輸出。數(shù)字棧最上面即是最終結(jié)果 return answer;/=/ 執(zhí)行局部/=void ShowMenu()printf(nn);printf(n);printf(n);printf( 表達(dá)式求值系統(tǒng) n);printf(n);printf(n);void Quit();void Manage()int answer;/ShowMenu();answer=EvaluateExpression();printf(nn表達(dá)式結(jié)果是: %dn,answer);Quit();void Quit()char

24、 ch; printf( 本次運(yùn)算完畢。n); printf( 繼續(xù)本系統(tǒng)嗎？nn);printf( 繼續(xù)運(yùn)算請(qǐng)按Y/y );printf(n 退出程序請(qǐng)按N/n );printf( n_n);ch=getch();ch=toupper(ch); /將ch字符轉(zhuǎn)換成大寫(xiě)字母if(ch = N)printf(nn 系統(tǒng)退出。n);exit(0);Manage();int main()ShowMenu(); Manage();return 0;感想體會(huì)與總結(jié)好的算法編程技巧高效率好的程序。1、 做什么都需要耐心，做設(shè)計(jì)寫(xiě)程序更需要耐心。一開(kāi)始的時(shí)候，我寫(xiě)函數(shù)寫(xiě)的很快，可是等最后調(diào)試的時(shí)候發(fā)現(xiàn)錯(cuò)誤很

25、隱蔽，就很費(fèi)時(shí)間了。后來(lái)我先在紙上構(gòu)思出函數(shù)的功能和參數(shù)，考慮好接口之后才動(dòng)手編，這樣就比擬容易成功了。2、 做任何事情我決定都應(yīng)該有個(gè)總體規(guī)劃。之后的工作按照規(guī)劃逐步展開(kāi)完成。對(duì)于一個(gè)完整的程序設(shè)計(jì)，首先需要總體規(guī)劃寫(xiě)程序的步驟，分塊寫(xiě)分函數(shù)寫(xiě)，然后寫(xiě)完一局部馬上糾錯(cuò)調(diào)試。而不是像我第一個(gè)程序，一口氣寫(xiě)完，然后再花幾倍的時(shí)間調(diào)試。一步步來(lái)，走好一步再走下一步。寫(xiě)程序是這樣，做項(xiàng)目是這樣，過(guò)我們的生活更是應(yīng)該這樣。3、 感覺(jué)一開(kāi)始設(shè)計(jì)結(jié)構(gòu)寫(xiě)函數(shù)表現(xiàn)的是數(shù)據(jù)結(jié)構(gòu)的思想，后面的調(diào)試如此更加表現(xiàn)了人的綜合素質(zhì)，專(zhuān)業(yè)知識(shí)、堅(jiān)決耐心、鍥而不舍，真的缺一不可啊。4、 通過(guò)這次課設(shè)，不僅僅復(fù)習(xí)了C語(yǔ)言相關(guān)知識(shí)、鞏固了數(shù)據(jù)結(jié)構(gòu)關(guān)于棧和排序的算法等知識(shí)，更磨練了我的意志。- 17 - / 17