數(shù)據(jù)結(jié)構(gòu)算術(shù)表達式求值實驗報告

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

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

3、，base為棧底指針，在順序棧中，它始終指向棧底，即top=base可作為?？盏臉擞?，每當插入新的棧頂元素時，指針top增1,刪除棧頂元素時，指針 top減1。2.2算法設(shè)計為了實現(xiàn)算符優(yōu)先算法。可以使用兩個工作棧。一個稱為OPTR，用以寄存運算符，另一個稱做OPND，用以寄存操作數(shù)或運算結(jié)果。1. 首先置操作數(shù)棧為空棧，表達式起始符”# ”為運算符棧的棧底元素；2. 依次讀入表達式，若是操作符即進OPND棧，若是運算符則和 OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)的操作，直至整個表達式求值完畢（即 OPTR棧的棧頂元素和當前讀入的字符均為”#”）。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端為棧底?；静僮鳎篒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é)果：判斷字符是否是運算符，運算符即返回1。Precede(c1, c2)初始

5、條件：c1,c2為運算符。操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運算符。操作結(jié)果：a與b進行運算，op為運算符，返回其值。nu m( n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達式合法。操作結(jié)果：返回表達式的最終結(jié)果。ADT Stack2.4功能模塊分析1棧的基本功能。InitStack(Stack *s)和 InitStack2(Stack2 *s)分別構(gòu)造運算符棧與構(gòu)造操作數(shù)棧，Push(Stack *s,charch)運算符棧插入 ch為新的棧頂元素，Push2(Stack2 *s,int ch)

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

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

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ō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的橫標*/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的縱標*/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); /*返回運算符 array7*i+j為對應(yīng)的 c1,c2 優(yōu)先關(guān)系 */2. int EvalExpr()主要操作函數(shù)。算法概要流程圖:char匚三表達式首字符a第7頁北京理工大學珠海學院計算機科學技術(shù)學院case 4 進操作符棧c =中屮+;case心進操作符棧尸*ptr

14、+；進操作數(shù)棧C-*第#頁北京理工大學珠海學院計算機科學技術(shù)學院IretumGetTop2(OPND) 操作數(shù)棧頭2個數(shù)進行 運算4第#頁北京理工大學珠海學院計算機科學技術(shù)學院第#頁北京理工大學珠海學院計算機科學技術(shù)學院利用該算法對算術(shù)表達式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) /不是運算符即進棧 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 '>':/退棧并將運算結(jié)果入棧theta=Pop(&OPTR);b=Pop

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

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

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

20、 C程序設(shè)計譚浩強清華大學出版社附錄程序源代碼:#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;/*定義運算符棧*/Stack2 OPND; /*定義操作數(shù)棧 */char expr255 = "" /*存放表達式串*/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->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) /判斷字符是否是運算符，運算符即返回1return(ch='+'|ch='-'|ch='*'|ch=7'|c

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

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

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

26、#39;>', '>',s的棧頂元素s的棧頂元素*/第17頁北京理工大學珠海學院計算機科學技術(shù)學院5555555555555 55555 555?J，switch(cl)/* i為下面array的橫標*/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的縱標*/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); /*返回運算符*/*操作函數(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ù)的長