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

#include #include#include#include#includeusing namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_SIZE 100#define STACKINCREMENT 10#define OPSIZE 7typedef double ElemType;typedef char SElemType;char opOPSIZE=+,-,*,/,(,),#;char priorOPSIZEOPSIZE=, ,base=(ElemType *)malloc(STACK_SIZE * sizeof(ElemType); if(NULL=S1-base) printf(Init Failed!n); exit (OVERFLOW); else S1-top=S1-base; S1-Stacksize=STACK_SIZE; int StackEmpty(OPND *S1) if(S1-top=S1-base) return 1; else return 0;int StackEmpty(OPTR *S2) if(S2-top=S2-base) return 1; else return 0;void InitStack(OPTR *S2) S2-base=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType); if(NULL=S2-base) printf(Init Failed!n); exit (OVERFLOW); else S2-top=S2-base; S2-Stacksize=STACK_SIZE; void Push(OPND *S1,ElemType e) if(S1-top-S1-base=S1-Stacksize) S1-base=(ElemType *)realloc(S1-base,(S1-Stacksize+STACKINCREMENT)*sizeof(ElemType); if(!S1-base) exit(OVERFLOW); S1-top=S1-base+S1-Stacksize; S1-Stacksize=S1-Stacksize+STACKINCREMENT; *S1-top=e; S1-top+;void Push(OPTR *S2,SElemType e) if(S2-top-S2-base=S2-Stacksize) S2-base=(SElemType *)realloc(S2-base,(S2-Stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S2-base) exit (OVERFLOW); S2-top=S2-base+S2-Stacksize; S2-Stacksize+=STACKINCREMENT; *S2-top+=e;ElemType Pop(OPND *S1,ElemType *e) if(!StackEmpty(S1) S1-top=S1-top-1; *e=*S1-top; else return ERROR; return OK;SElemType Pop(OPTR *S2,SElemType *e) if(StackEmpty(S2) return ERROR; else *e=*-S2-top; return OK;ElemType GetTop(OPND *S1,ElemType *e) if(!StackEmpty(S1) *e=*(S1-top-1); return OK;SElemType GetTop(OPTR *S2,SElemType *e) if(!StackEmpty(S2) *e=*(S2-top-1); return OK;bool Judege(char c,char *op)/判断C是否为运算符 bool check=false; int i; for(i=0;iOPSIZE;i+) if(c=opi) check = true; return check;int ReturnOpOrd(char c,char *op)/返回运算符c在OP中的位置 int i; for(i=0;iOPSIZE;i+) if(c=opi) return i; return OK;char Precede(char theat1,char theat2)/g判断运算符栈的栈顶运算符theta1和读入的运算符theta2优先关系 return priorReturnOpOrd(theat1,op)ReturnOpOrd(theat2,op);double Operate(ElemType a,SElemType theat,ElemType b)/操作数进行运算 switch(theat) case +: return a+b; break; case -: return a-b; break; case *: return a*b; break; case /: if(b!=0) return a/b; else printf(出错！除数为0！n); return ERROR; break; default: return 0; float EvaluateExpression(char *expression) OPND S1; OPTR S2; char *c=expression; ElemType e1,e2,result,d; char temp10,r2; SElemType e; InitStack(&S1); InitStack(&S2); Push(&S2,#); strcpy(temp,0); while(*c!=#|(GetTop(&S2,&e),e)!=#) if(!Judege(*c,op) r0=*c; r1=0; strcat(temp,r); c+; if(Judege(*c,op) d=(float)atof(temp); Push(&S1,d); strcpy(temp,0); else switch(Precede( (GetTop(&S2,&e),e),*c) case : Pop(&S1,&e1); Pop(&S1,&e2); Pop(&S2,&e); result=Operate(e2,e,e1); Push(&S1,result); break; Pop(&S1,&result); return result;int main()