算術(shù)表達(dá)式求值演示程序20頁(yè)

1、數(shù) 理 學(xué) 院課程設(shè)計(jì)報(bào)告書課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 算術(shù)表達(dá)式求值演示 專業(yè)班級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)教師 2014 年 12 月1設(shè)計(jì)時(shí)間2014年12月232014年12月29日2 設(shè)計(jì)目的設(shè)計(jì)一個(gè)程序，演示算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。利用算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值。3設(shè)計(jì)任務(wù)(1)設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系；(2)在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)的識(shí)別處理，以及相應(yīng)的運(yùn)算；(3)在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)換成整數(shù)形式；(4)在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的內(nèi)容。4 設(shè)計(jì)內(nèi)

2、容 4.1需求分析4.1.1該程序能實(shí)現(xiàn)算術(shù)四則運(yùn)算表達(dá)式的求值，顯示運(yùn)算過程。4.1.2輸入的形式：表達(dá)式，例如5*（3+7）#。包含的運(yùn)算符只能有+、 -、*、 /、 ( ) ；4.1.3輸出的形式：運(yùn)算結(jié)果，50。4.1.4程序所能達(dá)到的功能：對(duì)表達(dá)式求值并輸出。4.2總體設(shè)計(jì)4.2.1.棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對(duì)象：D=ai|aiChar,i=1,2.,n,n0數(shù)據(jù)關(guān)系：R1=ai-1,ai|ai-1,aiD,i=2,3.n約定an端為棧頂，ai端為棧底4.2.2基本操作： InitStack(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧S。 GetTop(S) 初始條件：棧S已

3、存在。 操作結(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) 初始條件：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é)果

4、。ADT Stack主程序的流程：EvaluateExpression()函數(shù)實(shí)現(xiàn)了對(duì)表達(dá)式求值的功能，main()函數(shù)直接調(diào)用EvaluateExpression()對(duì)輸入的表達(dá)式求值輸出。算法流程圖4.2.3函數(shù)的調(diào)用關(guān)系圖ReturnOpOrdmainprecede InPopPushEvaluateExpression輸出Operate4.3詳細(xì)設(shè)計(jì)4.3.1. Precede(char c1,char c2) 判斷運(yùn)算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。算符間的優(yōu)先關(guān)系如下：+-*/()#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , ,

5、 , , , , , , , , !, , , , , , , , !, =; /用一維數(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;break; switch(c2) /* j為下面array的縱標(biāo) */ case + : j=0;break; case - : j=1;break; case *

6、: 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)系*/ 利用該算法對(duì)算術(shù)表達(dá)式4*(6-2)求值操作過程如下：步驟OPTR棧OPND棧輸入字符主要操作1#4*(6-2)#Push(OPND,4)2#4*(6-2)#Push(OPTR,*)3#*4(6-2)#Push(OPNR,()4#*(46-2)#Push(OPND,6)5#*(4 6-2)#Push(O

7、PNR,-)6#*(-4 62)#Push(OPND,2)7#*(-4 6 2)#Operate(6,-,2)8#*(4 4)#Pop(OPTR)9#*4 4#Operate(4,*,4)10#16#Return(GetTop2(OPND)算法偽代碼如下：int EvalExpr()/主要操作函數(shù) c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) /不是運(yùn)算符即進(jìn)棧 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的數(shù)字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr

8、+; 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.3.2主函數(shù)和其他函數(shù)的偽碼int main( ) printf(請(qǐng)輸入正確的表達(dá)式以#結(jié)尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化運(yùn)算符棧 */ Push(&OPTR,#); /* 將#壓入運(yùn)算符棧 */ InitStack2(&O

9、PND); /* 初始化操作數(shù)棧 */ printf(表達(dá)式結(jié)果為:%dn, EvalExpr();return 0; 4.3.3 函數(shù)的調(diào)用關(guān)系圖ReturnOpOrdmainprecede InPopPushEvaluateExpression輸出Operate 調(diào)用關(guān)系圖4.4測(cè)試與分析4.4.1測(cè)試4.4.2實(shí)驗(yàn)分析：表達(dá)式求值程序是一個(gè)多次調(diào)用函數(shù)的過程，且調(diào)用的過程較為復(fù)雜，調(diào)試花費(fèi)時(shí)間較多。在while循環(huán)時(shí)指針移動(dòng)容易出錯(cuò)，因此多次出現(xiàn)內(nèi)存錯(cuò)誤，對(duì)于涉及的循環(huán)的操作開始和結(jié)束條件設(shè)置很關(guān)鍵。本次實(shí)驗(yàn)熟悉了棧數(shù)據(jù)結(jié)構(gòu)的表示與實(shí)現(xiàn)方法。算法時(shí)間和空間分析：算法的運(yùn)行時(shí)間主要花在wh

10、ile循環(huán)上，它從頭到尾掃描后綴表達(dá)式中的每一個(gè)數(shù)據(jù)（每個(gè)操作數(shù)或運(yùn)算符均為一個(gè)數(shù)據(jù)），若后綴表達(dá)式由n個(gè)數(shù)據(jù)組成，則 此算法的時(shí)間復(fù)雜度為O(n)。此算法在運(yùn)行時(shí)所占用的臨時(shí)空間主要取決于棧S的大小，顯然，它的最大深度不會(huì)超過表達(dá)式中操作數(shù)的個(gè)數(shù)，因?yàn)椴僮鲾?shù)的個(gè) 數(shù)與運(yùn)算符（假定把#也看作為一個(gè)特殊運(yùn)算符，即結(jié)束運(yùn)算符）的個(gè)數(shù)相等，所以此算法的空間復(fù)雜度也同樣為O(n)。4.5 附錄源程序：#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#def

11、ine STACKINCREMENT 20 /* 定義字符類型棧 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定義整型棧 */ typedef struct int stacksize; int *base; int *top; Stack2;/* - 全局變量- */ Stack OPTR;/* 定義運(yùn)算符棧*/Stack2 OPND; /* 定義操作數(shù)棧 */ char expr255 = ; /* 存放表達(dá)式串 */ char *ptr = expr; int InitStack(Stack *s) /

12、構(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;return 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

13、; int 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為新的棧頂元素 *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

14、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的棧頂元素 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) int i=0,j=0; static char array49=, , , ,

15、 , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; 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;break; switch(c2) /* j為下面array的縱標(biāo) */ case + : j=0;break;

16、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(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); r

17、eturn 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);/取字符串前面的數(shù)字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Pre

18、cede(GetTop(OPTR),c) case : theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; return GetTop2(OPND); int main( ) printf(請(qǐng)輸入正確的表達(dá)式以#結(jié)尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化運(yùn)算符棧 */ Push(&OPTR,#); /* 將#壓入運(yùn)算符棧 */ InitStack2(&OPND); /* 初始化操作數(shù)棧 */ printf(表達(dá)式結(jié)果為:%dn, EvalExpr();return 0; 5 總結(jié)與展望這次課程設(shè)計(jì)讓我更加了解大一學(xué)到的C和這個(gè)學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu)。課設(shè)題目要求不僅要求對(duì)課本知識(shí)有