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

1、 1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課 程 設(shè) 計(jì) 報(bào) 告 書(shū)題 目： 數(shù)據(jù)結(jié)構(gòu)蘇算術(shù)表達(dá)式求值 系 別： 數(shù)學(xué)院信息系統(tǒng)與信息管理學(xué) 號(hào)： 1201324095 學(xué)生姓名： 梅影 指導(dǎo)教師： 李文強(qiáng) 完成日期： 2013-10-19 2目錄目錄1.概要設(shè)計(jì)2.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2.2 算法設(shè)計(jì)2.3 adt 描述2.4 功能模塊分析2.詳細(xì)設(shè)計(jì)3.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)3.2 主要算法流程圖（或算法代碼）3.軟件測(cè)試4.附 錄 31概要設(shè)計(jì)概要設(shè)計(jì)(1) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)任何一個(gè)表達(dá)式都是由操作符,運(yùn)算符和界限符組成地.我們分別用順序棧來(lái)寄存表達(dá)式地操作數(shù)和運(yùn)算符.棧是限定于緊僅在表尾進(jìn)行插入或刪除操作地線性表.順

2、序棧地存儲(chǔ)結(jié)構(gòu)是利用一組連續(xù)地存儲(chǔ)單元依次存放自棧底到棧頂?shù)財(cái)?shù)據(jù)元素,同時(shí)附設(shè)指針 top 指示棧頂元素在順序棧中地位置,base 為棧底指針,在順序棧中,它始終指向棧底,即 top=base可作為棧空地標(biāo)記,每當(dāng)插入新地棧頂元素時(shí),指針 top 增 1,刪除棧頂元素時(shí),指針 top 減 1.(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)先

3、權(quán)后作相應(yīng)地操作,直至整個(gè)表達(dá)式求值完畢（即 optr 棧地棧頂元素和當(dāng)前讀入地字符均為”#” ）.(3) adt 描述adt stack數(shù)據(jù)對(duì)象：d= |elemset,i=1,2,n, n0iaia數(shù)據(jù)對(duì)象：r1=|,i=2,n1,iiaa1iadai約定端為棧頂,端為棧底.naia基本操作： initstack(&s) 操作結(jié)果：構(gòu)造一個(gè)空棧 s. gettop(s) 初始條件：棧 s 已存在. 4 操作結(jié)果：用 p 返回 s 地棧頂元素. push(&s,ch) 初始條件：棧 s 已存在. 操作結(jié)果：插入元素 ch 為新地棧頂元素. pop(&s) 初始條件：棧

4、 s 已存在. 操作結(jié)果：刪除 s 地棧頂元素.in(ch)操作結(jié)果：判斷字符是否是運(yùn)算符,運(yùn)算符即返回 1. precede(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é)果：a 與 b 進(jìn)行運(yùn)算,op 為運(yùn)算符,返回其值.num(n)操作結(jié)果：返回操作數(shù)地長(zhǎng)度.evalexpr()初始條件：輸入表達(dá)式合法.操作結(jié)果：返回表達(dá)式地最終結(jié)果.adt stack(4) 功能模塊分析1.棧地基本功能.initstack(stack *s) 和 initstack2(stack

5、2 *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ù)棧 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,該

6、功能只需簡(jiǎn)單地一條語(yǔ)句即可實(shí)現(xiàn)return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|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(int a,char op,int b)操作數(shù)用對(duì)應(yīng)地運(yùn)算符進(jìn)行運(yùn)算功能.運(yùn)算結(jié)果 5直接返回.(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”

7、.3 3詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì)(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 struct int stacksize; char *base; char *top; stack;/* 定義整型棧 */ typedef struct int stacksize; int *base; int *top; stack2;(2) 主要算法流程圖（或算法代碼）1. precede(char c1,char c2) 判斷運(yùn)算符優(yōu)先權(quán),

8、返回優(yōu)先權(quán)高地.算符間地優(yōu)先關(guān)系如下：+-*/()#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一維數(shù)組存儲(chǔ) 49 種情況switch(c1) /* i 為下面 array 地橫標(biāo) */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;

9、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)算符 array7*i+j為對(duì)應(yīng)地 c1,c2 優(yōu)先關(guān)系*/ 2. int evalexpr()主要操作函數(shù).算法概要流程圖： 7利用該算法對(duì)算術(shù)表達(dá)式 3*(7-2)求值操作過(guò)程如下：

10、步驟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 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!=#

11、|gettop(optr)!=#) if(!in(c) /不是運(yùn)算符即進(jìn)棧 if(!in(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面地?cái)?shù)字段 8n=num(m); push2(&opnd,m); ptr=ptr+n;c=*ptr+; else switch(precede(gettop(optr),c) case :/退棧并將運(yùn)算結(jié)果入棧 theta=pop(&optr); b=pop2(&opnd); a=pop2(&opnd); push2(&opnd,operate(a,theta,b);break; 4 4軟件測(cè)

12、試軟件測(cè)試1.運(yùn)行成功后界面. 92.輸入正確地表達(dá)式后.3.更改表達(dá)式,輸入有 2 位數(shù)地整數(shù)調(diào)試. 10附附 錄錄程序源代碼：#include #include #include #define null 0 #define ok 1#define error -1 #define stack_init_size 100#define stackincrement 20 /* 定義字符類(lèi)型棧 */ typedef struct int stacksize; char *base; char *top; stack;/* 定義整型棧 */ typedef struct int stacksi

13、ze; int *base; int *top; stack2; 11/* - 全局變量- */ 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_init_size;ret

14、urn ok; int initstack2(stack2 *s) /構(gòu)造操作數(shù)棧 s-base=(int *)malloc(stack_init_size*sizeof(int); if(!s-base) return error; s-stacksize=stack_init_size; s-top=s-base; return ok; 12int in(char ch) /判斷字符是否是運(yùn)算符,運(yùn)算符即返回 1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int push(stack *s,char ch) /運(yùn)算符棧插入 ch 為新地棧頂元素

15、 *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; 13return p; int pop2(stack2 *s)/刪除操作數(shù)棧 s 地棧頂元素,用 p 返回其值 int p;s-top-; p=*s-top; return p;char gettop(stack s)/用 p 返回運(yùn)算符棧 s 地棧頂

16、元素 char p=*(s.top-1); return p; int gettop2(stack2 s) /用 p 返回操作數(shù)棧 s 地棧頂元素 int p=*(s.top-1); return p; /* 判斷運(yùn)算符優(yōu)先權(quán),返回優(yōu)先權(quán)高地 */ char precede(char c1,char c2) 14 int i=0,j=0; static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i 為下面 ar

17、ray 地橫標(biāo) */ case + : i=0;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; 15switch(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;b

18、reak; case # : j=6;break; return (array7*i+j); /* 返回運(yùn)算符 */ /*操作函數(shù) */ int operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); 16 return 0; int num(int n)/返回操作數(shù)地長(zhǎng)度 char p10;itoa(n,p,10);/把整型轉(zhuǎn)換成字符串型n=strlen(p);return n;int evalexpr()/主要操作函數(shù) char c,theta,x; int n,m;int a,b; c = *ptr+; while(c!=#|gettop(optr)!=#) if(!in(c) if(!in(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面地?cái)?shù)字段n=num(m); push2(&opnd,m); 17ptr=ptr+n;c=*ptr+; else switch(precede(gettop(optr),c) case : theta=pop(&optr); b=pop2(&opnd);