《大數(shù)據(jù)結(jié)構(gòu)》算術(shù)表達(dá)式求值

《《大數(shù)據(jù)結(jié)構(gòu)》算術(shù)表達(dá)式求值》由會(huì)員分享，可在線閱讀，更多相關(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á)式的值。 二、程序的主要功能

2、 〔1〕 從鍵盤(pán)讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。 〔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(

3、char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //運(yùn)算符取棧頂元素 { if (s.top==s.base) //棧為空的時(shí)候返回ERROR { printf("運(yùn)算符棧為空!\n"); return ERROR; } else e=*(s.top-1); //棧不為空的時(shí)候用e做返回值，返回S的棧頂元素，并返回OK

4、 return OK; } int Push(SqStack &s,char e) //運(yùn)算符入棧 { if (s.top-s.base >= s.stacksize) { printf("運(yùn)算符棧滿!\n"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間 if(!s.base) exit (OVERFLOW); s.top=s.

5、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; } else { e=*--s.top; //棧不為空的時(shí)候用e做返回值，刪除S的棧頂元素，并返回OK return OK; } } i

6、nt StackTraverse(SqStack &s) //運(yùn)算符棧的遍歷 { char *t; t=s.base ; if (s.top==s.base) { 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 *

7、base; //棧底指針 int *top; //棧頂指針 int stacksize; //棧的長(zhǎng)度 }; int InitStackn (SqStackn &s) //建立一個(gè)空棧S { s.base=(int*)malloc(50*sizeof(int)); if(!s.base)exit(OVERFLOW); //存儲(chǔ)分配失敗 s.top=s.base; s.stacksize=50; return OK; } int GetTopn(SqStackn s,int &

8、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ù)棧滿!\n"); //棧滿的時(shí)

9、候，追加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.

10、base) { printf(" 運(yùn)算符棧為空!\n"); //棧為空棧的視時(shí)候，返回ERROR return ERROR; } else { e=*--s.top; //棧不空的時(shí)候，如此刪除S的棧頂元素，用e返回其值，并返回OK return OK; } } int StackTraversen(SqStackn &s) //數(shù)棧遍歷 { int *t; t=s.base ; if (s.top==s.base) { printf(" 運(yùn)算數(shù)棧為空!\n"); //棧為空棧的時(shí)候返回ERROR return ER

11、ROR; } while(t!=s.top) { printf(" %d",*t); //棧不為空的時(shí)候依次輸出 t++; } return ERROR; } 五、算法與時(shí)間復(fù)雜度 1、算法： 建立兩個(gè)不同類型的空棧，先把一個(gè)‘# ’壓入運(yùn)算符棧。輸入一個(gè)算術(shù)表達(dá)式的字符串〔以‘#’完畢〕，從第一個(gè)字符依次向后讀，把讀取的數(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)

12、數(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á)式是由操

13、作數(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〕 顯示輸入序列和棧的變化過(guò)程。 ************************************************************************************

14、***************/ #include #include #include #include #include #include #define OK 1 #define ERROR 0 #define STACK_INIT_SIZE 100 //#define STACKINCREMENT 10 //======================================================== //

15、 以下定義兩種棧，分別存放運(yùn)算符和數(shù)字 //======================================================== //*******************運(yùn)算符棧局部************************* struct SqStack //定義棧 { char *base; //棧底指針 char *top; //棧頂指針 int stacksize; //棧的長(zhǎng)度 }; int InitStack (SqStack &s) //建立一個(gè)空棧S {

16、 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.base) //棧為空的時(shí)候返回ERROR { printf("運(yùn)算符棧為空!\n"); return ERROR; } else e=*(

17、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)算符棧滿!\n"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //棧滿的時(shí)候，追加5個(gè)存儲(chǔ)空間

18、 if(!s.base) exit (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; } else { e=*--s.top; //棧不為空的時(shí)候用

19、e做返回值，刪除S的棧頂元素，并返回OK return OK; } } int StackTraverse(SqStack &s) //運(yùn)算符棧的遍歷 { char *t; t=s.base ; if (s.top==s.base) { printf("運(yùn)算符棧為空!\n"); //棧為空棧的時(shí)候返回ERROR return ERROR; } while(t!=s.top) { printf(" %c",*t); //棧不為空的時(shí)候依次取出棧內(nèi)元素 t++; } return ERROR; } //

20、**********************數(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(OVERFLOW); //存儲(chǔ)分配失敗

21、 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(

22、SqStackn &s,int e) //數(shù)棧入棧 { if (s.top-s.base >=s.stacksize) { printf("運(yùn)算數(shù)棧滿!\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; } *

23、(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; } else { e=*--s.top; //棧不空的時(shí)候，如此刪除S的棧頂元素，用e返回其值，并返回OK return OK; } } int StackTraversen(SqStackn &s) //數(shù)棧遍歷 { i

24、nt *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ù) //========

25、================================================ int Isoperator(char ch) //判斷是否為運(yùn)算符，分別將運(yùn)算符和數(shù)字進(jìn)入不同的棧 { 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;

26、 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í)的比擬 { char p; switch(ch1) { case '+': case '-': if (ch2=='+'|

27、|ch2=='-'||ch2==')'||ch2=='#') p = '>'; //ch1運(yùn)算符的優(yōu)先級(jí)小于ch2運(yùn)算符 else p = '<'; break; case '*': case '/': if (ch2 == '(') p = '<'; else p = '>'; break; case '(': if (ch2 == '

28、)') p = '='; else if (ch2 == '#') { printf(" 表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n") ; exit(0); } else p = '<'; break ; case ')': if (ch2 == '(') { printf(" 表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n") ; exit(0); } else p = '>'; break ; case '#': if (ch2 == ')') { printf("

29、表達(dá)式錯(cuò)誤!運(yùn)算符不匹配!\n") ; exit(0); } else if (ch2 == '#') p = '='; else p='<'; break; } return p; } //======================================================== // 以下是求值過(guò)程 //======================================================== { int a,

30、 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("\n\n按任意鍵開(kāi)始求解:\n\n"); // ch=getch();

31、 printf("\n請(qǐng)輸入表達(dá)式并以'#'完畢:\n"); str =(char*)malloc(50*sizeof(char)); gets(str); ch=str[j]; //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=str[j];

32、 j++; while(!Isoperator(ch)) { temp=temp*10 + ch-'0'; //將逐個(gè)讀入運(yùn)算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù) ch=str[j]; j++; } Pushn(OPND,temp); } else if (Isoperator(ch)) //判斷是否是運(yùn)算符,不是運(yùn)算符如此進(jìn)棧 switch (Precede(e,ch)) { case '<' : Push(OPTR,ch); // 棧頂元素優(yōu)先權(quán)低 ch = str[j+

33、+]; printf("\n\n 運(yùn)算符棧為：\n"); //輸出棧，顯示棧的變化 StackTraverse(OPTR); printf("\n 運(yùn)算數(shù)棧為：\n"); StackTraversen(OPND); break; case '=' : Pop(OPTR,op); // 脫括號(hào)并接收下一字符 ch = str[j++] ; printf("\n\n 運(yùn)算符棧為：\n"); StackTraverse(OPTR); printf("\n 數(shù)棧為：\n"); StackTraversen(OPND); break; case '>'

34、: Pop(OPTR,op); //彈出最上面兩個(gè)，并運(yùn)算，把結(jié)果進(jìn)棧 Popn(OPND,b); Popn(OPND,a); Pushn(OPND,Operate(a,op,b)); printf("\n\n 運(yùn)算符棧為：\n"); StackTraverse(OPTR); printf("\n 數(shù)棧為：\n"); StackTraversen(OPND); } else { printf("您的輸入有問(wèn)題，請(qǐng)檢查重新輸入!"); exit(0); } GetT

35、op(OPTR,e); //取出運(yùn)算符棧最上面元素是否是'#' } //while GetTopn(OPND,answer); //已輸出。數(shù)字棧最上面即是最終結(jié)果 return answer; } //======================================================== // 執(zhí)行局部 //======================================================== void ShowMenu()

36、 { printf("\n\n"); printf("███████████████████████████████████████\n"); printf("████\n"); printf("██ 表達(dá)式求值系統(tǒng) ██\n"); printf("████\n"); printf("███████████████████████████████████████\n"); } void Quit(); void Manage() { int answer; //

37、ShowMenu(); answer=EvaluateExpression(); printf("\n\n表達(dá)式結(jié)果是: %d\n",answer); Quit(); } void Quit() { char ch; printf(" 本次運(yùn)算完畢。\n"); printf(" 繼續(xù)本系統(tǒng)嗎？\n\n"); printf(" 繼續(xù)運(yùn)算請(qǐng)按Y/y "); printf("\n 退出程序請(qǐng)按N/n "); printf(" \n___________________________________________________________

38、________\n"); ch=getch(); ch=toupper(ch); //將ch字符轉(zhuǎn)換成大寫(xiě)字母 if(ch == 'N') { printf("\n\n 系統(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ò)誤很隱蔽，就很費(fèi)時(shí)間了。后來(lái)我先在紙上

39、構(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ì)，專業(yè)知識(shí)、堅(jiān)決耐心、鍥而不舍，真的缺一不可啊。 4、 通過(guò)這次課設(shè)，不僅僅復(fù)習(xí)了C語(yǔ)言相關(guān)知識(shí)、鞏固了數(shù)據(jù)結(jié)構(gòu)關(guān)于棧和排序的算法等知識(shí)，更磨練了我的意志。 - 17 - / 17