用栈实现表达式计算

《用栈实现表达式计算》由会员分享，可在线阅读，更多相关《用栈实现表达式计算（23页珍藏版）》请在装配图网上搜索。

1、用两种方式实现表达式自动计算一、设计思想算法一： 利用栈将中缀表达式转化成后缀表达式再进行计算。（1）构造char类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Min_Back()）。（3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表达式转换成后缀表达式的函数。函数中利用

2、构建的栈以及栈的相关函数对运算符进行操作：先看栈顶，如果栈为空或栈顶元素为（或者栈顶元素为+或并且现有运算符为*、/或%又或是现有运算符为（，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为），运算符出栈直到（出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。循环结束后，将栈中的运算符全部依次输出，最后将后缀表达式传递给求值函数（countfor()），再销毁栈。（4）求值函数中首先是利用strtod()函数将数字字符串转换成double类型的数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当遇到运算符时，就从数字栈中“扔出”两个数字进行相应的

3、运算，循环结束后，将数字栈中的数字“扔出”，并输出成为表达式最终的结果。算法二： 利用创建的两个栈直接对表达式进行计算。（1）分别构建一个char类型和一个double类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Countfor ()）。（3）在Countfor()函数中先创建一个数字栈和

4、一个符号栈，对表达式进行循环，直到元素为0。在循环中如果元素为数字、点或者#，将元素赋给新的数组Consist，再判断下一个元素是否为#，若是则利用strtod()函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组Consist；否则，继续判断。若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素为（或者栈顶元素为+或并且现有元素为*、/或%又或是现有元素为（，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为），运算符出栈直到（出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算

5、符一起传递给Judge()函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。（4）Judge()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。二、算法流程图 算法一： 利用栈将中缀表达式转化成后缀表达式再进行计算。 图1为算法一中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。是否是将一个#号传给数组str_pass元素不是数字或

6、.传给数组str_pass，原数组下脚标+1否传给数组str_pass将新的表达式传递给Countfor ()函数是对表达式进行循环开始用户输入表达式元素为0元素为数字或.否结束图1 中缀转后缀表达式算法main()函数流程图图2为算法一中Mid_Back()函数的算法流程图，主要功能为：将中缀表达式转换成后缀表达式。将栈进行循环栈不为空否是输出后缀表达式结束将表达式传给求值函数countfor()运算符出栈否声明并创建一个栈开始对表达式进行循环将元素传给数组Ba_str是是现有元素不为=元素为数字、点或者#看栈顶是元素进栈否栈为空或栈顶为(或+、-且元素为*、/、%或者元素为(元素为)出栈直

7、到(出栈是否出栈并赋给Ba_str看栈顶是元素进栈否出栈，将现有元素进栈否栈为空或栈顶为(或+、-且元素为*、/、%或者元素为(图2中缀转后缀表达式算法Mid_Back()函数流程图图3为算法一中countfor()函数的算法流程图，主要功能为：根据后缀表达式求出表达式的值。清空数组Consist()调用strtod()函数，结果进栈运算结果进栈将元素赋给Consist下一个元素为#是否利用switch()语句判断运算符并进行相应运算元素为数字、点或者#是是否从数字栈中“扔出”两个数开始结束 输出结果声明并创建数字栈表达式最终结果出栈对表达式进行循环元素不为0否 图3中缀转后缀表达式算法cou

8、ntfor()函数流程图算法二： 利用两个栈（数字栈和符号栈）直接对表达式求值。 图4为算法二中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。是否是将一个#号传给数组str_pass元素不是数字或.传给数组str_pass，原数组下脚标+1否传给数组str_pass将新的表达式传递给Countfor ()函数是对表达式进行循环开始用户输入表达式元素为0元素为数字或.否结束图4表达式直接求值算法main()函数流程图图5为算法二中Countfor ()函数的算法流程图，主要功能为：利用两个栈直接对表达式进行取值计算。将出栈的两个数和一个运算符传给Judge()，

9、并将返回值压进数栈元素进栈将出栈的两个数和一个运算符传给Judge()，并将返回值压进数栈将出栈的两个数和一个运算符传给Judge()，并将返回值压进数栈否否是否栈为空或栈顶为(或+、-且元素为*、/、%或者元素为(否元素为)出栈直到(出栈是是元素进栈是清空数组Consist调用strtod函数，并将返回值压进数栈是是对表达式进行循环开始声明并创建一个数字栈和一个符号栈元素不为=否结束对符号栈进行循环表达式最终结果出栈符号栈非空否输出结果将出栈的两个数和一个运算符传给Judge()，并将返回值压进数栈元素为数字、点或者#将元素传给数组Consist是元素为#否栈为空或栈顶为(或+、-且元素为*

10、、/、%或者元素为(图5表达式直接求值算法Countfor ()函数流程图图6为算法二中Judge()函数的算法流程图，主要功能为：判断运算符并根据判断将两个数进行相应的计算，返回计算结果。开始 结束利用switch语句对传进来的运算符进行判断并根据判断对两个数字进行相应的运算返回运算结果图6表达式直接求值算法Judge()函数流程图三、源代码下面给出的是用一个栈对表达式中缀转后缀再进行运算的算法实现的程序的源代码：#include stdafx.h#include stdio.h#include malloc.h#include stdlib.h#define STACK_INIT_SIZE

11、 10/存储空间初始分配量#define STACKINCREMENT 10/存储空间分配增量typedef struct/构建数字栈 double *base; /在栈构造之前和销毁之后，base的值为NULL double *top; /栈的顶指针 int stacksize; /当前已分配的存储空间，以元素为单位Od;void InitStack(Od &S)/创建一个栈 S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double);/分配类型为double if(!S.base) printf(OVERFLOW!); /存储分配失败 S.

12、top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Od S,double &e) /看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；否则，0 if(S.topS.base) /栈不空 e=*(S.top-1);/将栈顶元素赋给e return 1; else return 0; /GetTopvoid Push(Od &S,double e)/插入元素e为新的栈顶if(S.top-S.base=S.stacksize) /栈满，追加存储 S.base=(double*)realloc(S.base,(S.stack

13、size+STACKINCREMENT)*sizeof(double);if(!S.base) exit(0); /存储分配失败S.top=S.base+S.stacksize;/修改站顶指针，指向新的栈顶S.stacksize+=STACKINCREMENT;/更新当前已分配的存储空间 *(S.top)+=e; 将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元/Pushstatic Pop(Od &S,double &e)/删除S的栈顶元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStac

14、k(Od &S)/销毁栈S free(S.base);/释放栈空间 S.top=S.base=NULL;/栈顶、栈底指针均为空 S.stacksize=0;/当前已分配内存空间为0/DestroyStackstatic StackEmpty(Od S)/判断栈是否为空，栈空返回1，否则，返回0。 if(S.top=S.base) /空栈条件 return 1; else return 0;/StackEmptytypedef struct/构建字符栈 char *base;/在栈构造之前和销毁之后，base的值为NULL char *top;/栈的顶指针 int stacksize;/当前已分

15、配的存储空间，以元素为单位Op;void InitStack(Op &S)/创建一个栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/分配类型为char if(!S.base) printf(OVERFLOW!);/存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Op S,char &e)/看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；否则，0if(S.topS.base) e=*(S.top-1);/将栈顶元素赋给e return 1

16、; else return 0;/GetTopvoid Push(Op &S,char e)/插入元素e为新的栈顶 if(S.top-S.base=S.stacksize) /栈满，追加存储 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char);if(!S.base) exit(0);/存储分配失败S.top=S.base+S.stacksize; /修改站顶指针，指向新的栈顶S.stacksize+=STACKINCREMENT;/更新当前已分配的存储空间 *(S.top)+=e;/将e入栈，成为新的栈

17、顶元素，栈顶指针上移1个存储单元/Pushstatic Pop(Op &S,char &e)/删除S的栈顶元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Op &S)/销毁栈S free(S.base);/释放栈空间 S.top=S.base=NULL;/栈顶、栈底指针均为空 S.stacksize=0;/当前已分配内存空间为0/DestroyStackstatic StackEmpty(Op S)/判断栈是否为空，栈空返回1，否则，返回0。 if(S.top=S.base) /空栈条

18、件 return 1; else return 0;/StackEmptyint main(int argc, double* argv) void Mid_Back(char a);/中缀表达式转后缀表达式函数int i=0; /str数组的下脚标 int j=0; /str_pass数组的下脚标 char str50; /接受用户输入字符的数组 char str_pass50; /接受数字字符的数组 printf(请输入算数表达式：n); scanf(%s,&str); /输入表达式 while(stri!=0) /对str数组进行循环，知道stri为0 if(stri=0&stri=0&

19、stri=0&ai=0&Ba_stri=9)|Ba_stri=.|Ba_stri=#) /如果元素为数字、点或者#，则将元素赋给Consistj Consistj=Ba_stri; j+; i+; if(Ba_stri=#) /如果元素为# e=strtod(Consist,NULL);/利用strtod函数将字符串转换成double类型的数字 Push(Od,e);/数字进栈 for(j=0;jS.base) e=*(S.top-1); return 1; else return 0;/GetTopvoid Push(Od &S,double e)/插入元素e为新的栈顶 if(S.top-S

20、.base=S.stacksize) /如果栈满，追加存储 S.base=(double *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double); if(!S.base) exit(0); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)+=e;/Pushstatic Pop(Od &S,double &e)/删除S的栈顶元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/

21、Popvoid DestroyStack(Od &S)/销毁栈S free(S.base);/释放栈空间 S.top=S.base=NULL;/栈顶、栈底指针均为空 S.stacksize=0;/当前已分配内存空间为0/DestroyStackstatic StackEmpty(Od S)/判断栈是否为空，栈空返回1，否则，返回0。 if(S.top=S.base) /空栈条件 return 1; else return 0;/StackEmpty/*/typedef struct char *base;/在栈构造之前和销毁之后，base的值为NULL char *top;/栈的顶指针 int

22、 stacksize;/当前已分配的存储空间，以元素为单位Op;void InitStack(Op &S)/创建一个栈 S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);/分配类型为char if(!S.base) printf(OVERFLOW!);/存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE;/InitStackstatic GetTop(Op S,char &e) /看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；否则，0if(S.topS.base) e=*(S.top-1);

23、return 1; else return 0;/GetTopvoid Push(Op &S,char e)/插入元素e为新的栈顶 if(S.top-S.base=S.stacksize) /如果栈满，追加存储 S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char); if(!S.base) exit(0); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)+=e;/Pushstatic Pop(Op &S,cha

24、r &e)/删除S的栈顶元素，用e返回其值 if(S.top=S.base) return 0; e=*-S.top; return 1;/Popvoid DestroyStack(Op &S)/销毁栈S free(S.base);/释放栈空间 S.top=S.base=NULL;/栈顶、栈底指针均为空 S.stacksize=0;/当前已分配内存空间为0/DestroyStackstatic StackEmpty(Op S)/判断栈是否为空，是返回1，否则返回0。 if(S.top=S.base)/空栈条件 return 1; else return 0;/StackEmpty/*/int

25、main(int argc, double* argv) void Mid_Back(char a); int i=0; /str数组的下脚标 int j=0; /str_pass数组的下脚标 char str50; /接受用户输入字符的数组 char str_pass50; /接受数字字符的数组 void Countfor(char Min_str);/进行表达式运算的函数 printf(请输入算数表达式：n); scanf(%s,&str); /输入表达式 while(stri!=0) /对str数组进行循环，知道stri为0 if(stri=0&stri=0&stri=0&Min_str

26、i=9)|Min_stri=.|Min_stri=#)/判断Min_stri是否为数字或者点、#， Consistj=Min_stri; /是，则传入Consist数组，直至Min_stri为# j+; i+; if(Min_stri=#) /如果Min_stri为# eod=strtod(Consist,NULL);/利用strtod函数，将Consist数组中的字符串转换成double类型的数字 Push(Od,eod); /eod进栈 for(j=0;j20;j+)/将Consist数组循环清空 Consistj=0; j=0; else -i; else /Min_stri是运算符 G

27、etTop(Op,eop); /看栈 if(StackEmpty(Op)|eop=(|(eop=+|eop=-)&(Min_stri=*|Min_stri=%|Min_stri=/)| Min_stri=() Push(Op,Min_stri); /将栈中已有的运算符与现有的运算符进行比较 else if(Min_stri=) /如果现有的运算符为)， Pop(Op,eop); /则栈中的运算符出栈， for(;eop!=(;) /直到出栈的运算符为( Pop(Od,eod); /一个运算符出栈，数栈中就Pop出两个数，进行运算 Od2=eod; Pop(Od,eod); Od1=eod; e

28、od=Judge(eop,Od1,Od2);/对运算符进行判断，并根据判断进行运算 Push(Od,eod); /将函数的返回值压入进栈 Pop(Op,eop); else Pop(Op,eop); /运算符出栈Pop(Od,eod);/一个运算符出栈，数栈中就Pop出两个数，进行运算Od2=eod;Pop(Od,eod);Od1=eod;eod=Judge(eop,Od1,Od2); /对运算符进行判断，并根据判断进行运算 Push(Od,eod); /将函数的返回值压入进栈GetTop(Op,eop); /看栈顶if(StackEmpty(Op)|eop=(|(eop=+|eop=-)&(

29、Min_stri=*|Min_stri=%|Min_stri=/)|Min_stri=() Push(Op,Min_stri); else Pop(Op,eop); /运算符出栈 Pop(Od,eod);/一个运算符出栈，数栈中就Pop出两个数，进行运算 Od2=eod; Pop(Od,eod); Od1=eod; eod=Judge(eop,Od1,Od2); /对运算符进行判断，并根据判断进行运算 Push(Od,eod); /将函数的返回值压入进栈 Push(Op,Min_stri); for(;!StackEmpty(Op); /运算符出栈，直到栈空 Pop(Op,eop); /运算符

30、出栈 Pop(Od,eod); /一个运算符出栈，数栈中就Pop出两个数，进行运算 Od2=eod; Pop(Od,eod); Od1=eod; eod=Judge(eop,Od1,Od2); /对运算符进行判断，并根据判断进行运算 Push(Od,eod); /将函数的返回值压入进栈 Pop(Od,eod); printf(=%f,eod); /输出表达式最终结果 DestroyStack(Od); /销毁数字栈Od DestroyStack(Op); /销毁字符栈Opdouble Judge(char c_Operator,double Od1,double Od2) double eod

31、; switch(c_Operator) /判断c_Operator是什么运算符，并根据判断进行运算 case -:eod=Od1-Od2; break;/运算符为减号，则两数相减case +:eod=Od1+Od2; break; /运算符为加号，则两数相加case *:eod=Od1*Od2; break; /运算符为乘号，则两数相乘case /:eod=Od1/Od2;break; /运算符为除号，则两数相除case %:eod=(int)Od1%(int)Od2;break; /运算符为取余号，则两数相除取余/ degault: return eod; /返回运算结果四、运行结果算法一

32、： 利用栈将中缀表达式转化成后缀表达式再进行计算。 将表达式“3.4+2*（32-54/9）-7%5+3=”录入，先将中缀表达式转化成后缀表达式，#是为了区分数字与符号，得到结果为“56.400000”，为正确结果。 图7 中缀表达式转化成后缀表达式再进行计算算法的运行结果图 算法二： 利用创建的两个栈直接对表达式进行计算。 将表达式“3.4+2*（32-54/9）-7%5+3=”录入，得到结果为“56.400000”，为正确结果。图8 两个栈直接对表达式进行计算算法的运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 在第二个算法（表达式直接求值）中输

33、入表达式后，运算结果不正确： 图9 遇到的问题1问题1的解决方法：先判断“病根”在哪里，首先在数字栈和符号栈的Pop()函数和Push()函数中分别加输出语句，观察数字与字符是否正常出入栈，具体如图10。 图10 解决问题1中，在栈中添加输出语句再次运行后，结果如图11。图11 解决问题1中，在栈中添加输出语句后的运行结果根据图11，可判断出第一个数字1并没有成功的入栈反而被替换成了0，造成这样结果的原因可能有以下几点：（1）在算法的main()函数中，在对表达式中数字字符与运算符进行区分操作时，由于考虑的不全面产生逻辑错误，这会使得在接下来的运行中在靠#来辨别语速的函数中会产生错误；（2）在

34、算法的Countfor()函数中，运算符优先级的判别可能出现逻辑性错误，使得运算不正确；（3）在算法的Countfor()函数中，运用strtod()函数方法不正确，使得字符类型转化成double类型是发生错误，然后再将错误的数字传进栈中。根据判断依次进行调试，首先在main()函数中对代码进行检验，观察是否有逻辑性错误，结果发现在对表达式中数字字符与运算符进行区分操作时，没有考虑到元素为(和元素为)时的情况，使得在添加#号时（前和）后都添加了#，而这是不符合设计思想的，所以进行调节：在判断了当前元素是为数字或者点之后，在对下一个元素进行判断，看其是否为运算符，如果是则添加#号，如果不是就继续

35、循环。在对代码进行一番修改之后再运行，运行结果正常，说明问题解决了。l 在第一个算法（中缀表达式转后缀表达式再求值）中输入表达式（769+6*（1+1）=）后，中缀表达式转后缀表达式结果不正确+号应该在前，如图12。图12 遇到的问题2问题2的解决方法：如同解决问题一一样，判断“病根”在哪里，首先在数字栈和符号栈的Pop()函数和Push()函数中分别加输出语句，观察数字与字符是否正常出入栈，具体如图10。再次运行后，结果如图13。图13 解决问题2中，在栈中添加输出语句后的运行结果根据图13所示，数字字符与运算符加#号区分正确，所以，可以排除main()函数在对表达式中数字字符与运算符进行区

36、分操作时，由于考虑的不全面产生逻辑错误，那么接下来考虑是否是Mid_Back()函数中判断符号优先级时，由于考虑的不全面而产生的逻辑性的错误。接下来针对猜想结合图13对程序进行测试运算，原来在对符号的优先级的判断中没有考虑到当栈“扔出”一个元素后，应将现有元素再与栈顶的元素进行优先级的比较，根据比较决定现有元素是否入栈和栈顶元素是否出栈。病因已经找到了，接下来就是对代码进行修改：当栈“扔出”一个元素后，再次对栈顶元素和现有元素进行比较，如果现有元素的优先级比栈顶元素的优先级高时，则现有元素进栈，继续循环；否则，栈顶元素出栈，现有元素进栈。经过修改，运行结果正常，说明问题解决了。六、心得体会 通

37、过这次的作业，我学到了很多东西：首先，我了解到怎样用一个栈将中缀表达式转换成后缀表达式和怎样用两个栈对表达式直接进行计算，并且能够用C语言去实现他们。然后，我学会了怎样用C语言构造不同类型的栈以及栈的相关函数。这次的作业，也让我重温了C语言这个学了好久也忘记的差不多的语言，我觉得我的编程能了较之以前有了小小的提高，在发现问题和解决问题上也有了一些经验，但我知道只有这些事远远不够的，我要在平时的学习中多多进行锻炼，以提高自己各个方面的能力，它还让我了解到运算符之间的优先级，比较优先级再对运算符进行操作，然后利用字符串转double类型的函数strtod()将数字字符串转换成double类型的数字。为了完成这次的作业，我首先利用几天的时间复习C语言的知识和刚刚学过的数据结构的知识，在编程中谨记老师的教诲，要慎思，考虑问题要全面。下以后的时间里，我要多多练习多多学习，了解不同方面的知识，充分的充实自己，不断地努力，提高自己的能力。- 23 -