C语言实现表达式计算18页

1、一、设计思想两种算法首先都要建立两个栈，一个是存放操作数的数栈OdStack，一个是存放运算符的符栈OpStack。数栈采用double型的用来存放浮点数，符栈采用char型的用来存放运算符，由于考虑到运算符有优先级的问题，所以事先做了一个Type用来存储运算符的优先级。栈建立好了之后做栈的相关操作，初始化栈，入栈，出栈，看栈顶。其中入栈要判满，出栈和看栈顶要判空。中缀转后缀再计算的算法。此算法的基本思路是先将中缀表达式转换成后缀表达式，之后再利用后缀表达式的算法对表达式进行计算。首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。如果是数元素（

2、或小数点元素），则依次存入用来存储后缀表达式的char数组，直到一个整合数存完之后用空格将其与后面的元素分开。如果是运算符元素，则根据当前运算符的优先级和栈里面的运算符的优先级进行处理。如果栈内元素的优先级小于当前元素的优先级或者栈内为空，则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次将出栈元素存入后缀表达式，并用空格将其与后面的元素分开，直到栈内元素的优先级小或者栈内为空。对于左括号来说，无条件进栈，并只在有右括号出现的时候才有可能出栈。对于右括号来说，无条件让栈内元素出栈，直到左括号出栈。依次将每个元素进行处理直到中缀表达式索引完毕。至此，已经实现了将中缀表达式转换成了

3、后缀表达式，在数组的最后加上结束符以便下一步的调用。第二步，读出后缀表达式并进行计算。如果索引到空格则将索引标志后推1位。之后要先对char型的数字元素进行整合，从后缀表达式中依次取出数字元素（连同小数点）存入一个新的char型数组，直到一整个数取完后通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数。如果是索引到运算符，则在数栈中出栈两个数字与当前运算符进行运算，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈。依次进行计算直到后缀表达式索引完毕。此时对栈内剩余元素进行操作。每在符栈出栈一个运算符，就从数栈出栈两个数进行计

4、算，算法同上，将运算以后的结果再次存入数栈。循环操作直到符栈栈空，此时数栈出栈元素即为最后结果。边转换边计算的算法。此算法的基本思路是将中缀表达式按照转换后缀的表达式的方法逐步进行，边转换边进行计算和存储。首先，用一个char数组将中缀表达式读入，对数组中的每一个元素进行处理，区分哪些是数，哪些是运算符。如果是数元素（或小数点元素），则利用如上算法先进行元素整合，并将整合的元素通过atof函数将char型转换成浮点型存入数栈，并将新数组初始化用来存储下一个数。如果是索引到运算符，则要先根据当前运算符的优先级和栈里面的运算符的优先级进行处理。如果栈内元素的优先级小于当前元素的优先级或者栈内为空，

5、则将当前运算符入栈；如果栈内元素的优先级大于等于当前元素的，则依次出栈元素进行计算。每次计算要在数栈出栈两个整合后的数，先出栈的数字放在运算符后面，后出栈的数字放在运算符的前面，将运算以后的结果再次存入数栈。如果遇到左括号则无条件进栈，并只在有右括号出现的时候才有可能出栈。如果遇到右括号，则无条件让栈内元素出栈进行计算，直到左括号出栈为止。如此计算将表达式所有元素全部索引。之后再对栈内剩余元素进行操作。每在符栈出栈一个运算符，就从数栈出栈两个数进行计算，算法同上，将运算以后的结果再次存入数栈。循环操作直到符栈栈空，此时数栈出栈元素即为最后结果。为了方便计算，计算过程使用了函数体。主函数只负责输

6、入中缀表达式和输出最后的运算结果。同时，建立了优先级函数使用了swich语句为每个运算符赋值优先级，方便在计算过程中直接调用。也建立了运算函数对每个运算符做特定的运算，也是使用了swich语句。另外，最后为了能够识别一些错误，在运算过程中加入了错误的判定，比如出栈时栈空或者左右符号不符等。在编写过程中发现数栈的看栈顶没有使用过，所以删除了数栈的看栈顶。二、算法流程图中缀转后缀再计算的算法分两个流程，第一步是中缀表达式转换成后缀表达式；图1 中缀转后缀算法流程图第二步是将后缀表达式进行计算输出。图2 后缀计算算法流程图边转换边计算的算法只一个流程即可。图3 边转换边计算算法流程图三、源代码下面给

7、出的是用中缀转后缀再计算的算法实现的程序的源代码：#include#include#define N 100/*N为数栈和表达式数组容量*/#define M 50/*M为符栈和其他数组容量*/typedef struct /*定义运算符类型，level为运算符等级*/ char Type; int level;Type;typedef struct /*定义数栈*/ double stackN; int top;OdStack;typedef struct /*定义符栈*/ Type stackM; int top;OpStack;void Init_OdStack(OdStack *s)

8、/*定义初始化数栈*/ (*s).top=0; void OdPush(OdStack *s,double n) /*进数栈*/ if(*s).top=N-1) /*如果栈满则报错退出程序*/ Error(); (*s).stack(*s ).top=n; (*s).top+;double OdPop(OdStack *s) /*定义出数栈*/ if (*s).top=0) /*如果栈空则报错退出程序*/ Error(); else (*s).top-; return (*s).stack(*s).top; void Init_OpStack(OpStack *s) /*定义初始化符栈*/ (

9、*s).top=0; void OpPush(OpStack *s,Type *sign) /*定义进符栈*/ if(*s).top=M-1) /*如果栈满则报错退出程序*/ Error(); (*s).stack(*s).top=*sign; (*s).top+;Type OpPop(OpStack *s) /*定义出符栈*/ if (*s).top=0) /*栈空则报错退出程序*/ Error(); else (*s).top-; return (*s).stack(*s).top; Type OpPeek(OpStack *s) /*定义看符栈顶*/ Type ren; if (*s).

10、top=0) /*判栈空，空则赋等级0值*/ ren.level=0; return ren; else return (*s).stack(*s).top-1;int Error() /*报错函数*/ printf(Error!); getch(); exit(1);int Com(char tempch) /*定义运算符等级*/ int level; /*给不同运算符定级*/ switch (tempch) case +: case -:level=1;break; case *: case /: case %:level=2;break; return level;double Oper

11、(double a,double b,char tempch) /*定义运算过程*/ double ren; 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; /*取模运算将数取整*/ return ren;double Calu(char *exp1) OdStack OdStack; /*定义数栈*/ OpStack OpStack

12、; /*定义符栈*/ Type tempsign; /*定义Type型运算符*/ char exp2N,tempexpM,tempch; /*定义后缀表达式数组exp2，整合数组tempexp，tempch为运算符*/ int index1,index2,tempindex; /*index1为主要索引，index2为次要索引，tempindex为附加索引*/ double number,a,b,c; /*number为整合数，a、b、c为运算数*/ Init_OdStack(&OdStack); /*初始化数栈*/ Init_OpStack(&OpStack); /*初始化符栈*/ inde

13、x1=0; /*初始化索引，附加索引*/ index2=0; tempindex=0; tempexp0=0; /*初始化整合数组*/ while(exp1index1!=0) /*处理初始表达式转化成后缀表达式*/ if(exp1index1=0& exp1index1=0& exp1index1=tempsign.level) /*当栈中符的等级大于当前等级时则取出符存入后缀表达式*/ exp2index2=OpPop(&OpStack).Type; index2+; exp2index2= ; /*每两个运算符之间用空格分开*/ index2+; OpPush(&OpStack,&tem

14、psign); /*结束后将当前运算符入栈*/ index1+; else if(exp1index1=() /*如果是左括号则无条件进栈*/ tempsign.Type=exp1index1; tempsign.level=-1; /*进栈后等级为-1，以便遇到右括号出栈*/ OpPush(&OpStack,&tempsign); index1+; else if(exp1index1=) /*右括号规则*/ while(OpPeek(&OpStack).level != -1) /*遇到右括号则不断出栈存入后缀表达式直到寻到左括号*/ exp2index2=OpPop(&OpStack).

15、Type; index2+; exp2index2= ; /*每两个运算符之间用空格分开*/ index2+; OpPop(&OpStack); /*直到遇到左括号将左括号出栈*/ index1+; else /*如果输入了非法字符则报错退出程序*/ Error(); while(OpPeek(&OpStack).level !=0) /*原表达式结束后对栈进行操作直到栈空*/ if(OpPeek(&OpStack).level=-1) /*如果有为用掉的左括号则报错退出程序*/ Error(); exp2index2=OpPop(&OpStack).Type; index2+; exp2in

16、dex2= ; index2+; exp2index2=0 ; /*最后结束后缀表达式*/ printf(nThe Post Expression is : n %s,exp2); /* 得到后缀表达式 */ index1=0; /*索引归零，开始计算结果*/ while(exp2index1 != 0) /*循环直到后缀表达式结束*/ if(exp2index1=0& exp2index1=0& exp2index1=9) | exp2index1=. ) /*用附加索引判断数的长度并整合入整合数组*/ tempexptempindex=exp2index1; index1+; tempin

17、dex+; tempexptempindex=0; /*结束整合数组*/ if( tempexp0 != 0) /*如果整合数组有值则转换成浮点型存入数栈*/ number = atof(tempexp); OdPush(&OdStack ,number); tempexp0=0; /*入栈后初始化整合数组和附加索引以便下次整合*/ tempindex=0; else if(exp2index1= ) /*判断空格，有则跳过*/ while(exp2index1= ) index1+; else if(exp2index1=+|exp2index1=-|exp2index1=*|exp2ind

18、ex1=/|exp2index1=%) /*对加减乘除和取模进行运算*/ a=OdPop(&OdStack); b=OdPop(&OdStack); tempch=exp2index1; c=Oper(a,b,tempch); OdPush(&OdStack,c); /*将计算结果放入数栈*/ index1+; return OdPop(&OdStack) ; /*弹出结果*/main() char strN; /*定义数组以存储表达式*/ double result; /*定义result以存储结果*/ printf(Please Enter the Expression:n); scanf

19、(%s,str); result=Calu(str); /*计算表达式并返回结果值*/ printf(nThe result is : n %f,result); getch();下面给出的是用边转换边运算的算法实现的程序的源代码：#include#include#define N 100/*N为数栈和表达式数组容量*/#define M 50/*M为符栈和其他数组容量*/typedef struct /*定义运算符类型，level为运算符等级*/ char Type; int level;Type;typedef struct /*定义数栈*/ double stackN; int top;

20、OdStack;typedef struct /*定义符栈*/ Type stackM; int top;OpStack;void Init_OdStack(OdStack *s) /*定义初始化数栈*/ (*s).top=0; void OdPush(OdStack *s,double n) /*进数栈*/ if(*s).top=N-1) /*如果栈满则报错退出程序*/ Error(); (*s).stack(*s ).top=n; (*s).top+;double OdPop(OdStack *s) /*定义出数栈*/ if (*s).top=0) /*如果栈空则报错退出程序*/ Erro

21、r(); else (*s).top-; return (*s).stack(*s).top; void Init_OpStack(OpStack *s) /*定义初始化符栈*/ (*s).top=0; void OpPush(OpStack *s,Type *sign) /*定义进符栈*/ if(*s).top=M-1) /*如果栈满则报错退出程序*/ Error(); (*s).stack(*s).top=*sign; (*s).top+;Type OpPop(OpStack *s) /*定义出符栈*/ if (*s).top=0) /*栈空则报错退出程序*/ Error(); else

22、(*s).top-; return (*s).stack(*s).top; Type OpPeek(OpStack *s) /*定义看符栈顶*/ Type ren; if (*s).top=0) /*判栈空，空则赋等级0值*/ ren.level=0; return ren; else return (*s).stack(*s).top-1;int Error() /*报错函数*/ printf(Error!); getch(); exit(1);int Com(char tempch) /*定义运算符等级*/ int level; /*给不同运算符定级*/ switch (tempch) c

23、ase +: case -:level=1;break; case *: case /: case %:level=2;break; return level;double Oper(double a,double b,char tempch) /*定义运算过程*/ double ren; 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

24、; /*取模运算将数取整*/ return ren;double Calu(char *exp) /*定义计算过程，依次读入字符*/ OdStack OdStack; /*定义数栈*/ OpStack OpStack; /*定义符栈*/ Type tempsign; /*定义Type型运算符*/ char tempexpM,tempch; /*定义整合数组tempexp，tempch为运算符*/ int index,tempindex; /*index为索引，tempindex为附加索引*/ double number,a,b,c; /*number为整合数，a、b、c为运算数*/ Init_

25、OdStack(&OdStack); /*初始化数栈*/ Init_OpStack(&OpStack); /*初始化符栈*/ index=0; /*初始化索引，附加索引*/ tempindex=0; tempexp0=0; /*初始化整合数组*/ while(expindex!=0) /*执行操作直到表达式结束*/ if(expindex=0& expindex=0& expindex=tempsign.level) /*当栈中符的等级大于当前等级时则取出符进行运算*/ tempch=OpPop(&OpStack).Type; a=OdPop(&OdStack); b=OdPop(&OdSta

26、ck); c=Oper(a,b,tempch); OdPush(&OdStack,c); /*将计算结果放入数栈*/ OpPush(&OpStack,&tempsign); /*直到无法运算将当前符放入栈中*/ index+; else if(expindex=() /*如果是左括号则无条件进栈*/ tempsign.Type=expindex; tempsign.level=-1; /*进栈后等级为-1，以便遇到右括号出栈*/ OpPush(&OpStack,&tempsign); index+; else if(expindex=) /*右括号计算*/ while(OpPeek(&OpSt

27、ack).level!=-1) /*遇到右括号则计算直到左括号*/ tempch=OpPop(&OpStack).Type; /*取出两个数和一个符进行计算*/ a=OdPop(&OdStack); b=OdPop(&OdStack); c=Oper(a,b,tempch); OdPush(&OdStack,c); /*将计算结果放入数栈*/ OpPop(&OpStack); /*直到遇到左括号将左括号出栈*/ index+; else /*如果输入了非法字符则报错退出程序*/ Error(); while(OpPeek(&OpStack).level!=0) /*表达式结束后对栈进行操作直到

28、栈空*/ if(OpPeek(&OpStack).level=-1) /*如果有为用掉的左括号则报错退出程序*/ Error(); tempch=OpPop(&OpStack).Type; /*取出两个数和一个符进行计算*/ a=OdPop(&OdStack); b=OdPop(&OdStack); c=Oper(a,b,tempch); OdPush(&OdStack,c); /*将计算结果放入数栈*/ return OdPop(&OdStack) ; /*弹出结果*/main() char strN; /*定义数组以存储表达式*/ double result; /*定义result以存储结

29、果*/ printf(Please Enter the Expression:n); scanf(%s,str); result=Calu(str); /*计算表达式并返回结果值*/ printf(nThe result is : n %f,result); getch(); 四、运行结果中缀转后缀的运行结果图和判错图：图4 中缀转后缀运行结果图图5 中缀转后缀括号不匹配图边转换边计算的运行结果图和判错图：图6 边转换边计算运行结果图图7 边转换边计算错误字符图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 第一个问题是中缀转后缀时的数字元素整合问题解决办法：

30、一开始一直在纠结于如何在中缀转后缀时把数字元素整合后和运算符一起放入后缀表达式中，因为整合后的数是浮点型，而运算符是字符型。首先想到的解决办法是建立两个数组，一个是浮点型数组用来存储整合后的数，一个是字符型的数组用来存储运算符。两个数组使用同一个索引。当遇到数的时候进数组，符组读入空格；当遇到的是运算符的时候进符组，数组读入空格。当输出后缀表达式的时候，索引依次扫描，当在数组或符组中遇到的是元素时输出，当时空格时输出后转到另一个组索引。部分程序如下：num20,char20;/*num存储了整合数，char存储了字符，一下为输出后缀操作*/while (i!=0)if (numi!= )printf(%f ,numi);i+; else i+;if (chari!= )printf(%f ,numi);i+;else i+;但是方法过于繁琐，程序过于冗长，后来通过多次分析发现如果在转换的时候不整合数字就可以使用一个字符型数组进行存储后缀表达式，并且输出的时候也简单了些。只需要在后缀运算的时候整合就可以了。以下为最后修改的将中缀中的数存入后缀表达式的程序：if(exp1index1=0& exp1index1=0& exp1ind