算術(shù)表達式求值演示程序

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

2、容 4.1需求分析4.1.1該程序能實現(xiàn)算術(shù)四則運算表達式的求值，顯示運算過程。4.1.2輸入的形式：表達式，例如5*（3+7）#。包含的運算符只能有+、 -、*、 /、 ( ) ；4.1.3輸出的形式：運算結(jié)果，50。4.1.4程序所能達到的功能：對表達式求值并輸出。4.2總體設(shè)計4.2.1.棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：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)造一個空棧S。 GetTop(S) 初始條件：棧S已

3、存在。 操作結(jié)果：用P返回S的棧頂元素。 Push(&S，ch) 初始條件：棧S已存在。 操作結(jié)果：插入元素ch為新的棧頂元素。 Pop(&S) 初始條件：棧S已存在。 操作結(jié)果：刪除S的棧頂元素。In(ch)操作結(jié)果：判斷字符是否是運算符，運算符即返回1。 Precede(c1, c2) 初始條件：c1,c2為運算符。操作結(jié)果：判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的。Operate(a,op,b)初始條件：a,b為整數(shù)，op為運算符。操作結(jié)果：a與b進行運算，op為運算符，返回其值。num(n)操作結(jié)果：返回操作數(shù)的長度。EvalExpr()初始條件：輸入表達式合法。操作結(jié)果：返回表達式的最終結(jié)果

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

5、 , , , , , , , , !, , , , , , , , !, =; /用一維數(shù)組存儲49種情況switch(c1) /* i為下面array的橫標 */ 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的縱標 */ 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); /* 返回運算符array7*i+j為對應的c1,c2優(yōu)先關(guān)系*/ 利用該算法對算術(shù)表達式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) /不是運算符即進棧 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 :/退棧并將運算結(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(請輸入正確的表達式以#結(jié)尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化運算符棧 */ Push(&OPTR,#); /* 將#壓入運算符棧 */ InitStack2(&O

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

10、ile循環(huán)上，它從頭到尾掃描后綴表達式中的每一個數(shù)據(jù)（每個操作數(shù)或運算符均為一個數(shù)據(jù)），若后綴表達式由n個數(shù)據(jù)組成，則 此算法的時間復雜度為O(n)。此算法在運行時所占用的臨時空間主要取決于棧S的大小，顯然，它的最大深度不會超過表達式中操作數(shù)的個數(shù)，因為操作數(shù)的個 數(shù)與運算符（假定把#也看作為一個特殊運算符，即結(jié)束運算符）的個數(shù)相等，所以此算法的空間復雜度也同樣為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;/* 定義運算符棧*/Stack2 OPND; /* 定義操作數(shù)棧 */ char expr255 = ; /* 存放表達式串 */ char *ptr = expr; int InitStack(Stack *s) /

12、構(gòu)造運算符棧 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) /判斷字符是否是運算符，運算符即返回1 return(ch=+|ch=-|ch=*|ch=/|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

14、p; int Pop2(Stack2 *s)/刪除操作數(shù)棧s的棧頂元素，用p返回其值 int p;s-top-; p=*s-top; return p;char GetTop(Stack s)/用p返回運算符棧s的棧頂元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作數(shù)棧s的棧頂元素 int p=*(s.top-1); return p; /* 判斷運算符優(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的橫標 */ 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的縱標 */ 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); /* 返回運算符 */ /*操作函數(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ù)的長度 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(請輸入正確的表達式以#結(jié)尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化運算符棧 */ Push(&OPTR,#); /* 將#壓入運算符棧 */ InitStack2(&OPND); /* 初始化操作數(shù)棧 */ printf(表達式結(jié)果為:%dn, EvalExpr();return 0; 5 總結(jié)與展望這次課程設(shè)計讓我更加了解大一學到的C和這個學期學到的數(shù)據(jù)結(jié)構(gòu)。課設(shè)題目要求不僅要求對課本知識有