大數(shù)據(jù)結(jié)構(gòu)表達(dá)式求值實(shí)驗(yàn)報(bào)告材料

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書(shū)題目：表達(dá)式求值系別：計(jì)算機(jī)科學(xué)與信息系學(xué)學(xué)生:號(hào)：指導(dǎo)教師：完成日期：目錄? 1.前? 2.概要設(shè)計(jì)2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.2算法設(shè)計(jì)2.3 ADT描述2.4功能模塊分析? 3.詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)3.2主要算法流程圖（或算法代碼）? 4軟件測(cè)試? 5總結(jié)?附錄1前在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號(hào)組成。由于不同的運(yùn)算符具有不同 的優(yōu)先級(jí)，又要考慮括號(hào)，因此，算術(shù)表達(dá)式的求值不可能?chē)?yán)格地從左到右進(jìn)行。因而在程序 設(shè)計(jì)時(shí)，借助棧實(shí)現(xiàn)。算法輸入：一個(gè)算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號(hào)組成（以字符串形式輸入）。為簡(jiǎn)化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為

2、+、-*、/,用#表示結(jié)束。算法輸出：表達(dá)式運(yùn)算結(jié)果。算法要點(diǎn)：設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列的 同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，以及相應(yīng)運(yùn)算。2.概要設(shè)計(jì)2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)任何一個(gè)表達(dá)式都是由操作符，運(yùn)算符和界限符組成的。 我們分別用順序棧來(lái)寄存表達(dá)式的操作數(shù)和運(yùn)算符。 棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。順序棧的存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置，base為棧底指針，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉?biāo)記，每當(dāng)插入新的棧頂元素時(shí)，指針top

3、增1，刪除棧頂元素時(shí)，指針 top減1。2.2算法設(shè)計(jì)為了實(shí)現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€(gè)工作棧。一個(gè)稱(chēng)為OPTR，用以寄存運(yùn)算符，另一個(gè)稱(chēng)做OPND，用以寄存操作數(shù)或運(yùn)算結(jié)果。1首先置操作數(shù)棧為空棧，表達(dá)式起始符”# ”為運(yùn)算符棧的棧底元素；2依次讀入表達(dá)式，若是操作符即進(jìn) OPND棧，若是運(yùn)算符則和 OPTR棧的棧頂運(yùn)算符 比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個(gè)表達(dá)式求值完畢 （即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為” #”)。2.3 ADT描述ADT Stack數(shù)據(jù)對(duì)象：D= ai |ai ElemSet,i=1,2,n, n仝0數(shù)據(jù)對(duì)象：R仁< aZi 1 >向 1 ,ai

4、D,i=2,，n約定an端為棧頂，ai端為棧底。基本操作：Ini tStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧 SoGetTop(S)初始條件：棧S已存在。操作結(jié)果：用P返回S的棧頂元素。Push(&S, ch)初始條件：棧S已存在。操作結(jié)果：插入元素 ch為新的棧頂元素。Pop(&S)初始條件：棧S已存在。操作結(jié)果：刪除 S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回1oPrecede(c1, c2)初始條件：c1,c2為運(yùn)算符。操作結(jié)果：判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運(yùn)算符。操作結(jié)

5、果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值。nu m( n)操作結(jié)果：返回操作數(shù)的長(zhǎng)度。EvalExpr()初始條件：輸入表達(dá)式合法。操作結(jié)果：返回表達(dá)式的最終結(jié)果。ADT Stack2.4功能模塊分析1棧的基本功能。InitStack(Stack *s)和InitStack2(Stack2 *s)分別構(gòu)造運(yùn)算符棧與構(gòu)造操作數(shù)棧, Push(Stack *s,char ch)運(yùn)算符棧插入 ch為新的棧頂元素，Push2(Stack2 *s,int ch)操作數(shù)棧插 入ch為新的棧頂元素，Pop(Stack *s)刪除運(yùn)算符棧s的棧頂元素，用p返回其值，Pop2(Stack2 *s)刪除操作數(shù)棧

6、s的棧頂元素，用p返回其值，GetTop(Stack s)用p返回運(yùn)算符棧s的棧頂元素，GetTop2(Stack2 s)用p返回操作數(shù)棧s的棧頂元素。2其它功能分析。(1) 1 n(char ch)判斷字符是否是運(yùn)算符功能，運(yùn)算符即返回1，該功能只需簡(jiǎn)單的一條語(yǔ)句即可實(shí)現(xiàn)return(ch='+'|ch='-'|ch='*'|ch=7'|ch='('|ch=')'|ch='#')。(2) Precede(char c1,char c2)判斷運(yùn)算符優(yōu)先權(quán)功能，該函數(shù)判斷運(yùn)算符 c1,c2的優(yōu)

7、先權(quán)，具體優(yōu)先關(guān)系參照表1。(3) Operate(i nt a,char op,i nt b)操作數(shù)用對(duì)應(yīng)的運(yùn)算符進(jìn)行運(yùn)算功能。運(yùn)算結(jié)果直接返回。(4) num(int n)求操作數(shù)的長(zhǎng)度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長(zhǎng)度。(5) EvalExpr()主要操作函數(shù)運(yùn)算功能。分析詳細(xì)見(jiàn)“3詳細(xì)設(shè)計(jì)3.2”。3 詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)因?yàn)楸磉_(dá)式是由操作符，運(yùn)算符和界限符組成的。如果只用一個(gè)char類(lèi)型棧，不能滿(mǎn)足2位以上的整數(shù)，所以還需要定義一個(gè)int類(lèi)型的棧用來(lái)寄存操作數(shù)。/*定義字符類(lèi)型棧*/typedef structint stacks

8、ize;char *base;char *top; Stack;/*定義整型棧 */typedef structint stacksize;int *base;int *top; Stack2;3.2主要算法流程圖(或算法代碼)1. Precede(char c1,char c2)判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。算符間的優(yōu)先關(guān)系如下：+-*/()#+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<

9、;<<<=)>>>>>>#<<<<<=表1算法代碼如下：char Precede(char c1,char c2)static char array49=>'5'>'5'<'5'<'5'<','>'15'>'15>'5'>'5'<'5'<'5'<','>

10、'15'>'1 5>'5'>'5'>'5'>'5'<','>'15'>'1 5>'5'>'5'>'5'>'5'<','>'15'>'1 5<'5'<'5'<'5'<'5'<',

11、1_ 5'!'1 -，>'5'>'5'>'5'>'5'!''>'5'>'5<'5'<'5'<'5'<'5'<','!'1 ，'=' II用一維數(shù)組存儲(chǔ)49種情況switch(cl)I* i為下面array的橫標(biāo)case '+':i=0;break;case '-'i=1;bre

12、ak;case '*'i=2;break;case Ti=3;break;case '('i=4;break;case ')'i=5;break;case #:i=6;break;switch(c2)I* j為下面array的縱標(biāo)case '+':j=O;break;case '-'j=1;break;case '*' : j=2;break;case T : j=3;break;case '(' : j=4;break;case ')' : j=5;break;ca

13、se '#' : j=6;break;return (array7*i+j); /* 返回運(yùn)算符 array7*i切 為對(duì)應(yīng)的c1,c2優(yōu)先關(guān)系*/2. int EvalExpr()主要操作函數(shù)。算法概要流程圖：利用該算法對(duì)算術(shù)表達(dá)式3*(7-2)求值操作過(guò)程如下:步驟OPTR 棧OPND 棧輸入字符主要操作1#3*(7-2)#Push(OPND,' 3')2#3*(7-2)#Push(OPTR,' *')3#*3(7-2)#Push(OPNR,'(')4#*(37-2)#Push(OPND,' 7')5#*(3

14、7-2)#Push(OPNR,'-')6#*(-3 72)#Push(OPND,' 2')7#*(-3 7 2)#Operate( ' 7' ,' -' ,' 2')8#*(3 5)#Pop(OPTR)9#*3 5#Operate( '3' ,' *' ,5')10#15#Return(GetTop2(OPND)表2算法代碼如下:int EvalExpr()主要操作函數(shù) c = *ptr+;while(c!='#'|GetTop(OPTR)!='#&#

15、39;)if(!In(c) /不是運(yùn)算符即進(jìn)棧 if(!I n(*(ptr-1) ptr=ptr-1;m=atoi(ptr);取字符串前面的數(shù)字段n=num (m);Push2(&OPND,m);ptr=ptr+ n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c)case '<': 棧頂元素優(yōu)先權(quán)底Push(&OPTR,c);c = *ptr+;break;case '=': 脫括號(hào)并接收下一字符x=Pop(&OPTR);c = *ptr+;break;case '>':/

16、退棧并將運(yùn)算結(jié)果入棧theta=Pop(&OPTR);b=Pop2(&OPND); a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b);break;4 軟件測(cè)試c：- -C = ProcraB FilesXIxcrosQf-t VisualSt udi oHyPirn ject sshujujxeguoshi± ji i.i運(yùn)行成功后界面。2.輸入正確的表達(dá)式后。contrnue昭輸入正確的董達(dá)式以/斛結(jié)尾=抄用 甦式結(jié)果% = 15 Press an_y key to3.更改表達(dá)式，輸入有 2位數(shù)的整數(shù)調(diào)試。5

17、總結(jié)這次課程設(shè)計(jì)讓我更加了解大一學(xué)到的 c和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。課 設(shè)題目要求不僅要求對(duì)課本知識(shí)有較深刻的了解， 同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的 思維和動(dòng)手能力和更加了解編程思想和編程技巧。這次課程設(shè)計(jì)讓我有一個(gè)深刻的體會(huì)， 那就是細(xì)節(jié)決定成敗，編程最需要的 是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過(guò)分，往往檢查了半天發(fā)現(xiàn)錯(cuò)誤發(fā)生在某個(gè)括號(hào)， 分號(hào), 引號(hào)，或者數(shù)據(jù)類(lèi)型上。就像我在寫(xiě) EvalExpr()函數(shù)時(shí)，忘了指針的地址符值不 用加*號(hào)，這一點(diǎn)小小的錯(cuò)誤也耽誤了我?guī)资昼?，所以說(shuō)細(xì)節(jié)很重要。程序設(shè)計(jì)時(shí)，也不要怕遇到錯(cuò)誤，在實(shí)際操作過(guò)程中犯的一些錯(cuò)誤還會(huì)有意 外的收獲，感覺(jué)課程設(shè)計(jì)很有意思。在具體操作中這學(xué)

18、期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論 知識(shí)得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上 機(jī)中應(yīng)更加注意，同時(shí)體會(huì)到 C語(yǔ)言具有的語(yǔ)句簡(jiǎn)潔，使用靈活，執(zhí)行效率高 等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù)表達(dá)式有了深刻的理解。這個(gè)程序是我們3個(gè)人完成的，同時(shí)我認(rèn)為我們的工作是一個(gè)團(tuán)隊(duì)的工作， 團(tuán)隊(duì)需要個(gè)人，個(gè)人也離不開(kāi)團(tuán)隊(duì)，必須發(fā)揚(yáng)團(tuán)結(jié)協(xié)作的精神。某個(gè)人的離群都 可能導(dǎo)致導(dǎo)致整項(xiàng)工作的失敗。實(shí)習(xí)中只有一個(gè)人知道原理是遠(yuǎn)遠(yuǎn)不夠的， 必須 讓每個(gè)人都知道，否則一個(gè)人的錯(cuò)誤，就有可能導(dǎo)致整個(gè)工作失敗。團(tuán)結(jié)協(xié)作是 我們成功的一項(xiàng)非常重要的保證。而這次課程設(shè)計(jì)也正好鍛煉我們這一點(diǎn)，這也 是非常寶貴的最后

19、，感謝老師在這次課程設(shè)計(jì)的悉心指導(dǎo)， 祝老師身體健康，工作順利。程序源代碼：#in elude <stdio.h>#in clude <stdlib.h>#in clude <stri ng.h>#defi ne NULL 0#defi ne OK 1#defi ne ERROR -1#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 20/*定義字符類(lèi)型棧 */typedef structint stacksize;char *base;char *top; Stack;/*定義整型棧*/typedef

20、structint stacksize;int *base;int *top; Stack2;/* 全局變量*/Stack OPTR;/*定義運(yùn)算符棧*/Stack2 OPND; /*定義操作數(shù)棧 */char expr255 = "" /* 存放表達(dá)式串 */char *ptr = expr;int InitStack(Stack *s) / 構(gòu)造運(yùn)算符棧s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s->base) return ERROR;s->top=s->base;s->

21、;stacksize=STACK_INIT_SIZE;return OK;int InitStack2(Stack2 *s) / 構(gòu)造操作數(shù)棧s->base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!s->base) return ERROR;s->stacksize=STACK_INIT_SIZE;s->top=s->base;return OK;int In(char ch) /判斷字符是否是運(yùn)算符，運(yùn)算符即返回1return(ch='+'|ch='-'|ch='*&

22、#39;|ch=7'|ch='('|ch=')'|ch='#');int Push(Stack *s,char ch) /運(yùn)算符棧插入 ch為新的棧頂元素*s_>top=ch;s_>top+;return 0;int Push2(Stack2 *s,int ch)/操作數(shù)棧插入 ch為新的棧頂元素*s->top=ch;s->top+;return 0;char Pop(Stack *s) /刪除運(yùn)算符棧s的棧頂元素，用p返回其值char p;s->top-;p=*s->top;return p;int

23、Pop2(Stack2 *s)/刪除操作數(shù)棧s的棧頂元素，用p返回其值int p;s->top-;p=*s->top;return p;char GetTop(Stack s)用p返回運(yùn)算符棧char p=*(s.top-1);return p;int GetTop2(Stack2 s) / 用 p 返回操作數(shù)棧int p=*(s.top-1);return p;/*判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的s的棧頂元素s的棧頂元素*/char Precede(char c1,char c2)int i=O,j=O;static char array49=555555555555555555

24、5555555555555555 55555 555? ?J，switch(cl)/* i為下面array的橫標(biāo)*/case '+' : i=O;break;case '-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;switch(c2)/* j為下面array的縱標(biāo)*/case '+&

25、#39; : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;return (array7*i+j); /* 返回運(yùn)算符 */*操作函數(shù)*/int Operate(i nt a,char op,i nt b)switch(op)case '+' : retur n (a+b);case '-' : return (a-b);case '*' : return (a*b);case '