数据结构C语言表达式求值(带详细注释)

/*表达式求值，输入一个表达式，如1+2*3#，程序可计算出结果为7支持以下符号：+-*/()^.可以计算整数、小数其中^表示次方，2^5表示2的5次方*//*头文件*/#include<stdio.h>#include<malloc.h>#include<string.h>#include<math.h>#include<stdlib.h>/*宏定义*/#defineINIT_STACK_SIZE100#defineSET_NUM8#defineN100/*字符优先级表*/unsignedcharprior[SET_NUM][SET_NUM]={/*'+''-''*''/''('')''#''^'*//*'+'*/'>','>','<','<','<','>','>','<',/*'-'*/'>','>','<','<','<','>','>','<',/*'*'*/'>','>','>','>','<','>','>','<',/*'/'*/'>','>','>','>','<','>','>','<',/*'('*/'<','<','<','<','<','=','','<',/*')'*/'>','>','>','>','','>','>','>',/*'#'*/'<','<','<','<','<','','=','<',/*'^'*/'>','>','>','>','<','>','>','>'};unsignedcharpriorSet[SET_NUM]={'+','-','*','/','(',')','#','^'};/*结构体定义，这是用来存放字符的栈*/typedefstruct{char*base;char*top;intstacksize;}SqStackC;/*结构体定义，这是用来存放数字的栈*/typedefstruct{double*base;double*top;intstacksize;}SqStackN;voidinitStackN(SqStackN&);voidinitStackC(SqStackC&);voidpushN(SqStackN&,double);voidpushC(SqStackN&,double);voidpopN(SqStackN&,double&);voidpopC(SqStackN&,double&);doublecalculate(double,char,double);intfindInSet(char);charcompare(char,char);voidgetSolution();/*主函数*/voidmain(){getSolution();}/*初始化数字栈*/voidinitStackN(SqStackN&S){S.base=(double*)malloc(INIT_STACK_SIZE*sizeof(double));S.top=S.base;S.stacksize=INIT_STACK_SIZE;}/*初始化字符栈*/voidinitStackC(SqStackC&S){S.base=(char*)malloc(INIT_STACK_SIZE*sizeof(char));S.top=S.base;S.stacksize=INIT_STACK_SIZE;}/*向数字栈中存放数字*/voidpushN(SqStackN&S,doublex){if(S.top-S.base>=S.stacksize)return;*(S.top++)=x;}/*向字符栈中存放字符*/voidpushC(SqStackC&S,charx){if(S.top-S.base>=S.stacksize)return;*(S.top++)=x;}/*从数字栈中取出数字*/voidpopN(SqStackN&S,double&x){if(S.top==S.base)return;x=*(--S.top);}/*从字符栈中取出字符*/voidpopC(SqStackC&S,char&x){if(S.top==S.base)return;x=*(--S.top);}/*这个函数返回aoperationb的值。假如operation为'+'，则返回a+b的值*/doublecalculate(doublea,charoperation,doubleb){/*判断operation，返回对应的计算结果*/switch(operation){case'+':returna+b;case'-':returnb-a;case'*':returna*b;case'/':returnb/a;case'^':returnpow(b,a);default:return0;}}/*查找字符c在priorSet中的什么位置*//*priorSet是所支持的所有字符的集合*/intfindInSet(charc){inti;for(i=0;i<SET_NUM;i++){if(priorSet[i]==c)returni;}return-1;}/*比较optrtop和c的优先关系*/charcompare(charoptrtop,charc){inti,j;/*从priorSet中取出optrtop和c的位置*/i=findInSet(optrtop);j=findInSet(c);/*如果返回值中有-1表示这个符号不支持，结束程序*/if(i==-1||j==-1){printf("不支持的符号类型\n");exit(0);}/*否则返回二者优先级关系*/elsereturnprior[i][j];}/*取得计算结果*//*解释下代码处理数字的原理：假如输入为10+2.2*3-2#循环会从这个字符串第一个位置开始，也就是1如果当前字符是个数字，则要把这个数字从字符串里取出来这个时候涉及两个问题，一是数字可能是大于10的整数，二是可能有小数。处理方法是这样的：当遇到数字，先将数字保存在n上，判断下一个字符是数字还是运算符如果是数字，则将n乘以10加上这个数字，这样即可以处理大于10的数字。如果遇到运算符，就退出循环去处理运算符如果遇到的是小数点，表示这个数字是小数。小数不会立刻计算出来，而是先将小数点忽视掉，将整数计算出。比如2.2会先计算成22变量j和begin在遇到小数点时候用来计算小数点后面有几个数字，即这个小数有多少位。当begin=1时候，表示现在要计算小数点后的数字位数。这时候j会在每次循环加1这样计算后，n=22,j=1;此时算n=n/pow(10,j);即将n缩小10的j次方。就变成了2.2*/voidgetSolution(){/*operation是当前的运算符*/charoperation;/*temp是输入的字符串*/chartemp[N];/*i是循环变量，j和begin用来控制什么时候计算出小数*/inti=0,j=-1,begin=0;/*sum是每次的计算结果，a和b是从数字栈中取出的数字，n用来存放从字符串中取出的数*/doublesum,a,b,n;/*定义堆栈并初始化*/SqStackCOPTR;SqStackNOPND;initStackC(OPTR);initStackN(OPND);/*向字符栈中压入#，标志开始*/pushC(OPTR,'#');/*获得输入*/printf("请输入一个表达式，输入#结束\n");gets(temp);/*开始计算，当遇到#表示结束*/while(temp[i]!='#'||*(OPTR.top-1)!='#'){/*如果当前字符是个数字字符*/if(temp[i]>='0'&&temp[i]<='9'){/*重置n为0*/n=0;/*当当前字符是数字或者小数点*/while(temp[i]>='0'&&temp[i]<='9'||temp[i]=='.'){/*如果是小数点，begin=1，表示要从字符串中取出一个小数*/if(temp[i]=='.')begin=1;/*否则作为整数取出*/else n=n*10+temp[i]-'0';/*如果begin不为0，表示遇到了一个小数点，表示需要合并为小数*//*j表示这个小数的小数点后面有几位*/if(begin!=0)j++;/*循环变量加1*/i++;}/*如果j不为-1，则表示这是个小数，n是整数结果，除以pow(10,j)则变成了小数*/if(j!=-1)n=n/pow(10,j);/*将数字压入栈*/pushN(OPND,n);/*重置j和begin的值*/j=-1;begin=0;}else{/*如果当前字符不是数字，比较栈顶字符和当前字符优先级，根据优先级处理*/switch(compare(*(OPTR.top-1),temp[i])){/*如果栈顶字符优先级大，则可以取出计算*/case'>':/*取出字符栈顶运算符，和数字栈顶的两个数字*/popC(OPTR,operation);popN(OPND,a);popN(OPND,b);/*计算结果*/sum=calculate(a,operation,b);/*结果入栈*/pushN(OPND,