c语言-数据结构-两种方式计算表达式(共17页)

1、用两种方式实现表达式自动计算一、设计思想计算表达式有两种方式，第一种是先算后缀表达式，再计算结果，第二种是直接计算中缀表达式求值，下面介绍两种方式的设计思想。（1）先算后缀表达式，再计算结果。程序先定义了两个栈odlist和oplist，分别用作数字栈和运算符栈，并用指针*od和*op访问这两个栈，同时定义两个栈的入栈、出栈和看栈顶的函数，再定义一个判断是否是操作符的函数int is_op()、一个比较运算符优先级的函数int level()和计算两个数字运算结果的函数double re()。主函数中定义字符型的数组inorder100和postorder100分别用于存放中缀表达式和转换后的

2、后缀表达式，整型的inpos和postpos分别表示中缀表达式的扫描索引和后缀表达式的扫描索引。然后进行中缀表达式转换为后缀表达式。用while循环扫描inorder100数组，如果是数字字符，直接将其逐个复制给postorderpostorder+，并在最后加一个空格用于和下一个数字区分；如果是运算符，此运算符优先级比op栈栈顶优先级大时直接入栈，否则将op栈栈顶取出放入postorderpostorder+中，直到此运算符比栈顶优先级高，然后将次运算符入栈；如果是左括号，无条件入栈；如果是右括号，将op栈的栈顶元素出栈并放入postorder100中，循环执行上面的操作，直到栈顶为右括号，

3、然后将左括号出栈。当while循环结束后，如果op栈不为空时，将op栈中的运算符逐个出栈并放入postorderpostorder+中。此时字符数组postorder100中存放的就是已经转换为后缀表示的表达式，每一串数字字符结束后，都在后面用空格分割开来，防止和下一个数字叠加。再下来进行进行后缀表达式的计算。用while循环扫描字符数组postorder100，只要不遇到0，就一直从0往后扫描。如果遇到数字，就用atof()函数将数字字符转换为double类型，并将此数字压入od栈中；如果遇到运算符，就从od栈中先后取出两个数字，先取出的在后面，后取出的在前面，用函数double re()计

4、算两个数的运算结果，将结果重新压入od栈中。当这个while循环结束后，od栈栈顶存放的就是后缀表达式的计算结果。最后将存放在od栈栈顶的结果赋值给double类型的result，并在屏幕上输出。（2）直接计算结果。程序先定义了两个栈odlist和oplist，分别用作数字栈和运算符栈，并用指针*od和*op访问这两个栈，同时定义两个栈的入栈、出栈和看栈顶的函数，再定义一个判断是否是操作符的函数int is_op()、一个比较运算符优先级的函数int level()和计算两个数字运算结果的函数double re()。主函数中定义字符类型的数组inorder100，用来表示中缀表达式，整型的in

5、pos用来表示数组inorder100的扫描索引。然后开始扫描中缀表达式。从0开始扫描中缀表达式所在的数组inorder100,直到遇到0结束。在扫描过程中，如果遇到数字字符，用函数atof()将这一串数字字符转换为double类型的数字，并压入od栈中；如果遇到运算符，先判断此运算符是否可以入栈，如果不可以，将栈顶出栈，同时从od栈总取出两个数字，先取出的放在出栈的运算符符号后面，后取出的放在出栈的运算符前面，计算两个数字的运算结果，并将计算结果重新压入od栈中，重复执行上面的操作，直到此操作符可以入栈，然后将这个操作符压入op栈中。此while循环结束后，中缀表达式已经扫描完毕，数字和运算

6、符存储在栈中。接下来进行清空op栈的操作。如果op栈不为空，则将op栈栈顶出栈，同时从od栈中取出两个数字，先取出的放在出栈的运算符符号后面，后取出的放在出栈的运算符前面，计算两个数字的运算结果，并将计算结果重新压入od栈中，重复执行上面的操作，直到op栈为空。此while循环结束后，od栈栈顶中存放的就是中缀表达式的运算结果。最后将od栈栈顶元素的值赋值个double类型的result，并在屏幕上输出。二、算法流程图下面分别是两种算法的详细流程图：（1）先算后缀表达式，再算结果的算法流程图。是运算符是右括号是左括号是否能入op栈是0是运算符是数字字符否是扫描索引加1扫描索引加1是否否扫描索引

7、加1是数字字符op栈出栈，与od栈两数计算，结果压入od栈后缀表达式转换完成，进行计算判断运算符运算结束，输出栈顶结果转为数字压入od栈能入op栈入栈op栈出栈，与od栈两数计算，结果压入od栈结束op栈不是空字符不等于0表达式扫描完成继续扫描表达式开始接收表达式字符逐个复制给postorder，最后加空格入op栈判断运算符出栈计算，直到栈顶是左括号左括号出栈入op栈op栈顶出栈，复制到postorder图1 先算后缀，再算结果的算法流程图（2）直接计算的算法流程图。开始结束接收表达式字符不等于0继续扫描表达式判断运算符入op栈是左括号是数字字符字符转换为数字，压入od栈是右括号是运算符op栈

8、出栈，直到栈顶为左括号左括号出栈能入op栈运算符入op栈op栈顶出栈，od栈依次出两数，计算结果压入od栈中是否是否表达式扫描完成op栈是空计算表达式完成，od栈顶出栈，并在屏幕上输出是扫描索引加1否op栈顶出栈，od栈依次出两数，计算结果压入od栈中图2 直接计算的算法流程图三、源代码下面给出的是先算后缀表达式，再计算结果的程序的源代码：/*/* 程序名称：stack_1.c */* 计算多项式，先求后缀表达式，再求结果*/*/#include stdio.h#include string.h#include stdlib.h#define MAX 100/*定义栈的最大长度*/struct

9、 opnode/*声明op栈*/char str100;int top_op;struct odnode/*声明od栈*/double num100;int top_od;void push_op(struct opnode *op,char c) /*op栈的进栈函数*/if(op-top_op=MAX-1) /*如果栈为满，不进行操作*/else /*如果栈不满，进行压栈操作*/op-top_op+;op-strop-top_op=c;void pop_op(struct opnode *op)/*op栈的出栈函数*/if(op-top_optop_op-;char top_op(stru

10、ct opnode *op)/*op栈的看栈顶函数*/return(op-strop-top_op); /*/void push_od(struct odnode *od,double d)/*od栈的进栈操作*/if(od-top_od=MAX-1)/*如果栈为满，不进行操作*/else/*如果栈不为满，进行进栈操作*/od-top_od+;od-numod-top_od=d;void pop_od(struct odnode *od) /*od栈的出栈函数*/if(od-top_odtop_od-; /*使od栈的top_od-1*/double top_od(struct odnode

11、*od) /*od栈的看栈顶的函数*/return(od-numod-top_od); /*判断是否为运算符*/int is_op(char op)/*定义函数判断是否是运算符，返回整型*/switch(op)/*用switch函数选择，op为运算符*/case (:return 1;break;case ):return 1;break;case +:return 1;break;case -:return 1;break;case *:return 1;break;case /:return 1;break;case %:return 1;break;/*如果是操作符，返回1*/defau

12、lt:return 0;break;/*如果不是操作符，返回0*/*判断运算符优先级*/int level(char op)/*定义函数判断运算符的栈内优先级，返回整型*/switch(op)case #:return 0;break;/*#为op栈初始时的栈底元素*/case ):return 0;break;/*如果是#或），返回0*/case (:return 1;break;/*如果是（，返回1*/case +:return 2;break;case -:return 2;break;/*如果是+或-，返回0*/case *:return 3;break;case /:return 3

13、;break;case %:return 3;break;/*如果是/、*或%，返回3*/default:return 0;break;/*否则返回0*/*定义函数，用于计算两个数的加减乘除*/double re(double a,double b,char op)switch(op)case +:return a+b;/*返回a和b的和*/break;case -:return a-b;/*返回a和b的差*/break;case *:return a*b;/*返回a和b的积*/break;case /:if(b=0.0)return 0;/*返回a和b的商*/ else return a/b

14、;/*如果b=0，返回0，计算会出错，但程序不会强行终止*/break;case %:return (int)a%(int)b;/*返回a取余b的值*/break;default:return 0;break;/*否则返回0*/void main() char c; char inorder100;/*中缀表达式*/ char postorder100;/*后缀表达式*/ int inpos,postpos;/*表达式被扫描的位置*/ int i; double od_a,od_b,result;/*用于后缀表达式计算*/ char *p=NULL;/*字符转换为double时的指针*/str

15、uct opnode oplist;/*定义op栈oplist*/struct opnode *op;/*定义op栈的指针*/struct odnode odlist;/*定义od栈odlist*/struct odnode *od;/*定义od栈的指针*/op=&oplist;/*通过op指针访问oplist栈*/od=&odlist;/*通过od指针访问odlist栈*/ op-str0=#; /*作为栈低，当进行op栈的入栈操作时，不用再判断栈空*/ op-top_op=0;/*op栈栈顶指针为0*/ od-top_od=-1;/*od栈栈顶指针为-1*/ printf(输入一个中缀表达

16、式(先算后缀表达式,再计算):n);gets(inorder); /*获取一个中缀表达式*/ /*完成中缀变后缀，仍然用字符表示数字，存储在字符数组postorder100中*/ inpos=0,postpos=0;/*初始化扫描位置*/ while(inorderinpos!=0)/*/ c=inorderinpos; if(c=0&c=0&inorderilevel(top_op(op)|c=() /*操作符优先级高或者是(,将操作符压栈*/ push_op(op,c); else if(c=)/*操作符是),出栈到有(为止*/ while(top_op(op)!=()/*从op栈中取出的

17、操作符，除(*/ /*外，依次放入postorder100中*/ postorderpostpos+=top_op(op); pop_op(op); pop_op(op);/*将(从op栈中去掉*/ else if(level(c)=level(top_op(op) /*如果此操作符优先级低于栈顶元素*/ while(level(c)top_op0)/*如果栈此时不为空，一直出栈直到栈空*/ /*op栈栈底为#,不是操作符，不用取出*/ postorderpostpos+=top_op(op); pop_op(op); postorderpostpos=0;/*postorder100最后用0

18、作为结束标志*/ /*计算后缀表达式，取出字符时再转换为double类型*/ op-str0=#; /*再次重置栈，栈底放入#,栈顶指针为0*/ op-top_op=0; i=0;/*postorder100的扫描位置索引，赋值为0*/ while(i=0&c=0&postorderitop_op=MAX-1)/*如果栈满，不进行操作*/else/*否则，进行进栈操作*/op-top_op+;op-strop-top_op=c;void pop_op(struct opnode *op)/*定义op栈的出栈函数*/if(op-top_optop_op-;char top_op(struct o

19、pnode *op)/*定义op栈的看栈顶的函数*/return(op-strop-top_op); /*/void push_od(struct odnode *od,double d)/*定义od栈的进栈函数*/if(od-top_od=MAX-1)/*如果栈为满，不进行操作*/else/*否则，进行进栈操作*/od-top_od+;od-numod-top_od=d;void pop_od(struct odnode *od)/*定义od栈的出栈函数*/if(od-top_odtop_od-;double top_od(struct odnode *od)/*定义od栈看栈顶的函数*/r

20、eturn(od-numod-top_od); /*判断是否为运算符*/int is_op(char op)/*op为运算符*/switch(op)/*用switch语句判断*/case (:return 1;break;case ):return 1;break;case +:return 1;break;case -:return 1;break;case *:return 1;break;case /:return 1;break;case %:return 1;break;/*如果是运算符，返回1*/default:return 0;break;/*否则，返回0*/*判断运算符优先级*

21、/int level(char op)/*op为运算符*/switch(op)/*用switch语句判断，返回值为运算符的栈内优先级*/case #:return 0;break;/*#作为栈底元素*/case ):return 0;break;/*如果是#或)，返回0*/case (:return 1;break;/*如果是（，返回0*/case +:return 2;break;case -:return 2;break;/*如果是+或-，返回2*/case *:return 3;break;case /:return 3;break;case %:return 3;break;/*如果是

22、*,/或%，返回3*/default:return 0;break;/*计算*/double re(double a,double b,char op)/*计算两个浮点数的运算结果*/switch(op)/*用switch语句判断，op为运算符*/case +:return a+b;/*返回a和b的和*/break;case -:return a-b;/*返回a和b的差*/break;case *:return a*b;/*返回a和b的积*/break;case /:if(b=0.0)return 0;/*返回a和b的商*/else return a/b; /*如果b=0，返回0，计算结果出错

23、，但程序不会强行终止*/break;case %:return (int)a%(int)b;/*返回a取余b的结果*/break;default:return 0;break;/*否则，返回0*/ /*主函数*/void main() int i,inpos;/*inpos是inorder100的扫描索引*/ char inorderMAX;/*用于存储表达式*/ char c,*p=NULL;/*atof()函数所用的指针*/ double a,b,result; char temp_op;struct opnode oplist;/*定义op栈*/struct odnode odlist;

24、/*定义od栈*/struct opnode *op;/*定义op栈的指针*/struct odnode *od;/*定义od栈的指针*/op=&oplist;od=&odlist;od-top_od=-1;/*初始化od栈*/op-top_op=-1;/*初始化op栈*/c=#;push_op(op,c);/*向op栈栈底放入#，用于进栈时判断优先级*/printf(输入一个中缀表达式(直接计算):n);/*提示信息*/gets(inorder);/*接收表达式*/*扫描表达式*/i=0;/*i作为扫描inorder100的辅助索引*/inpos=0;/*初始化扫描索引*/c=inorder

25、inpos;while(c!=0)/*用while循环扫描数组inorder100*/c=inorderinpos;i=inpos;if(c=0&c=0&inorderilevel(top_op(op)|c=()/*如果操作符优先级大，压入op栈中*/push_op(op,c);else if(c=)/*如果操作符是)*/temp_op=top_op(op);while(temp_op!=()/*从op栈中出栈，直到栈顶为(*/temp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);p

26、op_od(od);/*从od栈中依次取出两个数字*/result=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*将结果压入od栈中*/temp_op=top_op(op);pop_op(op);/*将(出栈*/else if(level(c)=level(top_op(op)/*如果操作符优先级低*/dotemp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);pop_od(od);/*从od栈中依次取出两个数字*/result

27、=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*将结果压入od栈中*/while(level(c)top_op0)/*如果op栈中还有操作符*/temp_op=top_op(op);pop_op(op);/*从op栈中取出一个操作符*/b=top_od(od);pop_od(od);a=top_od(od);pop_od(od);/*从od栈中依次取出两个数字*/result=re(a,b,temp_op);/*计算两个数字的运算结果*/push_od(od,result);/*将结果压入od栈中*/*此while循环结束后，计算表达式

28、结束，结果存放在od栈的栈顶*/result=top_od(od);/*从od栈中取出计算结果*/printf(中缀表达式:);/*提示信息*/puts(inorder);/*输出中缀表达式*/printf(结果=%f,result);/*输出结果*/printf(n按任意键退出!);/*提示信息*/getch();/*实现程序按任意键退出*/四、运行结果下面是两个程序的运行结果截图，第一个是先计算后缀表达式，再计算结果的程序截图，第二个是直接计算中缀表达式的程序截图。图3 先算后缀，再算结果的运行结果图图4 直接计算的运行结果图 五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解

29、决方法如下所列：l 1.程序在特定的情况下会计算错误，例如输入表达式3.14*（5+4）-5/2+5%2时，程序会正确的计算出3.14*（5+4）-5/2的值等于25.76，最后的输出结果却是24.76.图5 错误的运行结果图图6 错误的运行结果图我后来有连续输入了几个算式，发现只要在上面的算式后面加上的加减操作都会得到相反的结果，程序会将加操作变成减操作，将减操作变成加操作。但是输入算式5/2+5%2时，程序又得到了正确的结果。当输入其他的一般算式时，程序会计算出正确的结果，不会出现错误。我对源代码进行了细致的检查，没有发现比较明显的错误。当使用编译器自带的调试功能调试程序时，通过跟踪压入o

30、d栈中的数字，发现前几个计算结果都是正确的，但压入栈中的符号出现了错误，最后的加号变成了减号。我想原因可能出在符号进栈时的优先级判定上。我复习了关于中缀表达式转换为后缀表达式的符号进栈的规则，发现只有栈外符号优先级大于栈顶优先级时，才允许此符号入栈。在我的源程序中，我写成了只要站外符号优先级不小于栈顶优先级是，就允许此符号入栈。找到了问题，就要这是知道如何造成的。我通过自己演算，发现了问题：当扫描到了表达式中”5/2”后面的加号时，此时od栈中从栈底开始依次为：28.26-2.5，op栈的栈内只有一个元素为：减号，这个加号与栈中的减号优先级相同，这个加号被压入op栈中。于是，当程序扫描完表达式时，od栈中元素从栈底开始依次为：28.26-2.5-1，op栈中元素从栈底开始依次为：减号-加号。当从