算术表达式的设计与实现问题!!!!
程序代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define STACK_INITSIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配量 #define OPSETSIZE 7 //算符的长度 typedef struct node { char ch; node *next; }Linkstack; Linkstack *Setstack() { //创建空链栈 Linkstack *S; S=(Linkstack *)malloc(sizeof(Linkstack)); S->next=NULL; return S; } Linkstack *Pushstack(Linkstack *S,char c) { //入栈 Linkstack *p; p=(Linkstack *)malloc(sizeof(Linkstack)); p->ch=c; p->next=S->next; S->next=p; return S; } Linkstack *Popstack(Linkstack *S) { //出栈 Linkstack *p; p=S->next; S->next=p->next; free(p); return S; } char Gettop(Linkstack *S) { //取栈顶数据 if(S->next!=NULL) return S->next->ch; else return ' '; } int Judgepair( ) { //判断圆括号是否正确配对 Linkstack *p; char c; int sign=1; p=Setstack(); printf("请输入算术表达式?并以'#'结束!\n"); c=MyExpression; while(c!='#') { switch(c){ case'(': //扫描到'('入栈 p=Pushstack(p,c); break; case')': //扫描到')'?判断栈顶是否是'(' if(Gettop(p)=='(') //若栈顶是'(',则出栈 p=Popstack(p); else //若栈顶不是'(',则配对错误 sign=0; break; } if(sign==0) break; else c=MyExpression; } if(p->next!=NULL) //最后查看栈中是否为空 sign=0; return sign; } void Judgeout(int a) { //判断结果输出 if(a==1) printf("算术表达式圆括号配对正确!\n"); if(a==0) printf("算术表达式圆括号配对错误!\n"); } /*----------算符栈的结构体--------------*/ typedef struct { char * base; //算符栈的栈底 char * top; //算符栈的栈顶 int stacksize; //算符栈的最大长度 }OPTR_STACK; /*----------操作数栈的结构体------------*/ typedef struct { double * base; //操作数栈的栈底 double * top; //操作数栈的栈顶 int stacksize; //操作数栈的最大长度 }OPND_STACK; /*-----------*/ int OPTR_InitStack(OPTR_STACK &s) // 算符栈的初始化函数 { s.base=(char *)malloc(STACK_INITSIZE*sizeof(char)); // 算符栈分配初始的存储空间 if(!s.base) return 0; // 若申请存储空间失败,返回0 s.top=s.base; // 栈顶等于栈底,为空栈 s.stacksize=STACK_INITSIZE; // 算符栈的最大长度为100 return 1; } char OPTR_GetTop(OPTR_STACK &s) { // 取算符栈顶元素函数 char e; if(s.top==s.base) return 0; // 算符栈为空,返回0 e=*(s.top-1); return e; // 返回算符栈顶元素 *(s.top-1) } int OPTR_Push(OPTR_STACK &s,char e) // 算符栈插入元素函数 { if(s.top-s.base>=s.stacksize) // 当栈的长度超过规定的最大长度s.stacksize时,需要申请额外的存储空间 { s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char)); if(!s.base) return 0; // 若申请空间失败,则返回0 s.top=s.base+s.stacksize; // 申请额外空间之前的栈顶位置s.top为s.base+s.stacksize s.stacksize+=STACKINCREMENT; // 申请额外空间之后的栈的长度增加了STACKINCREMENT } *s.top++=e; // 若栈的长度未超过规定的最大长度s.stacksize,将元素e入栈顶 return 1; } int OPTR_Pop(OPTR_STACK &s,char &e){ // 算符栈顶元素出栈函数 if(s.top==s.base) return 0; // 若为空栈,返回0 e=*--s.top; // 不为空栈,将栈顶元素出栈 return 1; } int OPND_InitStack(OPND_STACK &s) // 操作数栈的初始化函数 { s.base=(double *)malloc(STACK_INITSIZE*sizeof(double)); // 操作数栈分配初始的存储空间 if(!s.base) return 0; // 若申请存储空间失败,返回0 s.top=s.base; // 栈顶等于栈底,为空栈 s.stacksize=STACK_INITSIZE; // 操作数栈的最大长度为100 return 1; } double OPND_GetTop(OPND_STACK &s) // 取操作数栈顶元素函数 { double e; if(s.top==s.base) return 0; // 操作数栈为空,返回0 e=*(s.top-1); // 返回操作数栈顶元素 *(s.top-1) return e; } int OPND_Push(OPND_STACK &s,double e) // 操作数栈插入元素函数 { if(s.top-s.base>=s.stacksize) // 当栈的长度超过规定的最大长度s.stacksize时,需要申请额外的存储空间 { s.base=(double *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(double)); if(!s.base) return 0; // 若申请空间失败,则返回0 s.top=s.base+s.stacksize; // 申请额外空间之前的栈顶位置s.top为s.base+s.stacksize s.stacksize+=STACKINCREMENT; // 申请额外空间之后的栈的长度增加了STACKINCREMENT } *s.top++=e; // 若栈的长度未超过规定的最大长度s.stacksize,将元素e入栈顶 return 1; } int OPND_Pop(OPND_STACK &s,double &e) // 操作数栈顶元素出栈函数 { if(s.top==s.base) return 0; // 操作数栈为空,返回0 e=*--s.top; // 不为空栈,将栈顶元素出栈 return 1; } char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'}; //7种算符:'+' (加),'-' (减),'*' (乘),'/' (除),'(' (左括号),')' (右括号),'#' (结束符) char Prior[7][7] = { //7种算符的算符优先级如下 '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '<' , '<' , '<' , '<' , '<' , '=' , ' ', '>' , '>' , '>' , '>' , ' ' , '>' , '>', '<' , '<' , '<' , '<' , '<' , ' ' , '=' }; double Operate( double a, char theta, double b) // 两个数之间的四则运算函数 { switch(theta) // theta为运算符 { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; default : return 0; } } int In(char Test, char * TestOp) // 算符的判断函数 { int m=0; for (int i=0; i< OPSETSIZE; i++) // 将输入的字符与已知规定的算符比较 if (Test == TestOp[i]) m=1; return m; } int ReturnOpOrd(char op, char* TestOp) //返回该算符在算符数组中的位置的函数 { int i; for(i=0; i< OPSETSIZE; i++) if(op == TestOp[i]) return i; return 0; } char Precede(char Aop, char Bop) // 两个算符的优先级的判断函数 { return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)]; } double EvaluateExpression(char * MyExpression) { /* 表达式的正确性判断函数,同时计算表达式 */ OPTR_STACK OPTR; // OPTR为算符栈 OPND_STACK OPND; // OPND为操作数栈 char TempData[40]; // TempData[40]为辅助字符数组 double Data,a,b; // a和b为进行运算的两个操作数 char theta,*c,x,Dr[2]; // theta是算符,*c和x均为字符串的当前字符,Dr[2]保存当前字符和结束符 OPTR_InitStack (OPTR); // 初始化算符栈 OPTR_Push (OPTR, '#'); // '#'入算符栈,作为表达式的第一个字符 printf(" #入栈 \n"); OPND_InitStack (OPND); // 初始化操作数栈 c = MyExpression; // 当前c保存字符串MyExpression的首地址 strcpy(TempData,"\0"); while (*c!= '#' || OPTR_GetTop(OPTR)!= '#') // 当字符串的首字符和尾字符同时为#时,运算结束 { if(In(*c, OPSET)==0){ // 若当前字符是操作数 Dr[0]=*c; // Dr[0]保存当前字符 Dr[1]='\0'; // Dr[1]保存字符串的结束符'\0' strcat(TempData,Dr); // 将当前字符*c和结束符'\0'连接到字符串TempData中 c++; if(In(*c,OPSET)==1){ // 考虑到操作数有可能不止一位数 Data=(double)atof(TempData); // atof函数是将当前字符串转换成浮点型数据 OPND_Push(OPND, Data); strcpy(TempData,"\0"); printf(" %.3f入栈 \n",Data); } } else{ // 若当前字符是算符 switch (Precede(OPTR_GetTop(OPTR), *c)) { // 获取当前算符栈的栈顶字符,与*c比较优先级,进行运算 case '<': // 若当前栈顶算符优先级小于*c,则*c入算符栈 OPTR_Push(OPTR, *c); printf(" %c入栈 \n",*c); c++; break; case '=': // 若当前栈顶算符优先级等于*c,则当前栈顶字符出栈 OPTR_Pop(OPTR, x); printf(" %c出栈 \n",x); c++; break; case '>': // 若当前栈顶算符优先级大于*c,则进行运算 OPTR_Pop(OPTR, theta); // 将栈顶算符出栈 printf(" %c 出栈 \n",theta); OPND_Pop(OPND, b); // 将栈顶操作数出栈 printf(" %.3f出栈 \n",b); OPND_Pop(OPND, a); // 将次栈顶操作数出栈 printf(" %.3f出栈 \n",a); OPND_Push(OPND, Operate(a, theta, b)); // 将运算结果入操作数栈 printf(" %.3f入栈 \n",Operate(a, theta, b)); break; } } } return OPND_GetTop(OPND); // 返回表达式的运算结果 } void main() { int x,t=0; double RESULT; char * MyExpression,str[40]; printf(" 《 算术表达式的四则运算 》 \n"); printf("^^本课程设计完成简单的加、减、乘、除四则运算的功能^^\n\n"); printf(" case 1: 输入表达式 \n"); printf(" case 2: 输出表达式 \n"); printf(" case 3: 检验表达式 \n"); printf(" case 4: 计算表达式 \n"); printf(" case 0: 退出程序 \n\n"); for(;;){ printf(" 请输入您要进行的操作的序号:"); scanf("%d",&x); switch(x){ case 1: t++; getchar(); printf(" 请输入一个正确的表达式 \n\t\t\t\t"); gets(str); MyExpression=str; break; case 2: if(t==0) printf("您尚未输入表达式,请先进行1操作,然后再进行此操作! \n"); else{ printf(" 您输入的表达式为\n\t "); puts(MyExpression); } break; case3: if(t==0) printf("您尚未输入表达式,请先进行1操作,然后再进行此操作! \n"); else Judgeout(Judgepair()); break; case 4: if(t==0) printf("您尚未输入表达式,请先进行1操作,然后再进行此操作! \n"); else { RESULT=EvaluateExpression(MyExpression); printf(" 算术表达式的结果:%.3f \n",RESULT); } break; case 0: printf(" 欢迎使用,BYE BYE ^^__^^ \n"); exit(0); default: printf(" 操作序号错误,请重新输入 !\n"); break; } } }
在case3,检验表达式处错误,请各位大神指教指教!!!!