数据结构表达式求值.docx

数据结构表达式求值 #includeusing namespace std;#define TRUE 1#define FALSE 0#define Stack_Size 20#define Stack_Float 30/*建立字符栈*/ typedef struct char elemStack_Size;/存储定义 int top;Stack_char; void InitStack(Stack_char*S)/初始化顺序栈 S-top=-1; int Push(Stack_char *S,char x)/进栈 if(S-top=Stack_Size-1) return (FALSE); S-top+; S-elemS-top=x; return (TRUE);int Pop(Stack_char*S,char*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_char*S,char*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); char GetTop(Stack_char S) char x; GetTop(&S,&x); return x;/建立数字栈 typedef struct/建立 float elemStack_Float; int top;Stack_float;void InitStack(Stack_float*S)/初始化 S-top=-1;int Push(Stack_float*S,float e) /进栈 if(S-top=Stack_Float-1) return(FALSE); else S-top+; S-elemS-top=e; return(TRUE); int Pop(Stack_float*S,float*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_float*S,float*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); float GetTop(Stack_float S) float x; GetTop(&S,&x); return x; bool In(char ch)/判断字符 if(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#) return (TRUE); else return(FALSE); float GetNumber(char*ch)/转化数码 return (*ch-48);float Execute(float a,char op,float b) switch(op) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:return(a/b);break; default:cout); else return (); if(x=*|x=/) if(ch=() return(); if(x=() if(ch=) return(=); else return(); if(x=#) if(ch=#) return(=); else return();float ExpEvaluation() float n,v,a,b;char op; Stack_char OPTR; Stack_float OVS; InitStack(&OPTR); InitStack(&OVS); Push(&OPTR,#); cout请输入一个表达式串（以#结束）endl; char ch; ch=getchar(); while(ch!=#|GetTop(OPTR)!=#) if(!In(ch) n=GetNumber(&ch); Push(&OVS,n); ch=getchar(); else switch(Compare(GetTop(OPTR),ch) case: Pop(&OPTR,&op); Pop(&OVS,&b); Pop(&OVS,&a); v=Execute(a,op,b); Push(&OVS,v); break; case=: Pop(&OPTR,&op); ch=getchar(); break; v=GetTop(OVS); return(v); int main() coutExpEvaluation()endl; system(pause); return 0; 完善版#includeusing namespace std;#define TRUE 1#define FALSE 0#define Stack_Size 20#define Stack_Float 30/*建立字符栈*/ typedef struct char elemStack_Size;/存储定义 int top;Stack_char; void InitStack(Stack_char*S)/初始化顺序栈 S-top=-1; int Push(Stack_char *S,char x)/进栈 if(S-top=Stack_Size-1) return (FALSE); S-top+; S-elemS-top=x; return (TRUE);int Pop(Stack_char*S,char*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_char*S,char*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); char GetTop(Stack_char S) char x; GetTop(&S,&x); return x;void ClearStack(Stack_char*S)/清空栈 if(S-top!=-1) S-top=-1;/*建立数字栈*/ typedef struct/建立 float elemStack_Float; int top;Stack_float;void InitStack(Stack_float*S)/初始化 S-top=-1;int Push(Stack_float*S,float e) /进栈 if(S-top=Stack_Float-1) return(FALSE); else S-top+; S-elemS-top=e; return(TRUE); int Pop(Stack_float*S,float*x)/出栈 if(S-top=-1) return(FALSE); else *x=S-elemS-top; S-top-; return(TRUE); int GetTop(Stack_float*S,float*x)/ 取栈顶 if(S-top=-1) return(FALSE); else *x=S-elemS-top; return(TRUE); float GetTop(Stack_float S) float x; GetTop(&S,&x); return x;void ClearStack(Stack_float*S)/清空栈 if(S-top!=-1) S-top=-1;/*一些函数*/ char a7= +,-,*,/,(,), #; char p77= /优先权集合 , , , , , ,=48&ch=57) return(TRUE); else return(FALSE); bool Inc(char ch)/判断字符 if(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#) return (TRUE); else return(FALSE); float GetNumber(char*ch)/转化数码 return (*ch-48);float Execute(float a,char op,float b) switch(op) case+:return(a+b);break; case-:return(a-b);break; case*:return(a*b);break; case/:return(a/b);break; default:cout不能运算;break; char Compare(char x,char ch) /char x; / GetTop(&S,&x); int i,j,k; for(i=0;i7;i+) if(x=ai) j=i; if(ch=ai) k=i; return pjk;Stack_char OPTR;Stack_float OVS;/InitStack(&OPTR);/InitStack(&OVS);void ExpEvaluation() InitStack(&OPTR); InitStack(&OVS); Push(&OPTR,#); cout请输入一个表达式串（以#结束）endl; char ch; int w=0,q=0,y=0,z=0,m=0;float n=0,v,a,b;char op; ch=getchar(); if(!Ins(ch) if(ch=() z=1; else if(ch=-) w=1;ch=getchar();/记录输入负号 else cout输入错误，请重新a; fflush(stdin); /清理缓存 ClearStack(&OPTR); ExpEvaluation(); exit(1); /else while(ch!=#|GetTop(OPTR)!=#) if(Ins(ch) n=n*10+GetNumber(&ch); q=1;/记录输入数字 y=0;/记录输入字符 ch=getchar(); /coutn值nendl; /system(pause); if(Inc(ch) if(ch=() z=1; if(w=1) / coutzzendl; if(q=0) if(z=1) Push(&OPTR,ch); /cout+GetTop(OPTR)endl; z=0; m=2;/记录负的左括号 ch=getchar(); continue; else if(ch=-) w=0;ch=getchar(); else cout输入错误，请重新b; fflush(stdin); /清理缓存 ClearStack(&OPTR); ExpEvaluation(); exit(1); else coutwwendl;n=-n;w=0; if(m=2)n=-n;m-;coutmmendl; /else if(q=1) Push(&OVS,n); cout栈顶GetTop(OVS)endl; n=0; q=0; if(y=1) if(GetTop(OPTR)=(&ch=-) w=1;ch=getchar(); else if(ch=() z=1;/记录左括号 else /coutcchendl; cout输入错误，请重新c; fflush(stdin); /清理缓存 ClearStack(&OPTR); ClearStack(&OVS); ExpEvaluation(); exit(1); if(y=0|z=1) /coutdchendl; /couto栈顶GetTop(OPTR)endl; /cout*Compare(GetTop(OPTR),ch)endl; switch(Compare(GetTop(OPTR),ch) case: Push(&OPTR,ch); y=1;z=0; ch=getchar(); /couteGetTop(OPTR): Pop(&OPTR,&op); Pop(&OVS,&b); Pop(&OVS,&a); if(op=/&b=0) cout输入错误，请重新d; fflush(stdin); /清理缓存 ClearStack(&OPTR); ClearStack(&OVS); ExpEvaluation(); exit(1); v=Execute(a,op,b); if(m=1)v=-v;m=0; Push(&OVS,v); /cout*栈顶GetTop(OVS)endl; break; case=: Pop(&OPTR,&op); ch=getchar(); break; case: cout括号不匹配，请重新e; ffl