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

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

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

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

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

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

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

7、先權(quán)，具體優(yōu)先關(guān)系參照表1。(3) Operate(i nt a,char op,i nt b)操作數(shù)用對應(yīng)的運算符進行運算功能。運算結(jié)果直接返回。(4) num(int n)求操作數(shù)的長度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長度。(5) EvalExpr()主要操作函數(shù)運算功能。分析詳細(xì)見“3詳細(xì)設(shè)計3.2”。3 詳細(xì)設(shè)計3.1數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計因為表達(dá)式是由操作符，運算符和界限符組成的。如果只用一個char類型棧，不能滿足2位以上的整數(shù)，所以還需要定義一個int類型的棧用來寄存操作數(shù)。/*定義字符類型棧*/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ō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ù)組存儲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); /* 返回運算符 array7*i切 為對應(yīng)的c1,c2優(yōu)先關(guān)系*/2. int EvalExpr()主要操作函數(shù)。算法概要流程圖：利用該算法對算術(shù)表達(dá)式3*(7-2)求值操作過程如下:步驟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) /不是運算符即進棧 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 '=': 脫括號并接收下一字符x=Pop(&OPTR);c = *ptr+;break;case '>':/

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

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

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

19、，感謝老師在這次課程設(shè)計的悉心指導(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/*定義字符類型棧 */typedef structint stacksize;char *base;char *top; Stack;/*定義整型棧*/typedef

20、structint stacksize;int *base;int *top; Stack2;/* 全局變量*/Stack OPTR;/*定義運算符棧*/Stack2 OPND; /*定義操作數(shù)棧 */char expr255 = "" /* 存放表達(dá)式串 */char *ptr = expr;int InitStack(Stack *s) / 構(gòu)造運算符棧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) /判斷字符是否是運算符，運算符即返回1return(ch='+'|ch='-'|ch='*&

22、#39;|ch=7'|ch='('|ch=')'|ch='#');int Push(Stack *s,char ch) /運算符棧插入 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) /刪除運算符棧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返回運算符棧char p=*(s.top-1);return p;int GetTop2(Stack2 s) / 用 p 返回操作數(shù)棧int p=*(s.top-1);return p;/*判斷運算符優(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); /* 返回運算符 */*操作函數(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 '