算术表达式求值.doc

#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define ERROR -1#define TRUE 1#define OK 1struct SpStackRchar *top;char *base;int stacksize;/定义操作符栈结构体struct SpStackDint *top;int *base;int stacksize;/定义操作数结构体int InitStack(SpStackR &S)/定义建立操作符空栈的函数S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);/为栈申请指定长度的空间if(!S.base) exit(OVERFLOW);/如果空间申请失败，则返回-1S.top=S.base;/空栈时，站定指针和栈底指针指向同一单元S.stacksize=STACK_INIT_SIZE;return OK;int Push(SpStackR &S,char e)/定义操作符的入栈函数if(S.top-S.base=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);/如果栈已满，则追加栈的空间 if(!S.base) exit(OVERFLOW);/如果空间申请失败，则返回-1 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;return OK;int Pop(SpStackR &S,char &e)/定义操作符的出栈函数if(S.topS.base) return *(S.top-1); /如果栈非空，则返回栈顶元素 int InitStack(SpStackD &S)/定义建立操作数空栈的函数S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);/为栈申请指定长度的空间if(!S.base) exit(OVERFLOW);/如果空间申请失败，则返回-1S.top=S.base;/空栈时，站定指针和栈底指针指向同一单元S.stacksize=STACK_INIT_SIZE;return OK;int Push(SpStackD &S,int e)/定义操作数的入栈函数if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int);/如果栈已满，则追加栈的空间 if(!S.base) exit(OVERFLOW);/如果空间申请失败，则返回-1 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;return OK;int Pop(SpStackD &S,int &e)/定义操作数的出栈函数if(S.topS.base) return *(S.top-1); /如果栈非空，则返回栈顶元素 int Precede(char c1,char c2)/定义比较两个操作符优先级的函数，若c1大，则返回1；若等大，则返回0；若c1小，则返回-1switch(c1)/对第一个操作符为不同情况时，分别进行操作case +:if(c2=+)|(c2=-)|(c2=)|(c2=#) return 1; return -1;break;case -:if(c2=+)|(c2=-)|(c2=)|(c2=#) return 1; return -1;break; case *:if(c2=() return -1; return 1;break; case /:if(c2=() return -1; return 1;break; case (:if(c2=) return 0; return -1;break; case ):return 1;break;case #:if(c2=#) return 0; return -1;break;default :return ERROR; int Operate(int a,char b,int c)/定义运算函数，对操作数a和c及操作符b进行算术运算，返回运算结果switch(b)case +:return (a+c);break;case -:return (a-c);break;case *:return (a*c);break;case /:return (a/c);break; void main()/定义主函数char exp100;/定义数组，用于存放输入的运算表达式int a=0,b,d,e,f=0;char c;coutexp;for(;expa!=#;a+)switch(expa)case (:f+; break; case ):f-; break;if(f0) break;if(f!=0) cout输入的括号不配对！endl;/判断输入的括号是否配对，若配对，则进行算术表达式的求值，否则结束操作elseSpStackR OPTR;SpStackD OPND;InitStack(OPTR);/建立空的运算符栈InitStack(OPND);/建立空的运算数栈Push(OPTR,#);/#号如运算符栈cout=0)&(expa=9)/当当前字符为数字时，将字符转化为相应的数字 b=0;b=b*10+(expa-0);cout=0)&(expa+1=9) b=b*10+(expa+1-0);a+;coutexpa; Push(OPND,b); a+;cout ; /转化完的数字进入运算数栈else switch(Precede(GetTop(OPTR),expa) case -1:Push(OPTR,expa); a+; break;/当栈顶运算符优先符较低时，入栈 case 0:Pop(OPTR,c); a+; break;/当优先级相同时，脱括号 case 1:Pop(OPTR,c); coutc ; Pop(OPND,d); Pop(OPN