C语言实现表达式计算.doc

一、设计思想两种算法首先都要建立两个栈，一个是存放操作数的数栈OdStack,—个是存放运算符的符栈OpStack数栈采用double型的用来存放浮点数，符栈采用char型的用来存放运算符，由于考虑到运算符有优先级的问题，所以事先做了一个Type用来存储运算符的优先级栈建立好了之后做栈的相关操作，初始化栈，入栈，出栈，看栈顶其中入栈要判满，出栈和看栈顶要判空中缀转后缀再计算的算法此算法的基本思路是先将中缀表达式转换成后缀表达式，之后再利用后缀表达式的算法对表达式进行计算首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符如果是数元素（或小数点元素），则依次存入用来存储后缀表达式的char数组，直到一个整合数存完之后用空格将其与后面的元素分开如果是运算符元素,则根据当前运算符的优先级和栈里面的运算符的优先级进行处理如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次将出栈元素存入后缀表达式，并用空格将其与后面的元素分开，直到栈内元素的优先级小或者栈内为空对于左括号来说，无条件进栈，并只在有右括号出现的时候才有可能出栈。

对于右括号来说，无条件让栈内元素出栈，直到左括号出栈依次将每个元素进行处理直到中缀表达式索引完毕至此，已经实现了将中缀表达式转换成了后缀表达式，在数组的最后加上结束符以便下一步的调用第二步，读出后缀表达式并进行计算如果索引到空格则将索引标志后推1位之后要先对char型的数字元素进行整合，从后缀表达式中依次取出数字元素（连同小数点）存入一个新的char型数组，直到一整个数取完后通过atof函数将char型转换成浮点型存入数栈,并将新数组初始化用来存储下一个数如果是索引到运算符，则在数栈中出栈两个数字与当前运算符进行运算，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈依次进行计算直到后缀表达式索引完毕此时对栈内剩余元素进行操作每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈循环操作直到符栈栈空，此时数栈出栈元素即为最后结果边转换边计算的算法此算法的基本思路是将中缀表达式按照转换后缀的表达式的方法逐步进行，边转换边进行计算和存储首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。

如果是数元素（或小数点元素），则利用如上算法先进行元素整合，并将整合的元素通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数如果是索引到运算符，则要先根据当前运算符的优先级和栈里面的运算符的优先级进行处理如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次出栈元素进行计算每次计算要在数栈出栈两个整合后的数，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈如果遇到左括号则无条件进栈，并只在有右括号出现的时候才有可能出栈如果遇到右括号，则无条件让栈内元素出栈进行计算，直到左括号出栈为止如此计算将表达式所有元素全部索引之后再对栈内剩余元素进行操作每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈循环操作直到符栈栈空，此时数栈出栈元素即为最后结果为了方便计算，计算过程使用了函数体主函数只负责输入中缀表达式和输出最后的运算结果同时，建立了优先级函数使用了swich语句为每个运算符赋值优先级，方便在计算过程中直接调用也建立了运算函数对每个运算符做特定的运算，也是使用了swich语句。

另外，最后为了能够识别一些错误，在运算过程中加入了错误的判定，比如出栈时栈空或者左右符号不符等在编写过程中发现数栈的看栈顶没有使用过，所以删除了数栈的看栈顶二、算法流程图中缀转后缀再计算的算法分两个流程，第一步是中缀表达式转换成后缀表达式;-#-初始化1C开始J存入符栈-#--#-第二步是将后缀表达式进行计算输出图2后缀计算算法流程图-#--#-边转换边计算的算法只一个流程即可E初始化输入中缀表达式中缀衷数字整舍,辣作符元袁t定义操作符优先级出栈一个运算符耳存入符栈数栈弹出两亍数与当前操作符进行计算得到结果存入数栈*否出栈一个运算符中缀表达式索引结束符栈为空数栈岀栈结東大于栈顶优先级或栈空数栈弹出两个数与学前操作符进彳亍计算得到结果图3边转换边计算算法流程图-#-用两种方式实现表达式自动计算/*N为数栈和表达式数组容量*//*M为符栈和其他数组容量*//*定义运算符类型，level为运算符等级*//*定义数栈*//*定义符栈*//*定义初始化数栈*//*进数栈*//*如果栈满则报错退出程序*//*定义出数栈*//*如果栈空则报错退出程序*//*定义初始化符栈*//*定义进符栈*/三、源代码下面给出的是用中缀转后缀再计算的算法实现的程序的源代码#include#include#defineN100#defineM50typedefstruct{charType;intlevel;}Type;typedefstruct{doublestack[N];inttop;}OdStack;typedefstruct{Typestack[M];inttop;}OpStack;voidInit_OdStack(OdStack*s){(*s).top=0;}voidOdPush(OdStack*s,doublen){if((*s).top==N-1)Error();(*s).stack[(*s).top]=n;(*s).top++;}doubleOdPop(OdStack*s){if((*s).top==0)Error();else{(*s).top--;return(*s).stack[(*s).top];}}voidInit_OpStack(OpStack*s){(*s).top=0;}voidOpPush(OpStack*s,Type*sign)-#-用两种方式实现表达式自动计算-#-用两种方式实现表达式自动计算if((*s).top==M-1)Error();(*s).stack[(*s).top]=*sign;(*s).top++;}TypeOpPop(OpStack*s){if((*s).top==0)Error();else{(*s).top--;return(*s).stack[(*s).top];}}TypeOpPeek(OpStack*s){Typeren;if((*s).top==0){ren.level=0;returnren;}elsereturn(*s).stack[(*s).top-1];}intError(){printf("Error!");getch();exit(1);}intCom(chartempch){intlevel;switch(tempch){case'+':case'-':level=1;break;case'*':case'/':case'%':level=2;break;}/*如果栈满则报错退出程序*//*定义出符栈*//*栈空则报错退出程序*//*定义看符栈顶*//*判栈空，空则赋等级0值*//*报错函数*//*定义运算符等级*//*给不同运算符定级*/-#-用两种方式实现表达式自动计算-#-用两种方式实现表达式自动计算returnlevel;doubleOper(doublea,doubleb,chartempch)/*定义运算过程*/doubleren;switch(tempch){case'+':ren=b+a;break;case'-':ren=b-a;break;case'*':ren=b*a;break;case'/':ren=b/a;break;case'%':ren=(int)b%(int)a;break;}/*对不同运算符执行运算并返回结果*//*取模运算将数取整*/returnren;}doubleCalu(char*exp1){OdStackOdStack;OpStackOpStack;Typetempsign;charexp2[N],tempexp[M],tempch;/*定义数栈*//*定义符栈*//*定义Type型运算符*//*定义后缀表达式数组exp2，整合数组tempexp,tempeh为运算符*/intindex1,index2,tempindex;/*index1为主要索引，index2为次要索引，tempindex为附加索引*/doublenumber,a,b,e;Init_OdStaek(&OdStaek);Init_OpStaek(&OpStaek);index1=0;index2=0;tempindex=0;tempexp[0]='\0';/*number为整合数，a、b、e为运算数*//*初始化数栈*//*初始化符栈*//*初始化索引，附加索引*//*初始化整合数组*/while(exp1[index1]!='\0')/*处理初始表达式转化成后缀表达式*/{if((exp1[index1]>='0'&&exp1[index1]<='9'))/*处理数字元素*/{while((exp1[index1]>='0'&&exp1[index1]<='9')||exp1[index1]=='.'){exp2[index2]=exp1[index1];/*连续的数字元素不分开并依次存入后缀表达式*/index2++;index1++;}exp2[index2]='';/*结束后用空格将其与后面的元素分开*/index2++;}。