




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、word二 課程設(shè)計2算術(shù)表達式求值1、 需求分析2、 程序的主要功能3、 程序運行平臺4、 數(shù)據(jù)結(jié)構(gòu)5、 算法及時間復(fù)雜度6、 測試用例7、 程序源代碼三 感想體會與總結(jié)算術(shù)表達式求值一、需求分析一個算術(shù)表達式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù),運算符只含加減乘除等四種運算符,界限符有左右括號和表達式起始、結(jié)束符“#,如:#7+15*23-28/4#。引入表達式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法求算術(shù)表達式的值。二、程序的主要功能1 從鍵盤讀入一個合法的算術(shù)表達式,輸出正確的結(jié)果。2 顯示輸入序列和棧的變
2、化過程。三、程序運行平臺Visual C+ 版本四、數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為棧。1運算符棧局部:struct SqStack /定義棧 char *base; /棧底指針 char *top; /棧頂指針 int stacksize; /棧的長度;int InitStack (SqStack &s) /建立一個空棧S if (! = (char *)malloc(50 * sizeof(char) exit(0); =; =50; return OK; char GetTop(SqStack s,char &e) /運算符取棧頂元素 if = /棧為空的時候返回ERROR p
3、rintf("運算符棧為空!n"); return ERROR; else e=*; /棧不為空的時候用e做返回值,返回S的棧頂元素,并返回OK return OK; int Push(SqStack &s,char e) /運算符入棧 if >= printf("運算符棧滿!n"); =(char*)realloc ,+5)*sizeof(char) ); /棧滿的時候,追加5個存儲空間 if(! exit (OVERFLOW); =+; +=5;*+=e; /把e入棧return OK; int Pop(SqStack &s,c
4、har &e) /運算符出棧if = /棧為空棧的時候,返回ERROR printf("運算符棧為空!n"); return ERROR; elsee=*; /棧不為空的時候用e做返回值,刪除S的棧頂元素,并返回OKreturn OK; int StackTraverse(SqStack &s) /運算符棧的遍歷 char *t;t= ;if = printf("運算符棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!= printf(" %c",*t); /棧不為空的時候依次
5、取出棧內(nèi)元素 t+; return ERROR;(2) 數(shù)字棧局部: struct SqStackn /定義數(shù)棧 int *base; /棧底指針 int *top; /棧頂指針 int stacksize; /棧的長度;int InitStackn (SqStackn &s) /建立一個空棧S =(int*)malloc(50*sizeof(int); if(!exit(OVERFLOW); /存儲分配失敗 =; =50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if = printf("運算數(shù)棧為空!n
6、"); /棧為空的時候返回ERROR return ERROR; else e=*; /棧不為空的時候,用e作返回值,返回S的棧頂元素,并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if >=printf("運算數(shù)棧滿!n"); /棧滿的時候,追加5個存儲空間 =(int*)realloc ,+5)*sizeof(int) ); if(! exit (OVERFLOW); =+; /插入元素e為新的棧頂元素 +=5;*+=e; /棧頂指針變化return OK; int Popn(SqStac
7、kn &s,int &e) /數(shù)棧出棧if = printf(" 運算符棧為空!n"); /棧為空棧的視時候,返回ERROR return ERROR; elsee=*; /棧不空的時候,那么刪除S的棧頂元素,用e返回其值,并返回OKreturn OK; int StackTraversen(SqStackn &s) /數(shù)棧遍歷 int *t;t= ;if = printf(" 運算數(shù)棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!= printf(" %d",*t)
8、; /棧不為空的時候依次輸出 t+; return ERROR;五、算法及時間復(fù)雜度1、算法:建立兩個不同類型的空棧,先把一個# 壓入運算符棧。輸入一個算術(shù)表達式的字符串以#結(jié)束,從第一個字符依次向后讀,把讀取的數(shù)字放入數(shù)字棧,運算符放入運算符棧。判斷新讀取的運算符和運算符棧頂?shù)眠\算符號的優(yōu)先級,以便確定是運算還是把運算符壓入運算符棧。最后兩個#遇到一起那么運算結(jié)束。數(shù)字棧頂?shù)臄?shù)字就是要求的結(jié)果。2、時間復(fù)雜度:O(n)數(shù)據(jù)壓縮存儲棧,其操作主要有:建立棧int Push(SeqStack *S, char x)入棧int Pop(SeqStack *S, char x)出棧。以上各操作運算的
9、平均時間復(fù)雜度為O(n),其主要時間是消耗在輸入操作。6、 測試用例如下圖。最終結(jié)果如下圖:7、 源代碼/*第七題 算術(shù)表達式求值問題描述一個算術(shù)表達式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù),運算符只含加減乘除等四種運算符,界限符有左右括號和表達式起始、結(jié)束符“#,如:#7+15*23-28/4#。引入表達式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法求算術(shù)表達式的值。根本要求1 從鍵盤讀入一個合法的算術(shù)表達式,輸出正確的結(jié)果。2 顯示輸入序列和棧的變化過程。*/#include <>#include <
10、;>#include <>#include <>#include <>#include <>#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 /#define STACKINCREMENT 10/=/ 以下定義兩種棧,分別存放運算符和數(shù)字/=/*運算符棧局部*struct SqStack /定義棧 char *base; /棧底指針 char *top; /棧頂指針 int stacksize; /棧的長度;int InitStack (SqStack &s) /建立一個空
11、棧S if (! = (char *)malloc(50 * sizeof(char) exit(0); =; =50; return OK; char GetTop(SqStack s,char &e) /運算符取棧頂元素 if = /棧為空的時候返回ERROR printf("運算符棧為空!n"); return ERROR; else e=*; /棧不為空的時候用e做返回值,返回S的棧頂元素,并返回OK return OK; int Push(SqStack &s,char e) /運算符入棧 if >= printf("運算符棧滿!n
12、"); =(char*)realloc ,+5)*sizeof(char) ); /棧滿的時候,追加5個存儲空間 if(! exit (OVERFLOW); =+; +=5;*+=e; /把e入棧return OK; int Pop(SqStack &s,char &e) /運算符出棧if = /棧為空棧的時候,返回ERROR printf("運算符棧為空!n"); return ERROR; elsee=*; /棧不為空的時候用e做返回值,刪除S的棧頂元素,并返回OKreturn OK; int StackTraverse(SqStack &am
13、p;s) /運算符棧的遍歷 char *t;t= ;if = printf("運算符棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!= printf(" %c",*t); /棧不為空的時候依次取出棧內(nèi)元素 t+; return ERROR;/*數(shù)字棧局部* struct SqStackn /定義數(shù)棧 int *base; /棧底指針 int *top; /棧頂指針 int stacksize; /棧的長度;int InitStackn (SqStackn &s) /建立一個空棧S =(int*)mall
14、oc(50*sizeof(int); if(!exit(OVERFLOW); /存儲分配失敗 =; =50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if = printf("運算數(shù)棧為空!n"); /棧為空的時候返回ERROR return ERROR; else e=*; /棧不為空的時候,用e作返回值,返回S的棧頂元素,并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if >=printf("運算數(shù)棧滿!n")
15、; /棧滿的時候,追加5個存儲空間 =(int*)realloc ,+5)*sizeof(int) ); if(! exit (OVERFLOW); =+; /插入元素e為新的棧頂元素 +=5;*+=e; /棧頂指針變化return OK; int Popn(SqStackn &s,int &e) /數(shù)棧出棧if = printf(" 運算符棧為空!n"); /棧為空棧的視時候,返回ERROR return ERROR; elsee=*; /棧不空的時候,那么刪除S的棧頂元素,用e返回其值,并返回OKreturn OK; int StackTraversen
16、(SqStackn &s) /數(shù)棧遍歷 int *t;t= ;if = printf(" 運算數(shù)棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!= printf(" %d",*t); /棧不為空的時候依次輸出 t+; return ERROR;/=/ 以下定義函數(shù)/=int Isoperator(char ch) /判斷是否為運算符,分別將運算符和數(shù)字進入不同的棧switch (ch)case '+':case '-':case '*':case '
17、;/':case '(':case ')':case '#':return 1;default:return 0;int Operate(int a, char op, int b) /運算操作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
18、 Precede(char ch1, char ch2) /運算符優(yōu)先級的比擬 char p; switch(ch1) case '+': case '-': if (ch2='+'|ch2='-'|ch2=')'|ch2='#') p = '>' /ch1運算符的優(yōu)先級小于ch2運算符 else p = '<' break; case '*': case '/': if (ch2 = '(') p =
19、39;<' else p = '>' break; case '(': if (ch2 = ')')p = '=' else if (ch2 = '#') printf(" 表達式錯誤!運算符不匹配!n") ;exit(0); elsep = '<' break ; case ')': if (ch2 = '(') printf(" 表達式錯誤!運算符不匹配!n") ;exit(0); else p =
20、 '>' break ; case '#': if (ch2 = ')') printf(" 表達式錯誤!運算符不匹配!n") ; exit(0); else if (ch2 = '#')p = '=' elsep='<' break; return p; /=/ 以下是求值過程/=int EvaluateExpression() /參考書p53算法 int a, b, temp, answer; char ch,op,e; char *str; int j = 0;
21、 SqStackn OPND; /OPND為運算數(shù)字棧 SqStack OPTR; /OPTR為運算符棧 InitStack(OPTR); Push(OPTR,'#'); /,所以此棧底是'#',因為運算符棧以'#'作為結(jié)束標志 InitStackn(OPND); / printf("nn按任意鍵開始求解:nn"); / ch=getch(); printf("n請輸入表達式并以'#'結(jié)束:n"); str =(char*)malloc(50*sizeof(char); gets(str);
22、 ch=strj; /ch是字符型的,而e是整型的整數(shù) j+; GetTop(OPTR,e); /e為棧頂元素返回值 while (ch!='#' | e!='#') if (!Isoperator(ch) /遇到數(shù)字,轉(zhuǎn)換成十進制并計算 temp=ch-'0' /將字符轉(zhuǎn)換為十進制數(shù) ch=strj; j+; while(!Isoperator(ch) temp=temp*10 + ch-'0' /將逐個讀入運算數(shù)的各位轉(zhuǎn)化為十進制數(shù) ch=strj; j+; Pushn(OPND,temp); else if (Isopera
23、tor(ch) /判斷是否是運算符,不是運算符那么進棧 switch (Precede(e,ch) case '<' : Push(OPTR,ch); / 棧頂元素優(yōu)先權(quán)低 ch = strj+;printf("nn 運算符棧為:n"); /輸出棧,顯示棧的變化StackTraverse(OPTR);printf("n 運算數(shù)棧為:n");StackTraversen(OPND);break; case '=' : Pop(OPTR,op); / 脫括號并接收下一字符 ch = strj+ ;printf("
24、;nn 運算符棧為:n");StackTraverse(OPTR);printf("n 數(shù)棧為:n");StackTraversen(OPND);break; case '>' : Pop(OPTR,op); /彈出最上面兩個,并運算,把結(jié)果進棧 Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf("nn 運算符棧為:n");StackTraverse(OPTR);printf("n 數(shù)棧為:n");StackTraversen(OPN
25、D); else printf("您的輸入有問題,請檢查重新輸入!"); exit(0); GetTop(OPTR,e); /取出運算符棧最上面元素是否是'#' /while GetTopn(OPND,answer); /已輸出。數(shù)字棧最上面即是最終結(jié)果 return answer;/=/ 執(zhí)行局部/=void ShowMenu()printf("nn");printf("n");printf(" n");printf(" 表達式求值系統(tǒng) n");printf(" n");printf("n");void Quit();voi
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 廠區(qū)生態(tài)園林養(yǎng)護與環(huán)保責(zé)任合同
- 財務(wù)數(shù)據(jù)處理保密協(xié)議范本
- 綠色建材標準磚銷售代理合作協(xié)議
- 腫瘤科介入術(shù)后護理
- 中醫(yī)護理方案在臨床的應(yīng)用
- 高端商業(yè)綜合體地下車庫租賃合同范本
- 投資收益財產(chǎn)分配協(xié)議
- 茶葉展會參展商合作協(xié)議
- 倉儲物流安全風(fēng)險評估合同模板
- 2025年變電站兩票培訓(xùn)大綱
- 行業(yè)特定市場調(diào)研方法與技巧分享
- 大骨節(jié)考試題及答案
- 護理病歷質(zhì)控標準
- 2025年小學(xué)五年級數(shù)學(xué)期末沖刺卷:數(shù)學(xué)基礎(chǔ)知識鞏固
- CSCO惡性血液病診療指南(2025)解讀
- T/CHTS 20036-2023公路橋梁用硬聚氯乙烯聲測管
- 立訊精密經(jīng)營管理體系
- 軟式內(nèi)鏡清洗消毒技術(shù)規(guī)范2025
- 《動物保定技術(shù)》課件
- 北京市朝陽區(qū)2023-2024學(xué)年四年級下學(xué)期語文期末考試卷(含答案)
- 上樣合作協(xié)議合同協(xié)議
評論
0/150
提交評論