用栈实现表达式计算.docx
《用栈实现表达式计算.docx》由会员分享，可在线阅读，更多相关《用栈实现表达式计算.docx（19页珍藏版）》请在冰点文库上搜索。
用栈实现表达式计算
一、设计思想
算法一：
利用栈将中缀表达式转化成后缀表达式再进行计算。
（1）构造char类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。
（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。
）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Min_Back（））。
（3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表达式转换成后缀表达式的函数。
函数中利用构建的栈以及栈的相关函数对运算符进行操作：
先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘—’并且现有运算符为‘*’、‘/’或‘%’又或是现有运算符为‘（’，则现有元素进栈；否则，再对现有元素进行判断：
如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。
循环结束后，将栈中的运算符全部依次输出，最后将后缀表达式传递给求值函数（countfor（）），再销毁栈。
（4）求值函数中首先是利用strtod（）函数将数字字符串转换成double类型的数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当遇到运算符时，就从数字栈中“扔出”两个数字进行相应的运算，循环结束后，将数字栈中的数字“扔出”，并输出成为表达式最终的结果。
算法二：
利用创建的两个栈直接对表达式进行计算。
（1）分别构建一个char类型和一个double类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。
（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，继续循环。
）并将判断后的字符串传递到新的数组中，循环结束后，再将数组传递给中缀表达式转后缀表达式函数（Countfor（））。
（3）在Countfor（）函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为’\0’。
在循环中如果元素为数字、点或者#，将元素赋给新的数组Consist[]，再判断下一个元素是否为#，若是则利用strtod（）函数将数组中的字符串转换成double类型的数字，然后数字进栈，清空数组Consist[]；否则，继续判断。
若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’或‘—’并且现有元素为‘*’、‘/’或‘%’又或是现有元素为‘（’，则现有元素进栈；否则，再对现有元素进行判断：
如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。
每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge（）函数,并将函数的返回值压入栈中。
循环结束后，将栈中的运算符全部依次输出，每当有一个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge（）函数,并将函数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再销毁栈。
（4）Judge（）函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。
二、算法流程图
算法一：
利用栈将中缀表达式转化成后缀表达式再进行计算。
图1为算法一中main（）函数的算法流程图，主要功能为：
录入字符串和区分数字字符与运算符字符。
是
否
是
将一个#号传给数组str_pass[]
元素不是数字或’.’
传给数组str_pass[]，原数组下脚标+1
否
传给数组str_pass[]
将新的表达式传递
给Countfor（）函数
是
对表达式进行循环
开始
用户输入表达式
元素为’\0’
元素为数字或’.’
否
结束
图1中缀转后缀表达式算法main（）函数流程图
图2为算法一中Mid_Back（）函数的算法流程图，主要功能为：
将中缀表达式转换成后缀表达式。
将栈进行循环
栈不为空
否
是
输出后缀表达式
结束
将表达式传给求值函数countfor（）
运算符出栈
否
声明并创建一个栈
开始
对表达式进行循环
将元素传给数组Ba_str[]
是
是
现有元素不为’=’
元素为数字、点或者’#’
看栈顶
是
元素进栈
否
栈为空或栈顶为’（’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’（’
元素为’）’
出栈直到’（’出栈
是
否
出栈并赋给Ba_str[]
看栈顶
是
元素进栈
否
出栈，将现有元素进栈
否
栈为空或栈顶为’（’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’（’
图2中缀转后缀表达式算法Mid_Back（）函数流程图
图3为算法一中countfor（）函数的算法流程图，主要功能为：
根据后缀表达式求出表达式的值。
清空数组Consist（）
调用strtod（）函数，结果进栈
运算结果进栈
将元素赋给Consist[]
下一个元素为’#’
是
否
利用switch（）语句判断运算符并进行相应运算
元素为数字、点或者’#’
是
是
否
从数字栈中“扔出”两个数
开始
结束
输出结果
声明并创建数字栈
表达式最终结果出栈
对表达式进行循环
元素不为’\0’
否
图3中缀转后缀表达式算法countfor（）函数流程图
算法二：
利用两个栈（数字栈和符号栈）直接对表达式求值。
图4为算法二中main（）函数的算法流程图，主要功能为：
录入字符串和区分数字字符与运算符字符。
是
否
是
将一个#号传给数组str_pass[]
元素不是数字或’.’
传给数组str_pass[]，原数组下脚标+1
否
传给数组str_pass[]
将新的表达式传递
给Countfor（）函数
是
对表达式进行循环
开始
用户输入表达式
元素为’\0’
元素为数字或’.’
否
结束
图4表达式直接求值算法main（）函数流程图
图5为算法二中Countfor（）函数的算法流程图，主要功能为：
利用两个栈直接对表达式进行取值计算。
将出栈的两个数和一个运算符传给Judge（），并将返回值压进数栈
元素进栈
将出栈的两个数和一个运算符传给Judge（），并将返回值压进数栈
将出栈的两个数和一个运算符传给Judge（），并将返回值压进数栈
否
否
是
否
栈为空或栈顶为’（’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’（’
否
元素为’）’
出栈直到’（’出栈
是
是
元素进栈
是
清空数组Consist[]
调用strtod函数，并将返回值压进数栈
是
是
对表达式进行循环
开始
声明并创建一个数字栈和一个符号栈
元素不为’=’
否
结束
对符号栈进行循环
表达式最终结果出栈
符号栈非空
否
输出结果
将出栈的两个数和一个运算符传给Judge（），并将返回值压进数栈
元素为数字、点或者’#’
将元素传给数组Consist[]
是
元素为’#’
否
栈为空或栈顶为’（’或’+’、’-’且元素为’*’、’/’、’%’或者元素为’（’
图5表达式直接求值算法Countfor（）函数流程图
图6为算法二中Judge（）函数的算法流程图，主要功能为：
判断运算符并根据判断将两个数进行相应的计算，返回计算结果。
开始
结束
利用switch语句对传进来的运算符进行判断并根据判断对两个数字进行相应的运算
返回运算结果
图6表达式直接求值算法Judge（）函数流程图
三、源代码
下面给出的是用一个栈对表达式中缀转后缀再进行运算的算法实现的程序的源代码：
#include""
#include""
#include""
#include""
#defineSTACK_INIT_SIZE10）||a[i]=='#'）
{||Ba_str[i]=='#'）
{）||Min_str[i]=='#'）
{//判断Min_str[i]是否为数字或者点、#，
Consist[j]=Min_str[i];//是，则传入Consist[]数组，直至Min_str[i]为#
j++;
i++;
if（Min_str[i]=='#'）//如果Min_str[i]为#
{
eod=strtod（Consist,NULL）;//利用strtod函数，将Consist[]数组中的字符串转换成double类型的数字
Push（Od,eod）;//eod进栈
for（j=0;j<20;j++）//将Consist[]数组循环清空
{Consist[j]='\0';}
j=0;
}
else--i;
}
else
{//Min_str[i]是运算符
GetTop（Op,eop）;//看栈
if（StackEmpty（Op）||eop=='（'||（（eop=='+'||eop=='-'）&&（Min_str[i]=='*'||Min_str[i]=='%'||Min_str[i]=='/'））||Min_str[i]=='（'）
{Push（Op,Min_str[i]）;}//将栈中已有的运算符与现有的运算符进行比较
else
{
if（Min_str[i]=='）'）//如果现有的运算符为'）'，
{
Pop（Op,eop）;//则栈中的运算符出栈，
for（;eop!
='（';）//直到出栈的运算符为'（'
{
Pop（Od,eod）;//一个运算符出栈，数栈中就Pop出两个数，进行运算
Od2=eod;
Pop（Od,eod）;
Od1=eod;
eod=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=='-'）&&（Min_str[i]=='*'||Min_str[i]=='%'||Min_str[i]=='/'））||Min_str[i]=='（'）
{Push（Op,Min_str[i]）;}
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_str[i]）;
}
}
}
}
}
for（;!
StackEmpty（Op）;//运算符出栈，直到栈空
{
Pop（Op,eop）;//运算符出栈
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）;//销毁字符栈Op
}
doubleJudge（charc_Operator,doubleOd1,doubleOd2）
{
doubleeod;
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:
}
returneod;//返回运算结果
}
四、运行结果
算法一：
利用栈将中缀表达式转化成后缀表达式再进行计算。
将表达式“+2*（32-54/9）-7%5+3=”录入，先将中缀表达式转化成后缀表达式，#是为了区分数字与符号，得到结果为“56.400000”，为正确结果。
图7中缀表达式转化成后缀表达式再进行计算算法的运行结果图
算法二：
利用创建的两个栈直接对表达式进行计算。
将表达式“+2*（32-54/9）-7%5+3=”录入，得到结果为“56.400000”，为正确结果。
图8两个栈直接对表达式进行计算算法的运行结果图
五、遇到的问题及解决
这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：
在第二个算法（表达式直接求值）中输入表达式后，运算结果不正确：
图9遇到的问题1
问题1的解决方法：
先判断“病根”在哪里，首先在数字栈和符号栈的Pop（）函数和Push（）函数中分别加输出语句，观察数字与字符是否正常出入栈，具体如图10。
图10解决问题1中，在栈中添加输出语句
再次运行后，结果如图11。
图11解决问题1中，在栈中添加输出语句后的运行结果
根据图11，可判断出第一个数字1并没有成功的入栈反而被替换成了0，造成这样结果的原因可能有以下几点：
（1）在算法的main（）函数中，在对表达式中数字字符与运算符进行区分操作时，由于考虑的不全面产生逻辑错误，这会使得在接下来的运行中在靠’#’来辨别语速的函数中会产生错误；
（2）在算法的Countfor（）函数中，运算符优先级的判别可能出现逻辑性错误，使得运算不正确；（3）在算法的Countfor（）函数中，运用strtod（）函数方法不正确，使得字符类型转化成double类型是发生错误，然后再将错误的数字传进栈中。
根据判断依次进行调试，首先在main（）函数中对代码进行检验，观察是否有逻辑性错误，结果发现在对表达式中数字字符与运算符进行区分操作时，没有考虑到元素为’（’和元素为’）’时的情况，使得在添加#号时’（’前和’）’后都添加了#，而这是不符合设计思想的，所以进行调节：
在判断了当前元素是为数字或者点之后，在对下一个元素进行判断，看其是否为运算符，如果是则添加#号，如果不是就继续循环。
在对代码进行一番修改之后再运行，运行结果正常，说明问题解决了。
在第一个算法（中缀表达式转后缀表达式再求值）中输入表达式（76—9+6*（1+1）=）后，中缀表达式转后缀表达式结果不正确’+’号应该在’—’前，如图12。
图12遇到的问题2
问题2的解决方法：
如同解决问题一一样，判断“病根”在哪里，首先在数字栈和符号栈的Pop（）函数和Push（）函数中分别加输出语句，观察数字与字符是否正常出入栈，具体如图10。
再次运行后，结果如图13。
图13解决问题2中，在栈中添加输出语句后的运行结果
根据图13所示，数字字符与运算符加#号区分正确，所以，可以排除main（）函数在对表达式中数字字符与运算符进行区分操作时，由于考虑的不全面产生逻辑错误，那么接下来考虑是否是Mid_Back（）函数中判断符号优先级时，由于考虑的不全面而产生的逻辑性的错误。
接下来针对猜想结合图13对程序进行测试运算，原来在对符号的优先级的判断中没有考虑到当栈“扔出”一个元素后，应将现有元素再与栈顶的元素进行优先级的比较，根据比较决定现有元素是否入栈和栈顶元素是否出栈。
病因已经找到了，接下来就是对代码进行修改：
当栈“扔出”一个元素后，再次对栈顶元素和现有元素进行比较，如果现有元素的优先级比栈顶元素的优先级高时，则现有元素进栈，继续循环；否则，栈顶元素出栈，现有元素进栈。
经过修改，运行结果正常，说明问题解决了。
六、心得体会
通过这次的作业，我学到了很多东西：
首先，我了解到怎样用一个栈将中缀表达式转换成后缀表达式和怎样用两个栈对表达式直接进行计算，并且能够用C语言去实现他们。
然后，我学会了怎样用C语言构造不同类型的栈以及栈的相关函数。
这次的作业，也让我重温了C语言这个学了好久也忘记的差不多的语言，我觉得我的编程能了较之以前有了小小的提高，在发现问题和解决问题上也有了一些经验，但我知道只有这些事远远不够的，我要在平时的学习中多多进行锻炼，以提高自己各个方面的能力，它还让我了解到运算符之间的优先级，比较优先级再对运算符进行操作，然后利用字符串转double类型的函数strtod（）将数字字符串转换成double类型的数字。
为了完成这次的作业，我首先利用几天的时间复习C语言的知识和刚刚学过的数据结构的知识，在编程中谨记老师的教诲，要慎思，考虑问题要全面。
下以后的时间里，我要多多练习多多学习，了解不同方面的知识，充分的充实自己，不断地努力，提高自己的能力。
升级会员 