數(shù)據(jù)結(jié)構(gòu)C語言表達式求值(帶詳細注釋)

/*表達式求值，輸入一個表達式，如1+2*3#，程序可計算出結(jié)果為7支持以下符號：+-*/()^.可以計算整數(shù)、小數(shù)其中^表示次方，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/*字符優(yōu)先級表*/unsignedcharprior[SET_NUM][SET_NUM]={/*'+''-''*''/''('')''#''^'*//*'+'*/'>','>','<','<','<','>','>','<',/*'-'*/'>','>','<','<','<','>','>','<',/*'*'*/'>','>','>','>','<','>','>','<',/*'/'*/'>','>','>','>','<','>','>','<',/*'('*/'<','<','<','<','<','=','','<',/*')'*/'>','>','>','>','','>','>','>',/*'#'*/'<','<','<','<','<','','=','<',/*'^'*/'>','>','>','>','<','>','>','>'};unsignedcharpriorSet[SET_NUM]={'+','-','*','/','(',')','#','^'};/*結(jié)構(gòu)體定義，這是用來存放字符的棧*/typedefstruct{char*base;char*top;intstacksize;}SqStackC;/*結(jié)構(gòu)體定義，這是用來存放數(shù)字的棧*/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();/*主函數(shù)*/voidmain(){getSolution();}/*初始化數(shù)字棧*/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;}/*向數(shù)字棧中存放數(shù)字*/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;}/*從數(shù)字棧中取出數(shù)字*/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);}/*這個函數(shù)返回aoperationb的值。假如operation為'+'，則返回a+b的值*/doublecalculate(doublea,charoperation,doubleb){/*判斷operation，返回對應的計算結(jié)果*/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的優(yōu)先關系*/charcompare(charoptrtop,charc){inti,j;/*從priorSet中取出optrtop和c的位置*/i=findInSet(optrtop);j=findInSet(c);/*如果返回值中有-1表示這個符號不支持，結(jié)束程序*/if(i==-1||j==-1){printf("不支持的符號類型\n");exit(0);}/*否則返回二者優(yōu)先級關系*/elsereturnprior[i][j];}/*取得計算結(jié)果*//*解釋下代碼處理數(shù)字的原理：假如輸入為10+2.2*3-2#循環(huán)會從這個字符串第一個位置開始，也就是1如果當前字符是個數(shù)字，則要把這個數(shù)字從字符串里取出來這個時候涉及兩個問題，一是數(shù)字可能是大于10的整數(shù)，二是可能有小數(shù)。處理方法是這樣的：當遇到數(shù)字，先將數(shù)字保存在n上，判斷下一個字符是數(shù)字還是運算符如果是數(shù)字，則將n乘以10加上這個數(shù)字，這樣即可以處理大于10的數(shù)字。如果遇到運算符，就退出循環(huán)去處理運算符如果遇到的是小數(shù)點，表示這個數(shù)字是小數(shù)。小數(shù)不會立刻計算出來，而是先將小數(shù)點忽視掉，將整數(shù)計算出。比如2.2會先計算成22變量j和begin在遇到小數(shù)點時候用來計算小數(shù)點后面有幾個數(shù)字，即這個小數(shù)有多少位。當begin=1時候，表示現(xiàn)在要計算小數(shù)點后的數(shù)字位數(shù)。這時候j會在每次循環(huán)加1這樣計算后，n=22,j=1;此時算n=n/pow(10,j);即將n縮小10的j次方。就變成了2.2*/voidgetSolution(){/*operation是當前的運算符*/charoperation;/*temp是輸入的字符串*/chartemp[N];/*i是循環(huán)變量，j和begin用來控制什么時候計算出小數(shù)*/inti=0,j=-1,begin=0;/*sum是每次的計算結(jié)果，a和b是從數(shù)字棧中取出的數(shù)字，n用來存放從字符串中取出的數(shù)*/doublesum,a,b,n;/*定義堆棧并初始化*/SqStackCOPTR;SqStackNOPND;initStackC(OPTR);initStackN(OPND);/*向字符棧中壓入#，標志開始*/pushC(OPTR,'#');/*獲得輸入*/printf("請輸入一個表達式，輸入#結(jié)束\n");gets(temp);/*開始計算，當遇到#表示結(jié)束*/while(temp[i]!='#'||*(OPTR.top-1)!='#'){/*如果當前字符是個數(shù)字字符*/if(temp[i]>='0'&&temp[i]<='9'){/*重置n為0*/n=0;/*當當前字符是數(shù)字或者小數(shù)點*/while(temp[i]>='0'&&temp[i]<='9'||temp[i]=='.'){/*如果是小數(shù)點，begin=1，表示要從字符串中取出一個小數(shù)*/if(temp[i]=='.')begin=1;/*否則作為整數(shù)取出*/else n=n*10+temp[i]-'0';/*如果begin不為0，表示遇到了一個小數(shù)點，表示需要合并為小數(shù)*//*j表示這個小數(shù)的小數(shù)點后面有幾位*/if(begin!=0)j++;/*循環(huán)變量加1*/i++;}/*如果j不為-1，則表示這是個小數(shù)，n是整數(shù)結(jié)果，除以pow(10,j)則變成了小數(shù)*/if(j!=-1)n=n/pow(10,j);/*將數(shù)字壓入棧*/pushN(OPND,n);/*重置j和begin的值*/j=-1;begin=0;}else{/*如果當前字符不是數(shù)字，比較棧頂字符和當前字符優(yōu)先級，根據(jù)優(yōu)先級處理*/switch(compare(*(OPTR.top-1),temp[i])){/*如果棧頂字符優(yōu)先級大，則可以取出計算*/case'>':/*取出字符棧頂運算符，和數(shù)字棧頂?shù)膬蓚€數(shù)字*/popC(OPTR,operation);popN(OPND,a);popN(OPND,b);/*計算結(jié)果*/sum=calculate(a,operation,b);/*結(jié)果入棧*/pushN(OPND,