數(shù)據(jù)結(jié)構(gòu)課程設(shè)計表達(dá)式求值完整

1、XXXXXX大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告班級：學(xué)號：姓名：指導(dǎo)老師：目 錄一 算術(shù)表達(dá)式求值1、 需求分析2、 程序的主要功能3、 程序運行平臺4、 數(shù)據(jù)結(jié)構(gòu)5、 算法及時間復(fù)雜度6、 測試用例7、 程序源代碼二 感想體會與總結(jié)算術(shù)表達(dá)式求值一、需求分析一個算術(shù)表達(dá)式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運算符只含加減乘除等四種運算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。二、程序的主要功能（1） 從鍵

2、盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2） 顯示輸入序列和棧的變化過程。三、程序運行平臺Visual C+ 6.0版本四、數(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 (!(s.base = (char *)malloc(50 * sizeof(char) exit(0); s.top=s.base; s.stacksize=50; return

3、OK; char GetTop(SqStack s,char &e) /運算符取棧頂元素 if (s.top=s.base) /棧為空的時候返回ERROR printf("運算符棧為空!n"); return ERROR; else e=*(s.top-1); /棧不為空的時候用e做返回值，返回S的棧頂元素，并返回OK return OK; int Push(SqStack &s,char e) /運算符入棧 if (s.top-s.base >= s.stacksize) printf("運算符棧滿!n"); s.base=(ch

4、ar*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); /棧滿的時候，追加5個存儲空間 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) /運算符出棧if (s.top=s.base) /棧為空棧的時候，返回ERROR printf("運算符棧為空!n"); return ERROR; elsee=*-s.to

5、p; /棧不為空的時候用e做返回值，刪除S的棧頂元素，并返回OKreturn OK; int StackTraverse(SqStack &s) /運算符棧的遍歷 char *t;t=s.base ;if (s.top=s.base) printf("運算符棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!=s.top) printf(" %c",*t); /棧不為空的時候依次取出棧內(nèi)元素 t+; return ERROR;（2） 數(shù)字棧部分： struct SqStackn /定義數(shù)棧 int *bas

6、e; /棧底指針 int *top; /棧頂指針 int stacksize; /棧的長度;int InitStackn (SqStackn &s) /建立一個空棧S s.base=(int*)malloc(50*sizeof(int); if(!s.base)exit(OVERFLOW); /存儲分配失敗 s.top=s.base; s.stacksize=50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if (s.top=s.base) printf("運算數(shù)棧為空!n"); /棧為空的時候返

7、回ERROR return ERROR; else e=*(s.top-1); /棧不為空的時候，用e作返回值，返回S的棧頂元素，并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if (s.top-s.base >=s.stacksize)printf("運算數(shù)棧滿!n"); /棧滿的時候，追加5個存儲空間 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW); s.top=s.bas

8、e+s.stacksize; /插入元素e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK; int Popn(SqStackn &s,int &e) /數(shù)棧出棧if (s.top=s.base) printf(" 運算符棧為空!n"); /棧為空棧的視時候，返回ERROR return ERROR; elsee=*-s.top; /棧不空的時候，則刪除S的棧頂元素，用e返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /數(shù)棧遍歷 int

9、*t;t=s.base ;if (s.top=s.base) printf(" 運算數(shù)棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!=s.top) printf(" %d",*t); /棧不為空的時候依次輸出 t+; return ERROR;五、算法及時間復(fù)雜度1、算法：建立兩個不同類型的空棧，先把一個# 壓入運算符棧。輸入一個算術(shù)表達(dá)式的字符串（以#結(jié)束），從第一個字符依次向后讀，把讀取的數(shù)字放入數(shù)字棧，運算符放入運算符棧。判斷新讀取的運算符和運算符棧頂?shù)眠\算符號的優(yōu)先級，以便確定是運算還是把運算符壓入運

10、算符棧。最后兩個#遇到一起則運算結(jié)束。數(shù)字棧頂?shù)臄?shù)字就是要求的結(jié)果。2、時間復(fù)雜度：O(n)數(shù)據(jù)壓縮存儲棧，其操作主要有：建立棧int Push(SeqStack *S, char x)入棧int Pop(SeqStack *S, char x)出棧。以上各操作運算的平均時間復(fù)雜度為O(n)，其主要時間是耗費在輸入操作。6、 測試用例如圖所示。最終結(jié)果如圖所示：7、 源代碼/*第七題 算術(shù)表達(dá)式求值問題描述一個算術(shù)表達(dá)式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運算符只含加減乘除等四種運算符，界限符有左右括號和表達(dá)式起始、

11、結(jié)束符“#”，如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。基本要求（1） 從鍵盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（2） 顯示輸入序列和棧的變化過程。*/#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <conio.h>#include <ctype.h>#define OK 1#define ERROR 0#define STA

12、CK_INIT_SIZE 100 /#define STACKINCREMENT 10/=/ 以下定義兩種棧，分別存放運算符和數(shù)字/=/*運算符棧部分*struct SqStack /定義棧 char *base; /棧底指針 char *top; /棧頂指針 int stacksize; /棧的長度;int InitStack (SqStack &s) /建立一個空棧S if (!(s.base = (char *)malloc(50 * sizeof(char) exit(0); s.top=s.base; s.stacksize=50; return OK; char GetTo

13、p(SqStack s,char &e) /運算符取棧頂元素 if (s.top=s.base) /棧為空的時候返回ERROR printf("運算符棧為空!n"); return ERROR; else e=*(s.top-1); /棧不為空的時候用e做返回值，返回S的棧頂元素，并返回OK return OK; int Push(SqStack &s,char e) /運算符入棧 if (s.top-s.base >= s.stacksize) printf("運算符棧滿!n"); s.base=(char*)realloc (s

14、.base,(s.stacksize+5)*sizeof(char) ); /棧滿的時候，追加5個存儲空間 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) /運算符出棧if (s.top=s.base) /棧為空棧的時候，返回ERROR printf("運算符棧為空!n"); return ERROR; elsee=*-s.top; /棧不為空的時候用e做

15、返回值，刪除S的棧頂元素，并返回OKreturn OK; int StackTraverse(SqStack &s) /運算符棧的遍歷 char *t;t=s.base ;if (s.top=s.base) printf("運算符棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!=s.top) printf(" %c",*t); /棧不為空的時候依次取出棧內(nèi)元素 t+; return ERROR;/*數(shù)字棧部分* struct SqStackn /定義數(shù)棧 int *base; /棧底指針 int *to

16、p; /棧頂指針 int stacksize; /棧的長度;int InitStackn (SqStackn &s) /建立一個空棧S s.base=(int*)malloc(50*sizeof(int); if(!s.base)exit(OVERFLOW); /存儲分配失敗 s.top=s.base; s.stacksize=50; return OK; int GetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素 if (s.top=s.base) printf("運算數(shù)棧為空!n"); /棧為空的時候返回ERROR return ER

17、ROR; else e=*(s.top-1); /棧不為空的時候，用e作返回值，返回S的棧頂元素，并返回OK return OK; int Pushn(SqStackn &s,int e) /數(shù)棧入棧 if (s.top-s.base >=s.stacksize)printf("運算數(shù)棧滿!n"); /棧滿的時候，追加5個存儲空間 s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; /

18、插入元素e為新的棧頂元素 s.stacksize+=5;*(s.top)+=e; /棧頂指針變化return OK; int Popn(SqStackn &s,int &e) /數(shù)棧出棧if (s.top=s.base) printf(" 運算符棧為空!n"); /棧為空棧的視時候，返回ERROR return ERROR; elsee=*-s.top; /棧不空的時候，則刪除S的棧頂元素，用e返回其值，并返回OKreturn OK; int StackTraversen(SqStackn &s) /數(shù)棧遍歷 int *t;t=s.base ;if

19、(s.top=s.base) printf(" 運算數(shù)棧為空!n"); /棧為空棧的時候返回ERROR return ERROR;while(t!=s.top) printf(" %d",*t); /棧不為空的時候依次輸出 t+; return ERROR;/=/ 以下定義函數(shù)/=int Isoperator(char ch) /判斷是否為運算符，分別將運算符和數(shù)字進(jìn)入不同的棧switch (ch)case '+':case '-':case '*':case '/':case '(

20、':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 Precede(char ch1,

21、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 = '<' else p

22、 = '>' break; case '(': if (ch2 = ')')p = '=' else if (ch2 = '#') printf(" 表達(dá)式錯誤!運算符不匹配!n") ;exit(0); elsep = '<' break ; case ')': if (ch2 = '(') printf(" 表達(dá)式錯誤!運算符不匹配!n") ;exit(0); else p = '>' bre

23、ak ; case '#': if (ch2 = ')') printf(" 表達(dá)式錯誤!運算符不匹配!n") ; exit(0); else if (ch2 = '#')p = '=' elsep='<' break; return p; /=/ 以下是求值過程/=int EvaluateExpression() /參考書p53算法3.4 int a, b, temp, answer; char ch,op,e; char *str; int j = 0; SqStackn OPND;

24、/OPND為運算數(shù)字棧 SqStack OPTR; /OPTR為運算符棧 InitStack(OPTR); Push(OPTR,'#'); /,所以此棧底是'#'，因為運算符棧以'#'作為結(jié)束標(biāo)志 InitStackn(OPND); / printf("nn按任意鍵開始求解:nn"); / ch=getch(); printf("n請輸入表達(dá)式并以'#'結(jié)束:n"); str =(char*)malloc(50*sizeof(char); gets(str); ch=strj; /ch是字符

25、型的，而e是整型的整數(shù) j+; GetTop(OPTR,e); /e為棧頂元素返回值 while (ch!='#' | e!='#') if (!Isoperator(ch) /遇到數(shù)字,轉(zhuǎn)換成十進(jìn)制并計算 temp=ch-'0' /將字符轉(zhuǎn)換為十進(jìn)制數(shù) ch=strj; j+; while(!Isoperator(ch) temp=temp*10 + ch-'0' /將逐個讀入運算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù) ch=strj; j+; Pushn(OPND,temp); else if (Isoperator(ch) /判斷是否是運算

26、符,不是運算符則進(jìn)棧 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("nn 運算符棧為：n"

27、);StackTraverse(OPTR);printf("n 數(shù)棧為：n");StackTraversen(OPND);break; case '>' : Pop(OPTR,op); /彈出最上面兩個，并運算，把結(jié)果進(jìn)棧 Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf("nn 運算符棧為：n");StackTraverse(OPTR);printf("n 數(shù)棧為：n");StackTraversen(OPND); else printf("您的輸入有問題，請檢查重新輸入!"); exit(0); GetTop(OPTR,e); /取出運算符棧最上面元素是否是'#' /while GetTopn(OPND,answer); /已輸出。數(shù)字棧最上面即是最終結(jié)果 return answer;/=/ 執(zhí)行部分/=vo