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

1、北京理工大學(xué)珠海學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目算術(shù)表達(dá)式求值所在學(xué)院:專業(yè)班級:學(xué)生姓名:指導(dǎo)教師:2010年05月26日目錄1 前 言12 概要設(shè)計(jì) 12.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)12.2 算法設(shè)計(jì)12.3 ADT 描述22.4 功能模塊分析 23 .詳細(xì)設(shè)計(jì) 33.1數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計(jì) 33.2主要算法流程圖（或算法偽代碼） 34 .軟件測試 65.心得體會 8參考文獻(xiàn) 8附錄 8北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院1 .前言在計(jì)算機(jī)中，算術(shù)表達(dá)式由常量、變量、運(yùn)算符和括號組成。由于不同的運(yùn)算符具有不同的優(yōu)先級， 又要考慮括號，因此，算術(shù)表達(dá)式的求值不可能嚴(yán)格地從左到右進(jìn)行。因而在程序設(shè)計(jì)時(shí)，借助棧實(shí)

2、現(xiàn)。算法輸入：一個算術(shù)表達(dá)式，由常量、變量、運(yùn)算符和括號組成（以字符串形式輸入）。為簡化，規(guī)定操作數(shù)只能為正整數(shù)，操作符為 +、-*、/,用#表示結(jié)束。算法輸出：表達(dá)式運(yùn)算結(jié)果。算法要點(diǎn)：設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識別處理，以及相應(yīng)運(yùn)算。2. 概要設(shè)計(jì)2.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)任何一個表達(dá)式都是由操作符，運(yùn)算符和界限符組成的。我們分別用順序棧來寄存表達(dá)式的操作數(shù)和運(yùn)算符。棧是限定于緊僅在表尾進(jìn)行插入或刪除操作的線性表。順序棧的存儲結(jié)構(gòu)是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置

3、，base為棧底指針，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉?biāo)記，每當(dāng)插入新的棧頂元素時(shí)，指針top增1,刪除棧頂元素時(shí)，指針 top減1。2.2算法設(shè)計(jì)為了實(shí)現(xiàn)算符優(yōu)先算法?？梢允褂脙蓚€工作棧。一個稱為OPTR，用以寄存運(yùn)算符，另一個稱做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)的操作，直至整個表達(dá)式求值完畢（即 OPTR棧的棧頂元素和當(dāng)前讀入的字符均為”#”）。2.3 ADT描述ADT Stack數(shù)據(jù)對象

4、：D= ai |ai ElemSet,i=1,2, , , n, n 仝 0數(shù)據(jù)對象：R仁< ai ,ai J>|aiJ,a D ,i=2, , n約定an端為棧頂，ai端為棧底。基本操作：Ini 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é)果：判斷字符是否是運(yùn)算符，運(yùn)算符即返回1。Precede(c1, c2)初始

5、條件：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é)果：a與b進(jìn)行運(yùn)算，op為運(yùn)算符，返回其值。nu m( n)操作結(jié)果：返回操作數(shù)的長度。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,charch)運(yùn)算符棧插入 ch為新的棧頂元素，Push2(Stack2 *s,int ch)

6、操作數(shù)棧插入 ch為新的棧頂元素，Pop(Stack *s)刪除運(yùn)算符棧s的棧頂元素，用p返回其值，Pop2(Stack2 *s)刪除操作數(shù)棧s的棧頂元素，用p返回其值，GetTop(Stack s)用p返回運(yùn)算符棧s的棧頂元素，GetTop2(Stack2 s)用p返回操作數(shù)棧 s的棧頂元素。2其它功能分析。(1) In (char ch)判斷字符是否是運(yùn)算符功能，運(yùn)算符即返回1,該功能只需簡單的一條語句即可實(shí) 現(xiàn)，return(ch='+'|ch='-'|ch='*'|ch=7'|ch='('|ch=')

7、9;|ch='#')。(2) Precede(char c1,char c2)判斷運(yùn)算符優(yōu)先權(quán)功能，該函數(shù)判斷運(yùn)算符c1,c2的優(yōu)先權(quán)，具體優(yōu)先關(guān)系參照表1。(3) Operate。nt a,char op,int b)操作數(shù)用對應(yīng)的運(yùn)算符進(jìn)行運(yùn)算功能。運(yùn)算結(jié)果直接返回。(4) num(int n)求操作數(shù)的長度功能，需要用itoa函數(shù)把int型轉(zhuǎn)換成字符串型，strlen函數(shù)可求字符長度。(5) EvalExpr()主要操作函數(shù)運(yùn)算功能。分析詳細(xì)見“3詳細(xì)設(shè)計(jì)，3.2”。3. 詳細(xì)設(shè)計(jì)char類型棧，不能滿足2位以3.1數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計(jì)因?yàn)楸磉_(dá)式是由操作符，運(yùn)算符和界限符組成

8、的。如果只用一個上的整數(shù)，所以還需要定義一個int類型的棧用來寄存操作數(shù)。/*定義字符類型棧*/typedef structint stacksize;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、gt;>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=表1算法偽代碼如下：char Precede(char c1,char c2)static char array49=>'5'>'5'<'5'<'5'<','>'1 !'>'15>

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

11、'1 5<'5'<'5'<'5'<'5'<',1 _ !'!'1 ，>'5'>'5'>'5'>'5'!''>'5'>'5<'5'<'5'<'5'<'5'<','!'1 ，'=' /用一維數(shù)組存儲49種

12、情況switch(cl)/* i為下面array的橫標(biāo)*/case '+' : i=O;break;case '-' : i=1;break;case '*' : i=2;break;case T : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;switch(c2)/* j為下面array的縱標(biāo)*/case '+' : j=0;break;case '-' : j=1

13、;break;case '*' : j=2;break;case T : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;return (array7*i+j); /*返回運(yùn)算符 array7*i+j為對應(yīng)的 c1,c2 優(yōu)先關(guān)系 */2. int EvalExpr()主要操作函數(shù)。算法概要流程圖:char匚三表達(dá)式首字符a第7頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院case 4 進(jìn)操作符棧c =中屮+;case心進(jìn)操作符棧尸*ptr

14、+；進(jìn)操作數(shù)棧C-*第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院IretumGetTop2(OPND) 操作數(shù)棧頭2個數(shù)進(jìn)行 運(yùn)算4第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院利用該算法對算術(shù)表達(dá)式3*(7-2)求值操作過程如下:步驟OPTR 棧OPND 棧輸入字符主要操作1#3*(7-2)#PushQPND,''2#3*(7-2)#Push(OPTR,''3#*3(7-2)#Push(OPNR,'(')4#*(37-2)#PushQPND,''5#*(3 7-2)#Push(OPNR,

15、'-')6#*(-3 72)#PushQPND,''7#*(-3 7 2)#Operate( 7','-',''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)!='#')if(!In(c) /不是運(yùn)算符即進(jìn)棧 if(!I n(*(ptr-

16、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 '>':/退棧并將運(yùn)算結(jié)果入棧theta=Pop(&OPTR);b=Pop

17、2(&OPND); a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b);break;4. 軟件測試運(yùn)行成功后界面。第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院第9頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院2.輸入正確的表達(dá)式后。S3農(nóng)惠鑼麴譬式嘆”結(jié)尾Press any key to continue3.更改表達(dá)式，輸入有 2位數(shù)的整數(shù)調(diào)試。第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院5. 心得體會這次課程設(shè)計(jì)讓我更加了解大一學(xué)到的 C和這個學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。課設(shè)題目要 求不僅要求對課本知識有較深刻的了解，同時(shí)要求程序設(shè)計(jì)者有較強(qiáng)的

18、思維和動手能力和 更加了解編程思想和編程技巧。這次課程設(shè)計(jì)讓我有一個深刻的體會，那就是細(xì)節(jié)決定成敗，編程最需要的是嚴(yán)謹(jǐn)，如何的嚴(yán)謹(jǐn)都不過分，往往檢查了半天發(fā)現(xiàn)錯誤發(fā)生在某個括號，分號，引號，或者數(shù)據(jù)類型上。就像我在寫 EvalExpr()函數(shù)時(shí)，忘了指針的地址符值不用加*號，這一點(diǎn)小小的 錯誤也耽誤了我?guī)资昼姡哉f細(xì)節(jié)很重要。程序設(shè)計(jì)時(shí)，也不要怕遇到錯誤，在實(shí)際操作過程中犯的一些錯誤還會有意外的收獲，感覺課程設(shè)計(jì)很有意思。在具體操作中這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知識得到鞏固，達(dá)到課程設(shè)計(jì)的基本目的，也發(fā)現(xiàn)自己的不足之出，在以后的上機(jī)中應(yīng)更加注意，同時(shí)體會到 C語言具有的語句簡潔，使用靈活，執(zhí)

19、行效率高等特點(diǎn)。發(fā)現(xiàn)上機(jī)的重要作用，特別算術(shù) 表達(dá)式有了深刻的理解。這個程序是我們3個人完成的，同時(shí)我認(rèn)為我們的工作是一個團(tuán)隊(duì)的工作，團(tuán)隊(duì)需要個人，個人也離不開團(tuán)隊(duì)，必須發(fā)揚(yáng)團(tuán)結(jié)協(xié)作的精神。某個人的離群都可能導(dǎo)致導(dǎo)致整項(xiàng) 工作的失敗。實(shí)習(xí)中只有一個人知道原理是遠(yuǎn)遠(yuǎn)不夠的， 必須讓每個人都知道，否則一個 人的錯誤，就有可能導(dǎo)致整個工作失敗。團(tuán)結(jié)協(xié)作是我們成功的一項(xiàng)非常重要的保證。而 這次課程設(shè)計(jì)也正好鍛煉我們這一點(diǎn)，這也是非常寶貴的最后，感謝老師在這次課程設(shè)計(jì)的悉心指導(dǎo)，祝老師身體健康，工作順利。參考文獻(xiàn)：1數(shù)據(jù)結(jié)構(gòu)(C語言版)嚴(yán)蔚敏 清華大學(xué)出版社1. C語言程序設(shè)計(jì) 丁峻嶺中國鐵道出版社2.

20、 C程序設(shè)計(jì)譚浩強(qiáng)清華大學(xué)出版社附錄程序源代碼:#in elude <stdio.h>#in elude <stdlib.h>#in elude <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 structint stac

21、ksize;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->stacksize=STACK

22、_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 ln(char ch) /判斷字符是否是運(yùn)算符，運(yùn)算符即返回1return(ch='+'|ch='-'|ch='*'|ch=7'|c

23、h='('|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 Pop2(Stack2 *s)/

24、刪除操作數(shù)棧s的棧頂元素，用p返回其值int p;第15頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院第#頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院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)高的char Precede(char c1,char c2)int i=O,j=O;static char array49=

25、9;>', '>', '<', '<', '<', '>', '>','>', '>', '<', '<', '<', '>', '>','>', '>', '>', '>', '<', &

26、#39;>', '>',s的棧頂元素s的棧頂元素*/第17頁北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院5555555555555 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 &

27、#39;#' : i=6;break;switch(c2)/* j為下面array的縱標(biāo)*/case '+' : 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 '/' : return (a/b);return 0;int num(int n)返回操作數(shù)的長