版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、合肥學院計算機科學與技術系課程設計報告20 12 20 13 學年第 2 學期課程數據結構與算法 課程設計名稱算數表達式的求解學生姓名周麗娟學號1104012013專業(yè)班級11計本3班指導教師李紅20 13 年 3 月 【問題描述】(算數表達式的求解)給定一個算數表達式,通過程序求出最后的結果?!疽蟆?、 從鍵盤輸入要求解的算術表達式;2、 采用棧結構進行算數表達式的求解過程;3、 能夠判斷算數表達式的正確與否;4、 對于錯誤表達式給出提示;5、 對于正確表達時給出最后的結果。1、 問題分析和任務定義有題目可知,程序要求給定一算數表達式并計算最后的結果,我們知道,在高級語言中,任何一個表達式
2、都是有操作數、運算符和界限符組成。在計算過程中,還要考慮表達式中有無括號以及左右括號之分。由于運算符有優(yōu)先級的高低,因此一個算數表達是不可能總是按順序執(zhí)行。 通過以上可知,可以用棧來實現(xiàn)運算符的優(yōu)先級完成算術表達式的求解。為實現(xiàn)算法的優(yōu)先級,設置兩個棧:一個稱為操作數棧opnd,用以寄存操作數和運算結果,另一個為操作符棧optr,用以寄存運算符。該算法的基本思想是:(1) 首先置操作數棧opnd為空棧,表達式結束符“#”為操作符棧optr的棧底元素。(2)依次讀入表達式中每個字符,若為操作數,則進opnd棧;若是運算符,則與optr棧的棧頂運算符比較優(yōu)先級后做相應操作:若當前操作符大于optr
3、棧的棧頂,則當前操作符入棧;否則,opnd棧的棧頂元素、次棧頂元素出棧,同時optr棧的棧頂元素也出棧,形成運算,并將結果壓入opnd棧,直至整個表達式求值完畢(即optr棧的棧頂元素和當前讀入的字符均為“#”)。 對于算術表達式的輸入,本程序采用gets()的方法讀入,將運算符+,-,*,/,(,),#存儲在數組中時,定義表達式求解函數,在函數中判斷讀入的字符,如果是運算符,將這些字符入操作符optr棧,并比較優(yōu)先級,判斷是否運算。若讀入的字符為0到9之間的數字時,用字符相減轉化為整型,然后將轉化后的整型再轉化為ASCII的形式壓入操作數棧opnd中。2、數據結構的選擇和概要設計(1) 存儲
4、結構設計本程序主要采用順序棧結構類型(Stack)來存儲表達式計算中的數據。程序中需要建立兩個棧,一個棧用于寄存運算符,另一個則用于寄存操作數和計算結果,故需要建立兩個順序棧結構類型。(2) 算數優(yōu)先級設計 對一任意的表達式,由于表達式中運算符的優(yōu)先級不同,可能會使表達式不按順序進行計算。在本程序中定義函數Proceed()來比較運算符的優(yōu)先級,而函數中各優(yōu)先級的比較主要根據以下優(yōu)先級比較的表格:表1:運算符優(yōu)先級運算符+-*/()#用數字表示0123456棧內操作符的優(yōu)先級3355160棧外操作符的優(yōu)先級2244610 在Precede()函數中定義兩個字符型參數變量op和c,其中op表示棧
5、頂運算符,c表示當前讀入運算符,對于當前運算符是否入棧,進行如下操作:比較當前運算符和棧頂運算符的優(yōu)先級的大小: 1、如果當前運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級,即op<c;令函數返回值為'<',并將當前運算符進optr棧。 2、如果當前運算符的優(yōu)先級小于棧頂運算符的優(yōu)先級,即op>c;令函數返回值為'>',此時應將棧頂運算符出棧和棧頂、次棧頂操作數出棧并進行相應的運算。 3、如果當前元素的優(yōu)先級等于棧頂運算符的優(yōu)先級,即op=c;令函數的返回值為'=',此時界限符內的表達式已計算完畢。(3)程序模塊設計 1)程序模塊
6、本程序主要包含3個模塊:主程序模塊、計算模塊以及順序棧操作模塊,調用關系如圖所示:順序棧操作模塊計算模塊主程序模塊 圖1:程序模塊圖 2)系統(tǒng)功能模塊 本程序大致包含10個函數,其中包含主函數。每個函數都有其相對應的功能實現(xiàn)。 操作符的輸入函數 int In(char c); 運算符比較優(yōu)先級函數 char Proceed(char op,char c); 進行四則運算函數 int Operate(int a,char a1,int b); 實現(xiàn)表達式的求值函數 int EvalExpres(void); 初始化棧函數 void InitStack(Stack *s); 入棧函數 void P
7、ush(Stack *s, int x); 出棧函數 int Pop(Stack *s); 取棧頂元素函數 int GetTop(Stack *s) ; 判??蘸瘮?void Empty(Stack *s); 主函數 int main() 3)函數之間主要調用的關系圖 本程序主要包含10個程序,各程序之間的關系如圖所示:(部分函數用以上的編號表示)Void main()Int EvalExpres(void) 圖2:函數之間調用關系圖 3、詳細設計和編碼(1)、結構體類型的定義 typedef struct int dataMAXSIZE; int top; int base; /棧底 Sta
8、ck; (2) 、全局變量定義/以下為函數聲明void InitStack(Stack *); /初始化棧 int Empty(Stack *); /判空棧 void Push(Stack *, int ); /進棧 int Pop(Stack *);/出棧 int GetTop(Stack *); /取棧頂元素 int Operate(int ,char ,int ); / 計算結果 char Proceed(char ,char ); / 比較優(yōu)先級 int In(char ); /判斷輸入符int EvalExpres(void); /表達式計算函數/ 定義兩個棧分別存放運算符和操作數S
9、tack StackR,StackD; (3) 、系統(tǒng)主要子程序的詳細設計 1)、主函數模塊設計int main()/主函數 int v; char ch;while(1) printf("t*歡迎使用算術表達式的求解的小程序*n"); v = EvalExpres(); printf("t表達式的計算結果為:%d",v); printf("ntInput 'n' to quit and ENTER run again:"); do scanf("%c",&ch); if(ch = '
10、;n' | ch = 'N') exit(0); while(ch!='n'); system("cls"); return 0; 在主函數中,設定用戶操作界面的形式,通過調用表達式求解的子函數實現(xiàn)算法所要實現(xiàn)的功能,然后通過while()循環(huán)語句控制,可以實現(xiàn)多次調試。 2)、計算函數模塊 int Operate(int a,char a1,int b) int s; int d1 = a; int d2 = b; /把字符ab變?yōu)閷獢底?switch(a1) case '+': s = d1+d2; break;
11、 case '-': s = d2-d1;break; case '*': s = d1*d2; break; case '/': s = d2/d1; return (s+'0'); /將運算結果轉化為ascii碼的形式入棧, 在計算函數中,定義3個變量,表示基本運算中的變量。采用開關語句實現(xiàn)表達式的基本運算,將運算結果轉化為ASCII的形式返回。 3)、表達式求解的函數模塊 int EvalExpres(void) / 表達式求解函數 int a,b,i=0,s=0; char c80,r; InitStack(&St
12、ackR); /初始化棧 Push(&StackR,'#'); /將表達式起始符壓入棧 InitStack(&StackD); printf(" t請輸入表達式并以#結束:"); gets(c); while(ci!='#' | GetTop(&StackR)!='#') if(!In(ci) /判斷讀入的字符是不是運算符 不是則進opnd棧 if(ci >= '0' && ci <= '9') s += ci-'0' /字符的
13、ascii相減將字符型轉化為整型 while(!In(c+i) /繼續(xù)判斷下一個字符,若不是運算符,表明為多位數,直到讀取到字符為運算符為止 s*=10; s += ci-'0' Push(&StackD,s+'0'); /將整型轉化為ascii的形式入棧,使字符在棧內以ascii的形式保存,實現(xiàn)多位數的計算 s = 0; /初始化s,繼續(xù)判斷 else printf("你輸入的表達式有誤!n"); return 0; else switch(Proceed(GetTop(&StackR),ci) /此函數用來比較讀取的運算符
14、和棧頂運算符的優(yōu)先級 case '<': /棧頂的元素優(yōu)先級低,當前運算符入棧 Push(&StackR,ci); i+; break; case '=': Pop(&StackR); i+; break; case '>': /棧頂的優(yōu)先級高則出棧,并將計算結果壓入棧內 r = Pop(&StackR); a = Pop(&StackD)-'0' /操作數在棧內以ascii的形式存儲,出站后要將ascii轉化為整型,然后進行運算 b = Pop(&StackD)-'0&
15、#39; Push(&StackD,Operate(a,r,b) ; break; return (GetTop(&StackD)-'0'); / 將棧頂元素轉化為整型的形式輸出 對于表達式求解函數,在程序中主要思想是對讀入的表達式進棧進行判斷。若讀入的是0到9之間的字符,將這些字符采用ascii相減的形式轉化為整型,再入opnd棧,若讀入的字符為運算符,則將運算符入棧,并比較運算符之間的優(yōu)先級,看是否運算,若棧頂的運算符小于當前輸入的運算符,則不需運算,只要將當前運算符入棧即可。否則,運算。運算時先將optr棧的棧頂運算符和opnd棧的棧頂、次棧頂元素出棧,并
16、將opnd棧中出棧的元素的ASCII形式轉化為整型再計算,最后講計算結果再轉化為ASCII碼的形式壓入opnd棧中。使表達式求解函數返回值為opnd的棧頂元素。4、上級調試過程遇到問題以及解決方案 問題1、調試時沒有錯誤,但運行時顯示錯誤。解決方案:通過它提示的錯誤和警告,在判斷是否為運算符的子函數中出現(xiàn)錯誤,如果為運算符時返回1,其次返回0,在返回0時沒有用else,這樣使得整個子函數可以返回一個有效值。 問題2、調試時程序顯示沒有錯誤,可以運行,但在運行時結果卻出現(xiàn)錯誤。解決方案:把程序從頭看了一遍,發(fā)現(xiàn)在比較優(yōu)先級的函數中,優(yōu)先級的比較比較亂,而且部分出錯,后來查了關于運算符優(yōu)先級的資料
17、,通過在紙上把各種優(yōu)先級列出,解決這個錯誤。算法的時間復雜度 由于在主函數用到嵌套循環(huán),故算法的時間復雜度為O(n2)。5、 測試結果及其分析 (1)、實現(xiàn)基本的加減乘除運算,當想要繼續(xù)輸入表達式時點擊enter鍵,若要結束,點擊n或N鍵即可,而且可實現(xiàn)多位數的運算。(2)、實現(xiàn)復雜的算術表達式(3)、錯誤表達式的處理6、用戶使用說明 (1)本程序執(zhí)行的文件為“算數表達式的求解問題”。 (2)所求表達式中都只是僅包含加、減、乘、除4種基本運算的,其中也包含括號的應用,所有的運算對象均為簡單變量,要求將表達式中的數字字符轉化為整型,且輸入表達式以“#”結束。 (3)輸入表達式時,以#結束,當點擊
18、回車鍵時即可得到運算結果,當想繼續(xù)輸入表達式時,再次點擊回車鍵即可,當想結束時,點擊字母n或N。 (4)當輸入錯誤表達式時,程序會給出相應的提醒。7、 參考文獻 (1)王昆侖 、李紅主編,數據結構與算法,北京:中國鐵道出版社,2007年5月 (2)阮宏一 、魯靜主編,數據結構課程設計(C/C+描述),北京:電子工業(yè)出版社,2011年1月8、 附錄(源程序):#include <malloc.h>#include <stdio.h>#define MAXSIZE 16typedef struct int dataMAXSIZE; int top; int base; /棧
19、低 Stack; / 順序棧的定義/以下為函數聲明void InitStack(Stack *); /初始化棧 int Empty(Stack *); /判空棧 void Push(Stack *, int ); /進棧 int Pop(Stack *);/出棧 int GetTop(Stack *); /取棧頂元素 int Operate(int ,char ,int ); / 計算結果 char Proceed(char ,char ); / 比較優(yōu)先級 int In(char ); /判斷輸入符int EvalExpres(void); /表達式計算函數/ 定義兩個棧分別存放運算符和操作
20、數Stack StackR,StackD; int main()/主函數 int v; char ch;while(1) printf("t*歡迎使用算術表達式的求解的小程序*n"); v = EvalExpres(); printf("t表達式的計算結果為:%d",v); printf("ntInput 'n' to quit and ENTER run again:"); do scanf("%c",&ch); if(ch = 'n' | ch = 'N'
21、) exit(0); while(ch!='n'); system("cls"); return 0; void InitStack(Stack *s) /初始化棧 s->top = 0; s->base = 0; int Empty(Stack *s)/判斷棧是否為空 if(s->top =s->base) return 1; /??諘r返回1,否則返回0 else return 0; void Push(Stack *s, int x) / 進棧 if(s->top = MAXSIZE) printf("terror
22、!n");exit(0); else s->datas->top = x; s->top+; int Pop(Stack *s)/ 出棧 int e; if(Empty(s) printf("terror!n"); exit(0); else s->top-; e = s->datas->top; return e; int GetTop(Stack *s) /取棧頂元素 if(Empty(s) printf("terror!n"); exit(0); else return s->datas->
23、top-1; int EvalExpres(void) / 表達式求解函數 int a,b,i=0,s=0; char c80,r; InitStack(&StackR); Push(&StackR,'#'); InitStack(&StackD); printf(" t請輸入表達式并以#結束:"); gets(c); while(ci!='#' | GetTop(&StackR)!='#') if(!In(ci) /判斷讀入的字符不是運算符 是則進棧 if(ci >= '0
24、9; && ci <= '9') s += ci-'0' /字符相減將字符型轉化為整型 while(!In(c+i) /繼續(xù)判斷下一個字符,若不是運算符,表明為多位數,直到讀取到字符為運算符為止 s*=10; s += ci-'0' Push(&StackD,s+'0'); /將整型轉化為ascii的形式入棧,使字符在棧內以ascii的形式保存,實現(xiàn)多位數的計算 s = 0; /初始化s,繼續(xù)判斷 else printf("t你輸入的表達式有誤!n"); exit(0); else
25、 switch(Proceed(GetTop(&StackR),ci) /此函數用來比較讀取的運算符和棧頂運算符的優(yōu)先級 case '<': /棧頂的元素優(yōu)先級低,當前運算符入棧 Push(&StackR,ci); i+; break; case '=': Pop(&StackR); i+; break; case '>': /棧頂的優(yōu)先級高則出棧,并將計算結果壓入棧內 r = Pop(&StackR); a = Pop(&StackD)-'0' /操作數在棧內以ascii的形式
26、存儲,出站后要將ascii轉化為整型,然后進行運算 b = Pop(&StackD)-'0' Push(&StackD,Operate(a,r,b) ; break; return (GetTop(&StackD)-'0'); / 將棧頂元素轉化為整型的形式輸出 int In(char c) /判斷C是否為運算符是返回1否則返回0 char ch7='+','-','*','/','#','(',')' int i; for(i
27、 = 0; i < 7; i+) if(c = chi) return 1; return 0; char Proceed(char op,char c) /op為棧頂元素,c為當前讀入的運算符,比較二者的優(yōu)先級 char ch; if(op='(' && c=')' | op='#' && c='#' ) ch = '=' else if(op='+' | op='-') /*棧頂元素為+或-的時候*/ switch(c) case '
28、+': case '-': case ')': case '#': ch = '>' break; case '*': case '/': case '(': ch = '<' else if(op='*' | op='/') /*棧頂元素為*或/的時候*/ switch(c) case '+': case '-': case '*': case '/': case ')': case '#': ch = '>' break; case '(': ch = '<' else if(op='(') /*棧頂元素為(的時候*/ switch(c) case '+': case '
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 供應鏈中的供應鏈決策支持系統(tǒng)考核試卷
- 農業(yè)金屬工具行業(yè)政策分析考核試卷
- 員工激勵與績效改進考核試卷
- 光學儀器的應用領域考核試卷
- 儀器制造中的精密加工技術考核試卷
- 網頁課程設計新的
- 2025-2030全球落地式化學發(fā)光免疫分析儀行業(yè)調研及趨勢分析報告
- 2025-2030全球艾滋病預防藥行業(yè)調研及趨勢分析報告
- 餐飲電商學堂課程設計書
- 課程設計自評
- 浙江省安全員C證考試題庫及答案(推薦)
- 《文化苦旅》讀書分享 PPT
- 氧化鋁生產工藝教學拜耳法
- 2023年十八項醫(yī)療核心制度考試題與答案
- 氣管切開患者氣道濕化的護理進展資料 氣管切開患者氣道濕化
- 管理模板:某跨境電商企業(yè)組織結構及部門職責
- 底架總組裝工藝指導書
- 簡單臨時工勞動合同模板(3篇)
- 聚酯合成反應動力學
- 上??萍即髮W,面試
- 《五年級奧數總復習》精編課件
評論
0/150
提交評論