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

1、.XXXXXX大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)老師：,.目 錄一 算術(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á)式起始、結(jié)束符“#”，如： #（7+15）* （23-28/4 ）#。引入表達(dá)式起始、結(jié)束符是為了方便。編程利用“算符優(yōu)先法”求算術(shù)表達(dá)式的值。二、程序的主要功

2、能（ 1） 從鍵盤讀入一個(gè)合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。（ 2） 顯示輸入序列和棧的變化過(guò)程。三、程序運(yùn)行平臺(tái)Visual C+6.0 版本四、 數(shù)據(jù)結(jié)構(gòu)本程序的數(shù)據(jù)結(jié)構(gòu)為棧。（1）運(yùn)算符棧部分：struct SqStack/ 定義棧char*base;/ 棧底指針char*top;/ 棧頂指針intstacksize;/ 棧的長(zhǎng)度;int InitStack (SqStack &s)/建立一個(gè)空棧Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(0);s.top=s.base;s.stacksize=50;return OK

3、;charGetTop(SqStack s,char &e)/ 運(yùn)算符取棧頂元素if (s.top=s.base)/棧為空的時(shí)候返回ERRORprintf(" 運(yùn)算符棧為空 !n");return ERROR;elsee=*(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*)real

4、loc (s.base,(s.stacksize+5)*sizeof(char) );/ 棧滿的時(shí)候，追加 5 個(gè)存儲(chǔ)空間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í)候，返回ERRORprintf(" 運(yùn)算符棧為空 !n");return ERROR;elsee=*-s.top; /棧不為空的時(shí)候

5、用 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;（2）數(shù)字棧部分：struct SqStackn /定義數(shù)棧int*base;/棧底指針int

6、*top;/ 棧頂指針intstacksize;/棧的長(zhǎng)度;int InitStackn (SqStackn &s)/建立一個(gè)空棧Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);/存儲(chǔ)分配失敗s.top=s.base;s.stacksize=50;return OK;intGetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素if (s.top=s.base)printf(" 運(yùn)算數(shù)棧為空 !n"); / 棧為空的時(shí)候返回ERRORreturn ERROR;elsee

7、=*(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í)候，追加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; / 插入元素

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

9、op=s.base)printf(" 運(yùn)算數(shù)棧為空 !n"); / 棧為空棧的時(shí)候返回 ERROR return ERROR;while(t!=s.top)printf(" %d",*t); / 棧不為空的時(shí)候依次輸出t+;return ERROR;五、算法及時(shí)間復(fù)雜度1、算法：建立兩個(gè)不同類型的空棧，先把一個(gè) #壓入運(yùn)算符棧。輸入一個(gè)算術(shù)表達(dá)式的字符串（以 結(jié)#束），從第一個(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)算結(jié)束

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

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

12、efine STACK_INIT_SIZE 100/#define STACKINCREMENT 10/=/以下定義兩種棧，分別存放運(yùn)算符和數(shù)字/=/* 運(yùn)算符棧部分 *struct SqStack/定義棧char*base;/棧底指針char*top;/棧頂指針intstacksize;/棧的長(zhǎng)度;int InitStack (SqStack &s)/建立一個(gè)空棧 Sif (!(s.base = (char *)malloc(50 * sizeof(char),.exit(0);s.top=s.base;s.stacksize=50;return OK;charGetTop(SqSt

13、ack s,char &e)/運(yùn)算符取棧頂元素if (s.top=s.base)/棧為空的時(shí)候返回ERRORprintf(" 運(yùn)算符棧為空 !n");return ERROR;elsee=*(s.top-1);/棧不為空的時(shí)候用e 做返回值，返回S 的棧頂元素，并返回OKreturn 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.stac

14、ksize+5)*sizeof(char) );/棧滿的時(shí)候，追加 5 個(gè)存儲(chǔ)空間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;,.elsee=*-s.top;/棧不為空的時(shí)候用e 做返回值，刪除S 的棧頂元

15、素，并返回 OKreturn 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;/* 數(shù)字棧部分 *struct SqStackn / 定義數(shù)棧int*base;/棧底指針int*top;/棧頂指針intstack

16、size;/棧的長(zhǎng)度;int InitStackn (SqStackn &s)/建立一個(gè)空棧 Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW);/存儲(chǔ)分配失敗s.top=s.base;s.stacksize=50;return OK;,.intGetTopn(SqStackn s,int &e) /數(shù)棧取棧頂元素if (s.top=s.base)printf(" 運(yùn)算數(shù)棧為空 !n"); / 棧為空的時(shí)候返回 ERROR return ERROR;elsee=*(s.top-1); /

17、 棧不為空的時(shí)候，用e 作返回值，返回S 的棧頂元素，并返回 OKreturn OK;int Pushn(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.stac

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

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

20、39;:case '#':return 1;default:return 0;int Operate(int a, char op, int b) /運(yùn)算操作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, char ch2) /運(yùn)算符優(yōu)先級(jí)

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

22、9;(':if (ch2 = ')')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);elsep = '>'break ;case '#':if (ch2 = ')&

23、#39;)printf(" 表達(dá)式錯(cuò)誤 !運(yùn)算符不匹配 !n") ;exit(0);else if (ch2 = '#')p = '='elsep='<'break;return p;/=/以下是求值過(guò)程/=int EvaluateExpression()/ 參考書 p53 算法 3.4int a, b, temp, answer;char ch,op,e;char *str;intj = 0;SqStackn OPND;/OPND 為運(yùn)算數(shù)字棧SqStack OPTR;/OPTR 為運(yùn)算符棧InitStack(OPTR

24、);Push(OPTR,'#');/,所以此棧底是 '#'，因?yàn)檫\(yùn)算符棧以 '#'作為結(jié)束標(biāo)志InitStackn(OPND);/ printf("nn 按任意鍵開始求解 :nn");/ ch=getch();,.printf("n 請(qǐng)輸入表達(dá)式并以 '#'結(jié)束 :n");str =(char*)malloc(50*sizeof(char);gets(str);ch=strj;/ch 是字符型的，而 e 是整型的整數(shù)j+;GetTop(OPTR,e);/e 為棧頂元素返回值while (ch

25、!='#' | e!='#')if (!Isoperator(ch)/遇到數(shù)字 ,轉(zhuǎn)換成十進(jìn)制并計(jì)算temp=ch-'0'/將字符轉(zhuǎn)換為十進(jìn)制數(shù)ch=strj;j+;while(!Isoperator(ch)temp=temp*10 + ch-'0'/將逐個(gè)讀入運(yùn)算數(shù)的各位轉(zhuǎn)化為十進(jìn)制數(shù)ch=strj;j+;Pushn(OPND,temp);else if (Isoperator(ch)/判斷是否是運(yùn)算符 ,不是運(yùn)算符則進(jìn)棧switch (Precede(e,ch)case '<' : Push(OPTR,c

26、h);/ 棧頂元素優(yōu)先權(quán)低ch = strj+;printf("nn運(yùn)算符棧為： n");/輸出棧，顯示棧的變化StackTraverse(OPTR);printf("n 運(yùn)算數(shù)棧為： n");StackTraversen(OPND);break;case '=' : Pop(OPTR,op); / 脫括號(hào)并接收下一字符 ch = strj+ ;printf("nn運(yùn)算符棧為： n");StackTraverse(OPTR);printf("n 數(shù)棧為： n");StackTraversen(OPN

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