算數(shù)表達式的求解課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-05-01 格式：doc 頁數(shù)：18 大?。?86.31KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩17頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　合肥學院　　計算機科學與技術系　　課程設計報告　　20 12 ～20 13 學年第 2 學期　　20 13 年 3 月&l

2、t;/p>　　【問題描述】　?。ㄋ銛?shù)表達式的求解）給定一個算數(shù)表達式，通過程序求出最后的結果。　　【要求】　　從鍵盤輸入要求解的算術表達式；　　采用棧結構進行算數(shù)表達式

3、的求解過程；　　能夠判斷算數(shù)表達式的正確與否；　　對于錯誤表達式給出提示；　　對于正確表達時給出最后的結果。　　問題分析和任務定義　　有題目可知，程序要求給定一算數(shù)表達式并計算最后的結果，我們

4、知道，在高級語言中，任何一個表達式都是有操作數(shù)、運算符和界限符組成。在計算過程中，還要考慮表達式中有無括號以及左右括號之分。由于運算符有優(yōu)先級的高低，因此一個算數(shù)表達是不可能總是按順序執(zhí)行。　　通過以上可知，可以用棧來實現(xiàn)運算符的優(yōu)先級完成算術表達式的求解。　　為實現(xiàn)算法的優(yōu)先級，設置兩個棧：一個稱為操作數(shù)棧opnd，用以寄存操作數(shù)和運算結果，另一個為操

5、作符棧optr，用以寄存運算符。　　該算法的基本思想是：　　首先置操作數(shù)棧opnd為空棧，表達式結束符“#”為操作符棧optr的棧底元素。　　（2）依次讀入表達式中每個字符，若為操作數(shù)，則進opnd棧；若是運算符，則與optr棧的棧頂運算符比較優(yōu)先級后做相應操作：若當前操作符大于optr棧的棧頂，則當前操作符入棧

6、；否則，opnd棧的棧頂元素、次棧頂元素出棧，同時optr棧的棧頂元素也出棧，形成運算，并將結果壓入opnd棧，直至整個表達式求值完畢（即optr棧的棧頂元素和當前讀入的字符均為“#”）。　　對于算術表達式的輸入，本程序采用gets()的方法讀入，將運算符‘+’，‘-’，‘*’，‘/’，‘（’，‘）’，‘#’存儲在數(shù)組中時，定義表達式求解函數(shù)，在函數(shù)中判斷讀入的字符，如果是運算符，將這些字符入操

7、作符optr棧，并比較優(yōu)先級，判斷是否運算。若讀入的字符為‘0’到‘9’之間的數(shù)字時，用字符相減轉化為整型，然后將轉化后的整型再轉化為ASCII的形式壓入操作數(shù)棧opnd中。　　2、數(shù)據(jù)結構的選擇和概要設計　　存儲結構設計　　本程序主要采用順序棧結構類型（Stack）來存儲表

8、達式計算中的數(shù)據(jù)。程序中需要建立兩個棧，一個棧用于寄存運算符，另一個則用于寄存操作數(shù)和計算結果，故需要建立兩個順序棧結構類型。　　算數(shù)優(yōu)先級設計　　對一任意的表達式，由于表達式中運算符的優(yōu)先級不同，可能會使表達式不按順序進行計算。在本程序中定義函數(shù)Proceed（）來比較運算符的優(yōu)先級，而函數(shù)中各優(yōu)先級的比較主要根據(jù)

9、以下優(yōu)先級比較的表格：　　表1：運算符優(yōu)先級　　在Precede（）函數(shù)中定義兩個字符型參數(shù)變量op和c，其中op表示棧頂運算符，c表示當前讀入運算符，對于當前運算符是否入棧，進行如下操作：　　比較當前運算符和棧頂運算符的優(yōu)先級的大?。?lt;/p>

10、;　　1、如果當前運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級，即op<c;令函數(shù)返回值為'<'，并將當前運算符進optr棧。　　2、如果當前運算符的優(yōu)先級小于棧頂運算符的優(yōu)先級，即op>c；令函數(shù)返回值為'>'，此時應將棧頂運算符出棧和棧頂、次棧頂操作數(shù)出棧并進行相應的運算。　　3、如果當前元素的優(yōu)先級等

11、于棧頂運算符的優(yōu)先級，即op=c；令函數(shù)的返回值為'='，此時界限符內的表達式已計算完畢。　　（3）程序模塊設計　　1）程序模塊　　本程序主要包含3個模塊：主程序模塊、計算模塊以及順序棧操作模塊，調用關系如圖所示：<

12、/p>　　圖1：程序模塊圖 　　2）系統(tǒng)功能模塊　　本程序大致包含10個函數(shù)，其中包含主函數(shù)。每個函數(shù)都有其相對應的功能實現(xiàn)。　　操作符的輸入函數(shù) int In(char c);　　運算符比較優(yōu)先級函

13、數(shù) char Proceed(char op,char c);　　進行四則運算函數(shù) int Operate(int a,char a1,int b);　　實現(xiàn)表達式的求值函數(shù) int EvalExpres(void);　　初始化棧函數(shù) void InitStack(Stack *s);&l

14、t;p>　　入棧函數(shù) void Push(Stack *s, int x);　　出棧函數(shù) int Pop(Stack *s);　　取棧頂元素函數(shù) int GetTop(Stack *s) ;　　判?？蘸瘮?shù) void Empty(Stack *s);　　主函數(shù)

15、int main()　　3)函數(shù)之間主要調用的關系圖　　本程序主要包含10個程序，各程序之間的關系如圖所示：（部分函數(shù)用以上的編號表示）　　圖2：函數(shù)之間調用關系圖 　　3、詳細設計和編碼

16、（1）、結構體類型的定義　　typedef struct　　{ 　　int data[MAXSIZE]; 　　int top; 　　int base; //

17、棧底 　　}Stack; 　　、全局變量定義　　//以下為函數(shù)聲明　　void InitStack(Stack *); //初始化棧 </

18、p>　　int Empty(Stack *); //判空棧　　void Push(Stack *, int ); //進棧　　int Pop(Stack *);//出棧　　int GetTop(Stack *); //取棧頂元素

19、　int Operate(int ,char ,int ); // 計算結果　　char Proceed(char ,char ); // 比較優(yōu)先級　　int In(char ); //判斷輸入符　　int EvalExpres(void); //表達式計算函數(shù)<p&

20、gt;　　// 定義兩個棧分別存放運算符和操作數(shù)　　Stack StackR,StackD; 　　、系統(tǒng)主要子程序的詳細設計　　1）、主函數(shù)模塊設計　　int main()//主函數(shù)　　{

21、;　　int v; 　　char ch;　　while(1)　　{

22、　printf("\t************歡迎使用算術表達式的求解的小程序************\n"); 　　v = EvalExpres(); 　　printf("\t表達式的計算結果為:%d",v);

23、　　printf("\n\tInput 'n' to quit and ENTER run again:"); 　　do　　{ 　　scanf("%c",&ch

24、); 　　if(ch == 'n' || ch == 'N') 　　exit(0); 　　}while(ch!='\n'); 　　system("cls"); <

25、/p>　　}　　return 0; 　　}　　在主函數(shù)中，設定用戶操作界面的形式，通過調用表達式求解的子函數(shù)實現(xiàn)算法所要實現(xiàn)的功能，然后通過while()循環(huán)語句控制，可以實現(xiàn)多次調試。

26、　　2）、計算函數(shù)模塊 　　int Operate(int a,char a1,int b) 　　{ 　　int s; 　　int d1 = a;

27、　　int d2 = b; //把字符ab變?yōu)閷獢?shù)字 　　switch(a1) 　　{ 　　case '+': 　　s = d1+d2;

28、　　break; 　　case '-': 　　s = d2-d1;　　break; 　　case '*': 　　s = d1*d2; &l

29、t;p>　　break; 　　case '/': 　　s = d2/d1; 　　}　　return (s+'0'); //將運算結果轉化為ascii碼的形式入

30、棧， 　　}　　在計算函數(shù)中，定義3個變量，表示基本運算中的變量。采用開關語句實現(xiàn)表達式的基本運算，將運算結果轉化為ASCII的形式返回。　　3）、表達式求解的函數(shù)模塊　　int EvalExpres(void) // 表達式

31、求解函數(shù)　　{ 　　int a,b,i=0,s=0; 　　char c[80],r; 　　InitStack(&StackR); //初始化棧 　　Push

32、(&StackR,'#'); //將表達式起始符壓入棧 　　InitStack(&StackD); 　　printf(" \t請輸入表達式并以‘#’結束："); 　　gets(c); 　　w

33、hile(c[i]!='#' || GetTop(&StackR)!='#') 　　{ 　　if(!In(c[i])) //判斷讀入的字符是不是運算符不是則進opnd棧 　　{ if(c[i] >= &#

34、39;0' && c[i] <= '9') 　　{ 　　s += c[i]-'0'; //字符的ascii相減將字符型轉化為整型

35、　　while(!In(c[++i])) //繼續(xù)判斷下一個字符，若不是運算符，表明為多位數(shù)，直到讀取到字符為運算符為止 　　{ 　　s*=10; 　　s += c[i]-'0';

36、 　　} 　　Push(&StackD,s+'0'); //將整型轉化為ascii的形式入棧，使字符在棧內以ascii的形式保存，實現(xiàn)多位數(shù)的計算 　　s = 0; //初始化s，繼續(xù)判斷

37、　　} 　　else 　　{ 　　printf("你輸入的表達式有誤!\n"); 　　return 0;

38、 　　} 　　} 　　else 　　switch(Proceed(GetTop(&StackR),c[i])) //此函

39、數(shù)用來比較讀取的運算符和棧頂運算符的優(yōu)先級 　　{ 　　case '<': //棧頂?shù)脑貎?yōu)先級低，當前運算符入棧 　　Push(&StackR,c[i]); </p

40、>　　i++; 　　break; 　　case '=': 　　Pop(&StackR);

41、　i++; 　　break; 　　case '>': //棧頂?shù)膬?yōu)先級高則出棧，并將計算結果壓入棧內 　　r = Pop(&StackR); </p&g

42、t;　　a = Pop(&StackD)-'0'; //操作數(shù)在棧內以ascii的形式存儲，出站后要將ascii轉化為整型，然后進行運算 　　b = Pop(&StackD)-'0'; 　　Push(&StackD,Operat

43、e(a,r,b)) ; 　　break; 　　} 　　}　　return (GetTop(&

44、StackD)-'0'); // 將棧頂元素轉化為整型的形式輸出　　}　　對于表達式求解函數(shù)，在程序中主要思想是對讀入的表達式進棧進行判斷。若讀入的是‘0’到‘9’之間的字符，將這些字符采用ascii相減的形式轉化為整型，再入opnd棧，若讀入的字符為運算符，則將運算符入棧，并比較運算符之間的優(yōu)先級，

45、看是否運算，若棧頂?shù)倪\算符小于當前輸入的運算符，則不需運算，只要將當前運算符入棧即可。否則，運算。運算時先將optr棧的棧頂運算符和opnd棧的棧頂、次棧頂元素出棧，并將opnd棧中出棧的元素的ASCII形式轉化為整型再計算，最后講計算結果再轉化為ASCII碼的形式壓入opnd棧中。使表達式求解函數(shù)返回值為opnd的棧頂元素。　　4、上級調試過程</p

46、>　　遇到問題以及解決方案　　問題1、調試時沒有錯誤，但運行時顯示錯誤。　　解決方案：通過它提示的錯誤和警告，在判斷是否為運算符的子函數(shù)中出現(xiàn)錯誤，如果為運算符時返回1，其次返回0，在返回0時沒有用else，這樣使得整個子函數(shù)可以返回一個有效值。　　問題2、調試時程序顯示沒有錯誤，可以

47、運行，但在運行時結果卻出現(xiàn)錯誤。　　解決方案：把程序從頭看了一遍，發(fā)現(xiàn)在比較優(yōu)先級的函數(shù)中，優(yōu)先級的比較比較亂，而且部分出錯，后來查了關于運算符優(yōu)先級的資料，通過在紙上把各種優(yōu)先級列出，解決這個錯誤。　　算法的時間復雜度　　由于在主函數(shù)用到嵌套循環(huán)，故算法的時間復雜度為O（n

48、^2）。　　測試結果及其分析　?。?）、實現(xiàn)基本的加減乘除運算，當想要繼續(xù)輸入表達式時點擊enter鍵，若要結束，點擊n或N鍵即可，而且可實現(xiàn)多位數(shù)的運算。　　（2）、實現(xiàn)復雜的算術表達式　　（3）、錯誤表達式的處理

49、;　　6、用戶使用說明　?。?）本程序執(zhí)行的文件為“算數(shù)表達式的求解問題”。　　（2）所求表達式中都只是僅包含加、減、乘、除4種基本運算的，其中也包含括號的應用，所有的運算對象均為簡單變量，要求將表達式中的數(shù)字字符轉化為整型，且輸入表達式以“#”結束。

50、?。?）輸入表達式時，以‘#’結束，當點擊回車鍵時即可得到運算結果，當想繼續(xù)輸入表達式時，再次點擊回車鍵即可，當想結束時，點擊字母‘n’或‘N’。　　（4）當輸入錯誤表達式時，程序會給出相應的提醒。　　參考文獻　　（1）王昆侖、李紅主編，數(shù)據(jù)結構與算法，北京：中國鐵道出版社

51、，2007年5月　　（2）阮宏一、魯靜主編，數(shù)據(jù)結構課程設計（C/C++描述），北京：電子工業(yè)出版社，2011年1月　　附錄（源程序）：　　#include <malloc.h>　　#include <stdio.

52、h>　　#define MAXSIZE 16　　typedef struct　　{ 　　int data[MAXSIZE]; 　　int top;

53、　　int base; //棧低 　　}Stack; // 順序棧的定義　　//以下為函數(shù)聲明　　void InitStack(Stack *); //初始化棧 　　int

54、 Empty(Stack *); //判空棧　　void Push(Stack *, int ); //進棧　　int Pop(Stack *);//出棧　　int GetTop(Stack *); //取棧頂元素　　int Operate(int ,ch

55、ar ,int ); // 計算結果　　char Proceed(char ,char ); // 比較優(yōu)先級　　int In(char ); //判斷輸入符　　int EvalExpres(void); //表達式計算函數(shù)　　// 定義兩個棧分別存放運算符和

56、操作數(shù)　　Stack StackR,StackD; 　　int main()//主函數(shù)　　{ 　　int v; 　　char c

57、h;　　while(1)　　{ 　　printf("\t************歡迎使用算術表達式的求解的小程序************\n");

58、;　　v = EvalExpres(); 　　printf("\t表達式的計算結果為:%d",v); 　　printf("\n\tInput 'n' to quit and ENTER run again:");

59、　　do　　{ 　　scanf("%c",&ch); 　　if(ch == 'n' || ch == 'N') </p&g

60、t;　　exit(0); 　　}while(ch!='\n'); 　　system("cls"); 　　}　　return 0; <p&

61、gt;　　}　　void InitStack(Stack *s) //初始化棧　　{ 　　s->top = 0; 　　s->base = 0;

62、　　}　　int Empty(Stack *s)//判斷棧是否為空　　{ 　　if(s->top ==s->base) 　　retur

63、n 1; //?？諘r返回1，否則返回0 　　else 　　return 0;　　} 　　void Push(Stack *s, int x) // 進棧

64、　　{ 　　if(s->top == MAXSIZE) 　　{ 　　printf("\terror!\n");

65、exit(0); 　　} 　　else 　　{ 　　s->data[s->top] = x;

66、　s->top++; 　　} 　　} 　　int Pop(Stack *s)// 出棧　　{

67、　　int e; 　　if(Empty(s)) 　　{ 　　printf("\terror!\n"); 　　exit(0); </p&

68、gt;　　} 　　else 　　{ 　　s->top--; 　　e = s->data[s->top];

69、 　　return e; 　　}　　} 　　int GetTop(Stack *s) //取棧頂元素<b

70、>　　{ 　　if(Empty(s)) 　　{ 　　printf("\terror!\n"); 　　exit(0); &l

71、t;p>　　} 　　else 　　return s->data[s->top-1]; 　　}　　int EvalExpres(void) // 表達

72、式求解函數(shù)　　{ 　　int a,b,i=0,s=0; 　　char c[80],r; 　　InitStack(&StackR); 　　Push(&

73、;StackR,'#'); 　　InitStack(&StackD); 　　printf(" \t請輸入表達式并以‘#’結束："); 　　gets(c); 　　while(c[i]!='#

74、' || GetTop(&StackR)!='#') 　　{ 　　if(!In(c[i])) //判斷讀入的字符不是運算符是則進棧 　　{ if(c[i] >= '0' && c[

75、i] <= '9') 　　{ 　　s += c[i]-'0'; //字符相減將字符型轉化為整型 　　while(!In(c[++i])) //繼續(xù)判斷下

76、一個字符，若不是運算符，表明為多位數(shù)，直到讀取到字符為運算符為止 　　{ 　　s*=10; 　　s += c[i]-'0'; 　　}

77、 　　Push(&StackD,s+'0'); //將整型轉化為ascii的形式入棧，使字符在棧內以ascii的形式保存，實現(xiàn)多位數(shù)的計算 　　s = 0; //初始化s，繼續(xù)判斷　　} </p

78、>　　else 　　{ 　　printf("\t你輸入的表達式有誤!\n"); 　　exit(0);

79、　　} 　　} 　　else 　　switch(Proceed(GetTop(&StackR),c[i])) //此函數(shù)用來比較讀取的運算符和棧頂運算符的優(yōu)先級

80、 　　{ 　　case '<': //棧頂?shù)脑貎?yōu)先級低，當前運算符入棧 　　Push(&StackR,c[i]); 　　i++;

81、 　　break; 　　case '=': 　　Pop(&StackR); 　　i++; </p&

82、gt;　　break; 　　case '>': //棧頂?shù)膬?yōu)先級高則出棧，并將計算結果壓入棧內 　　r = Pop(&StackR); 　　a = Pop(&St

83、ackD)-'0'; //操作數(shù)在棧內以ascii的形式存儲，出站后要將ascii轉化為整型，然后進行運算 　　b = Pop(&StackD)-'0'; 　　Push(&StackD,Operate(a,r,b)) ; &l

84、t;/p>　　break; 　　} 　　}　　return (GetTop(&StackD)-'0'); // 將棧頂

85、元素轉化為整型的形式輸出　　}　　int In(char c) //判斷C是否為運算符是返回1否則返回0　　{ 　　char ch[7]={'+','

86、-','*','/','#','(',')'}; 　　int i; 　　for(i = 0; i < 7; i++) 　　if(c == ch[i])

87、 　　return 1; 　　return 0; 　　} 　　char Proceed(char op,char c) //op為棧頂元素，c為當前讀入的運算符,比較二者的優(yōu)先級</p&g

88、t;　　{ 　　char ch; 　　if(op=='(' && c==')' || op=='#' && c=='#' ) </p&

89、gt;　　ch = '='; 　　else if(op=='+' || op=='-') /*棧頂元素為‘+’或‘-’的時候*/ 　　switch(c) 　　{ &

90、lt;/p>　　case '+': 　　case '-': 　　case ')': 　　case '#': ch = '>'; break;

91、 　　case '*': 　　case '/': 　　case '(': ch = '<'; 　　} &l

92、t;/p>　　else if(op=='*' || op=='/') /*棧頂元素為‘*’或‘/’的時候*/ 　　switch(c) 　　{ 　　case '+': &l

93、t;/p>　　case '-': 　　case '*': 　　case '/': 　　case ')': <p&g

94、t;　　case '#': ch = '>'; break; 　　case '(': ch = '<'; 　　} 　　else if(op=='(&#

95、39;) /*棧頂元素為‘(’的時候*/ 　　switch(c) 　　{ 　　case '+': 　　case '-':

96、 　　case '*': 　　case '/': 　　case '(': ch = '<'; break; 　　case

97、 '#': 　　printf("\tError!沒有右括號!\n"); 　　exit(0); 　　} 　　else if(op==')') //棧頂元

98、素為‘)’的時候 　　switch(c) 　　{ 　　case '+': 　　case '-': <

99、p>　　case '*': 　　case '/': 　　case '#': ch = '>'; break; 　　case '(': <p

100、>　　printf("\tError!括號匹配錯誤!\n"); 　　exit(0); 　　} 　　else if(op=='#') //棧頂元素為‘#’的時候

101、　　switch(c) 　　{ 　　case '+': 　　case '-': 　　case '*'

102、: 　　case '/': 　　case '(': ch = '<'; break; 　　case ')': 　　printf(&quo

103、t;\tError!沒有左括號!\n");　　exit(0); 　　} 　　return ch; 　　} <p&

104、gt;　　int Operate(int a,char a1,int b) 　　{ 　　int s; 　　int d1 = a; 　　int d2 = b; //把字符ab變

105、為對應數(shù)字 　　switch(a1) 　　{ 　　case '+': 　　s = d1+d2; 　　break; 　　case

106、 '-': 　　s = d2-d1;　　break; 　　case '*': 　　s = d1*d2; 　　break;

107、;　　case '/': 　　if(d1!=0)　　{　　s = d2/d1;}　　else

108、{printf("\t除數(shù)不可以為0!\n");　　exit(0);} 　　}　　return (s+'0'); //將運算結果轉化為ascii碼的形式入棧，

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

算數(shù)表達式的求解課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

算數(shù)表達式的求解課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載