数据结构之算术表达式求值.doc

数据结构之算术表达式求值C语言编写#include #include #include #define MAXLEN 100typedef struct char ch; int level;opt;typedef struct /定义操作栈 opt stMAXLEN; int top;Tstack;typedef struct /定义数据栈 double DMAXLEN; int top;Nstack;void Unit(Tstack *s) /初始化操作栈 s-top=-1;/Unitvoid DUnit(Nstack *s) /初始化数据栈 s-top=-1;/DUnitchar Push(Tstack *s,opt c) /入操作栈 s-top+; s-sts-top=c; return c.ch;/Pushdouble DPush(Nstack *s,double c) /入数据栈 s-top+; s-Ds-top=c; return c;/DPushopt Top(Tstack *s) /操作栈栈顶 opt error=$,-2; if(s-top=0) return s-sts-top; else return error;/Topdouble DTop(Nstack *s) /数据栈栈顶 if(s-top=0) return s-Ds-top; else return 0;/DTopopt Pop(Tstack *s) /出操作栈 opt i; opt error=$,-2; if(s-top=0) i=s-sts-top; s-sts-top.ch=0; s-top-; return i; else return error;/Popdouble DPop(Nstack *s) /出数据栈 double i; if(s-top=0) i=s-Ds-top; s-Ds-top=0; s-top-; return i; else return 0;/DPopint Empty(Tstack *s) /判断操作栈空 if(s-topsts-top.ch;/Emptyint NEmpty(Nstack *s) /判断数据栈空 if(s-topDs-top);/NEmptydouble valuate(char *e) /计算 Tstack T; Nstack N; char tmpMAXLEN=0; int i=0,leng; double d,dp; opt A=+,1; opt R=-,1; opt M=*,2; opt D=/,2; opt B=(,-1; Unit(&T); DUnit(&N); while(*e!=0) while(*e = 0 & *e = 0 & *e = 9 | *e = .) tmpi+=*e+; d=atof(tmp); DPush(&N,d); leng=strlen(tmp); for(i=0;ileng;i+) tmpi=0; i=0; switch(*e) case + : if(!Empty(&T) | Top(&T).level =A.level) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; case +: dp=DPop(&N)+DPop(&N); DPush(&N,dp); break; case -: dp=DPop(&N); dp=DPop(&N)-dp; DPush(&N,dp); break; Push(&T,A); *e+; break; case -: if(!Empty(&T) | Top(&T).level =R.level) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; case +: dp=DPop(&N)+DPop(&N); DPush(&N,dp); break; case -: dp=DPop(&N); dp=DPop(&N)-dp; DPush(&N,dp); break; Push(&T,R); *e+; break; case *: if(!Empty(&T) | Top(&T).level =M.level) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; Push(&T,M); *e+; break; case /: if(!Empty(&T) |Top(&T).level =D.level) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; Push(&T,D); *e+; break; case (: Push(&T,B); e+; break; case ): while(Top(&T).level!=-2) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; case +: dp=DPop(&N)+DPop(&N); DPush(&N,dp); break; case -: dp=DPop(&N); dp=DPop(&N)-dp; DPush(&N,dp); break; Pop(&T); e+; break; while(Empty(&T) switch(Pop(&T).ch) case * : dp=DPop(&N)*DPop(&N); DPush(&N,dp); break; case / : dp=DPop(&N); dp=DPop(&N)/dp; DPush(&N,dp); break; case +: dp=DPop(&N)+DPop(&N); DPush(&N,dp); break; case -: dp=DPop(&N); dp=DPop(&N)-dp; D