《用栈实现表达式计算》由会员分享，可在线阅读，更多相关《用栈实现表达式计算（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；否则，继续判断。若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素为（或者栈顶元素为+或并且现有元素为*、/或%又或是现有元素为（，则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为），运算符出栈直到（出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Ju
5、dge()函数,并将函数的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。（4）Judge()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。二、算法流程图 算法一： 利用栈将中缀表达式转化成后缀表达式再进行计算。 图1为算法一中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。是否是将一个#号传给数组str_pass元素不是数字或.传给数组str
6、_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中缀转后缀表达式算法countfor()函
8、数流程图算法二： 利用两个栈（数字栈和符号栈）直接对表达式求值。 图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 10/存储空间
11、初始分配量#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.top=S.ba
12、se; 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.stacksize+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 DestroyS
