C语言后缀表达式计算

《C语言后缀表达式计算》由会员分享，可在线阅读，更多相关《C语言后缀表达式计算（18页珍藏版）》请在装配图网上搜索。

1、word一、设计思想计算算数表达式并求值，采取的共有两种方法：1. 先将算数表达式转化为后缀表达式，然后对后缀表达式进展计算。2. 对算数表达式进展直接的计算。第一种算法这种解决方案又分为两步：在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式然后，对于得到的用户输入的字符串进展逐个的扫描，如果是数组或者小数点，如此直接存放到数组中，并且在后面参加一个分隔符，如果是操作符，如此和栈中的已存的进展比拟，如果比栈中的操作符的优先级高，如此直接入栈，如果优先级低或相等，如此栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，如此此操作符入

2、栈，然后扫描下一个字符，直到遇到字符串的完毕符号0，扫描完毕。数组中存的就是后缀表达式。得到后缀表达式后，进展计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进展扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进展计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。第二种算发首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进展扫描，如果是数字字符或者小数点，如此将字符转化为浮点数存到数栈里，如果是操作符，如此观察符号栈，如果栈顶元素的优先级低于观察的操作符，如此操作符入栈，如果栈顶元素的优先级高于

3、或者等于观察的操作符，如此从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进展相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，如此此操作符入栈，然后对下一个字符进展扫描。如果是左括号，如此不进展优先级的比拟，直接入栈，入栈后优先级为-1。如果是右括号，如此从数值栈中取两个操作数，符号栈中取出一个符号，然后进展计算后得数放入数栈中，不断进展此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描完毕后，计算也完毕了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。容错的算法简要：括号匹配：当扫描

4、到左括号是，左括号直接入栈，扫描到右括号时，如此左括号出栈，如果栈为空，如此右括号多，如果最后栈中还有括号，如此左括号多。给出错误提示。除数不为0：当扫描到/时，就判断其后面的数字是否为0，如果为0报错。取余运算：取余运算时，操作数判断是否为整数，不为整数报错。二、算法流程图第一种算法:先将表达式转化为后缀表达式，然后计算其主函数流程图为：得到用户输入的中缀表达式调用容错函数存在错误 报错并完毕无错调用函数得到后缀表达式后缀表达式的计算返回计算结果调用直接计算的函数返回直接计算的结果图1 主函数算法流程图其中将中缀表达式转化为后缀表达式的主要流程为：取得字符并判断如果是数字或小数点直接放入字符

5、数组中在其后参加分隔符如果是操作符与栈顶比拟判断哪类括号直接入栈右括号取出不为(从栈中取出操作符放入数组直接入栈优先级高于栈顶如果是括号出栈存入数组中左括号优先级不高于栈顶图2 中缀转化为后缀算法流程图后缀表达式的计算，实现的流程图为：从数栈取2个数做相应计算结果存入数栈判断符号类型得到后缀表达式数字字符操作符转化为浮点数入栈从数栈中取出计算结果作为返回值图3 后缀表达式计算算法流程图下面介绍直接计算出结果的算法的实现：栈非空栈空低于栈顶高于栈顶NOYES左括号得到中缀表达式从字符串中取出一个字符判断字符类型数字字符操作符转化为浮点数入栈括号括号类型直接入栈右括号从栈中取出操作符是否为丢弃放入

6、数组与栈顶比拟直接入栈取出栈顶两个数作相应计算结果存入数栈符号栈是否为空将数值栈顶返回取栈顶符号与2个数计算，结果存入数值栈图4 直接计算中缀表达式算法流程图三、源代码下面给出的是用先转后缀再计算和直接计算的算法实现的程序的源代码：#include /*导入需要用到的各种包*/#include#includetypedef struct /*定义结构体用来存储操作符*/char op; /*存储字符*/int level; /*存储优先级*/OpNode;typedef struct OpNode op100; int top; int size; /*表示栈内元素的个数*/ stack; /

7、*定义符号栈*/void init(stack *st) /*初始化栈*/ st-size=0; st-top=0;OpNode pop(stack *a) /*出栈*/ if (a-size=0) /*如果栈为空完毕操作*/ exit(-1); a-size-; return a-op-(a-top); /*取出栈顶元素*/void push(stack *a,OpNode op) /*入栈函数*/ a-size+; a-op(a-top)+=op;OpNode top(stack *a) /*观察栈顶函数*/ if (a-size=0) /*如果栈为空完毕操作*/ printf(stack

8、 is emptyn); exit(-1); return a-op(a-top)-1; /*只得到栈顶的值而不出栈*/typedef struct /*定义数值栈*/ double num100; int top; /*栈顶指针*/ int size; numstack;void init2(numstack *st) /*初始化数值栈*/ st-size=0; st-top=0;double pop2(numstack *a) /*数值栈出栈*/ if (a-size=0) /*出栈前的判空*/ exit(-1); a-size-; return a-num-(a-top); /*得到栈顶

9、的值*/void push2(numstack *a,double num) /*入栈*/ a-size+; a-num(a-top)+=num;void main() /*主函数*/ void change (char str,char exp); /*声明要用到的各个函数*/ double CalResult(char exp); /*声明后缀表达式的计算函数*/ double Directcalresult(char str); int check(char str,char chestr100); char str100,exp100,chestr100; /*str存储原算术表达式，

10、exp存储对应的 printf(算术表达式为:n);后缀表达式,chestr存储容错字符*/ gets(str); if(check(str,chestr) /*调用容错函数*/ printf(表达式错在：n); printf(%sn,str); printf(chestr); /*根据输入情况指出错误的地方*/ exit(-1); change(str,exp); /*调用函数将中缀转化为后缀*/ printf(后缀表达式为:%sn,exp); printf(运算结果为： %fn,CalResult(exp); /*调用函数计算后缀表达式*/ printf(直接运算的结果为: %fn,Dir

11、ectcalresult(str); /*调用直接计算函数*/void change (char str,char ch) /*将前缀表达式转化为后缀表达式*/int i=0; /*str的索引*/int k=0;char c; /*字符串中取出的放在C中*/stack st; /*定义符号栈*/OpNode op;OpNode ops;init(&st); /*初始化符号栈*/c=stri+; while (c!=0) /*对字符串进展扫描*/if ( (c=0&c=0&c0) /*再次检查栈是否为空，*/op=top(&st); else break; /*为空就完毕*/pop(&st);

12、 /*去掉左括号*/if (c=+|c=-) /*如果是+-号*/ op.op=c;op.level=1; /*优先级为1*/ if (st.size=0)push(&st,op); /*如果此时栈为空直接入栈*/else ops=top(&st); /*观察栈顶*/ while (ops.level=op.level) /*如果栈顶优先级高*/ ops=pop(&st); chk+=ops.op; /*将栈顶元素取出存入数组中*/ if (st.size0)ops=top(&st); /*进展判空操作，栈为空完毕*/ else break; push(&st,op); /*此时栈顶优先级低，

13、入栈*/if(c=*|c=/|c=%) /*如果是*/进展*/op.op=c;op.level=2; /*优先级为1*/ if (st.size=0)push(&st,op); /*如果此时栈为空直接入栈*/else ops=top(&st); /*观察栈顶*/ while (ops.level=op.level) /*如果栈顶优先级高*/ ops=pop(&st); /*将栈顶元素取出存入数组中*/ chk+=ops.op; if (st.size0)ops=top(&st); /*进展判空操作，栈为空完毕*/ else break;push(&st,op); /*此时栈顶优先级低，入栈*/

14、c=stri+; /*索引自加检索下一个字符*/ while(st.size!=0) /*最后判断栈如果不为空*/ops=pop(&st); /*取出栈内元素存入数组中*/chk+=ops.op; chk=0; /*将0作为结尾存入数组*/double CalResult(char exp) /*后缀表达式的计算*/ char c; numstack numst; /*建立数值栈*/ double d1,d2,dr; int k=0; /*后缀表达式的索引*/ int i=0; /*将字符转化为浮点数的索引*/ char *s; char trans100; /*存字符表示的一段数字*/ in

15、it2 (&numst); /*实现数值栈*/ c=expk+; while (c!=0) /*开始扫描后缀表达式*/ if(c=+|c=-|c=*|c=/|c=%) /*如果是操作符*/ switch(c) case + : /*如果是加法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1+d2; /*相加后入栈*/ push2(&numst,dr); break; case - : /*如果是减法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1-d2; /*相减后入栈*/ push2(&numst,dr); br

16、eak; case * : /*如果是乘法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1*d2; /*相乘后入栈*/ push2(&numst,dr); break; case / : /*如果是除法操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=d1/d2; /*相除后入栈*/ push2(&numst,dr); break; case % : /*如果是取余操作*/ d2=pop2(&numst); d1=pop2(&numst); dr=(double)(int)d1%(int)d2); /*类型转化并取余后入

17、栈*/ push2(&numst,dr); break; if (c=0&c=0&c=9|c=.)transi+=c; /*将字符存入数组进展下一个的扫描*/c=expk+; transi+=0; /*将表示数字的字符串完毕*/ i=0;s=trans; /*将指针指向该数组*/d1=atof(s); /*利用函数将字符串转化为浮点数*/push2(&numst,d1); c=expk+; return pop2(&numst); /*最后结果将在数值栈中，取出作为返回值*/double Directcalresult(char str) /*表达式的直接计算出结果*/ stack ms; /

18、*建立符号栈*/ numstack mns; /*建立数值栈*/ double calculate(double od1,double od2,OpNode op); int index=0; /*str的索引*/ int len=strlen(str); char c; char trans100; /*存放数值的一段字符*/ int i=0; /*trans的索引*/ char * s; double d; OpNode tempn; /*存放当前扫描的操作符*/ OpNode templn; double oda,odb,odr; double result; /*作为返回值返回结果*/

19、 init (&ms); /*实现两个栈*/ init2(&mns); while(index=0&c=0&c=tempn.level) /*栈顶优先级高*/ templn=pop(&ms); /*取出操作数和操作符计算*/odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mns,odr); /*结算结果入栈*/ if(ms.size0) templn=top(&ms); /*如果栈空完毕*/ else break; push(&ms,tempn); /*操作符入栈*/ if(c=*|c=/|c=%) /

20、*如果是*/%操作*/ tempn.level=2; /*定义优先级为2*/ tempn.op=c; if(ms.size=0) push(&ms,tempn); /*栈空直接入栈*/ else templn=top(&ms); while (templn.level=tempn.level) /*栈顶优先级高*/ templn=pop(&ms); /*取出操作数和操作符计算*/ odb=pop2(&mns); oda=pop2(&mns); odr=calculate(oda,odb,templn); push2(&mns,odr); /*结算结果入栈*/ if(ms.size0) temp

21、ln=top(&ms); else break; /*如果栈空完毕*/ templn=top(&ms); push(&ms,tempn); /*操作符入栈*/ if(c=() /*如果是左括号*/ tempn.level=-1; tempn.op=c; /*直接入栈优先级定位-1*/ push(&ms,tempn); if(c=) /*如果是右括号*/ while(tempn.op!=() /*遇到左括号完毕*/ templn=pop(&ms); odb=pop2(&mns); /*从数栈中取两个数，从符号栈里取操作符*/ oda=pop2(&mns); odr=calculate(oda,o

22、db,templn); /*计算出结果入栈*/ push2(&mns,odr); if (ms.size0) tempn=top(&ms); else break; /*如果栈空完毕*/ pop(&ms); /*取出左括号*/ tempn=top(&ms); while(1) templn=pop(&ms); odb=pop2(&mns); /*从数栈中取两个数，从符号栈里取操作符*/oda=pop2(&mns); odr=calculate(oda,odb,templn); /*计算出结果入栈*/ push2(&mns,odr); if (ms.size0)tempn=top(&ms); /

23、*如果栈空完毕*/ else break; result =pop2(&mns); /*最后的结果在数值栈中返回*/ return result;double calculate(double od1,double od2,OpNode op) /*操作符和操作数的计算*/switch(op.op) case + : return od1+od2; case - : return od1-od2; /*判断操作符是哪个执行相应计算*/ case * : return od1*od2; case / : return od1/od2; case % : return (double)(int)o

24、d1%(int)od2);return 0; /*如果上面的都没有执行返回0*/int check(char str,char chestr100) /*容错函数*/ char c; char cdivide; int i=0; /*str的索引*/ stack che; /*括号匹配用到的栈*/ OpNode temp; int k=0; /*chestr的索引*/ int isinteger(char integer100); /*%计算是判断是否是整数*/ char s110; /*%操作时存储%左右的数字*/ char s210; int indexs1=0; /*s1s2的索引*/

25、int indexs2=0; init (&che); int flag=0; /*0没有出错1有错*/ int tag=0; c=stri; /*开始扫描*/ int j; /*数组chestr索引*/ for(j=0;j0) pop(&che); /*栈不为空就取出一个左括号*/ else flag=1; printf(缺少左括号n); /*否如此提示有错*/ chestri=; /*右括号下加*/ if(c=/) /*判断除数是否为0*/ j=0; cdivide=stri+1+j; /*取出除号后的数*/ while(cdivide=0&cdivide=0&stri-indexs1-1

26、=0&stri+indexs2+10) /*如果最后栈不为空*/ printf(缺少右括号n); /*栈中还有没配对的左括号报错*/ return flag; /*返回是否有错*/int isinteger(char integer100) /*判断数组内是否是整数*/int i=0; /*传过来的数组的索引*/char c;c=integeri+;while(c!=0) /*直到字符串最后扫描完毕*/ if(c=.) /*只要有一个字符为小数点就不是整数*/return 1;elsec=integeri+; /*扫描下一个*/return 0;四、 运行结果在输入表达式没有错误的情况下，可以

27、得到两种算法的运算结果为：图5 表达式正确时两种算法运行结果图如果表达式的输入有错误，运行结果分别如下：图6除数为0提示错误图2. 取余运算操作数不为整数：图7取余操作数不为整提示错误图3.括号匹配的问题：图8缺少左括号提示错误图图9缺少右括号提示错误图五、遇到的问题与解决在编程的时候总是会有很多的意想不到的为题出现。这局部我主要遇到了如下两个问题，其内容与解决方法如下所列：l 将字符表示的数字转化为浮点数这个操作的主要目的就是数字是用一串字符表示的，在计算的过程中就要把字符串转化成对应的浮点数，要解决这个问题，首先查找C语言的库函数，其中找到一个可以将字符串转化为浮点数的函数atof()。那

28、么就需要将数值的一串字符存入预定的数组中。利用循环到时可以得到要求，但是总是出现如下情况： 图10 转化为浮点时的错误出现这种情况，首先确定后缀表达式是正确的，但在后缀表达式的计算时出现了错误，导致结果出错。检查程序，没有语法错误。逐步打印可以看到的结果，发现在利用atof后用printf函数打印时出现了错误，最后才发现是因为在每一次调用atof时都要将一串字符存入trans数组，可是，每次存储完毕时，却忘记将trans数组的索引重新设为0，这就导致了数组中是多个数都存到了数组中，然后就把数组转化为浮点数，导致了浮点数不是应得的数值。只要将trans的数组索引i每次都归零就可以了。l 在将中缀

29、转化为后缀表达式的过程中，得不到结果 得到用户输入的中缀表达式后调用函数，目的是得到后缀表达式 可是总是出现如下的情况：图11 转化为浮点时的错误由于学习C语言的时候使用的编译器是WIN TC而这次编程使用的是VC，询问过用VC的人之后才知道，如果字符串没有完毕符号就会“喊烫。检查程序后才知道，在将中缀转化为后缀的时候，在最后没有对字符串手动的参加0来表示完毕。因此，在程序的最后参加chk=0; 就可以了。六、心得体会大一就开始学习C语言，可是，当时学的时候就觉得语言好似是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一个不得不动手操作的机会，在十一的这几天中，复习了以前学过的C的根本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想方法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想方法自己解决，然后和好的方案进展比拟，从中找出自己的差距在哪里。18 / 18