长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx
《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx》由会员分享，可在线阅读，更多相关《长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告.docx（11页珍藏版）》请在冰点文库上搜索。
长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
批之阿布丰王创作
阅
实验报告
年级班号学号姓名
实验名称：
栈的实现及其应用：
算术表达式的计算
实验日期2016年12月2日
实验陈述撰写内容
一、实验环境
二、实验目的
三、实验内容
四、数据结构与算法思想描述
五、程序清单
六、程序执行结果及其分析
计算机科学与技术系
2016年制
一、实验环境
32位操纵系统下的Window平台MicrosoftVisualC++
二、实验目的
掌握栈的实现及使用
三、实验内容
1.实现栈的存储结构
2.实现栈的基本操纵的有关算法
3.利用栈解决*算术表达式求值问题
四、数据结构与算法思想描述
顺序读取中缀表达式：
1、当遇到数字时，将数字入数字栈
2、当遇到操纵符时，与操纵符栈栈顶比较：
If（当前操纵符优先级大于操纵符栈栈顶的优先级）
If（非”）”操纵符）
将当前操纵符进操纵符栈;
Else
While（操纵符栈栈顶不等于”（“）
取操纵符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
Else
If（非（“操纵符）
While（操纵符栈栈顶不等于”（“）
取操纵符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
Continue;（直到当前操纵符比栈顶操纵符优先级大）
Else
将当前操纵符进操纵符栈;
3、While（操纵符栈非空）
操纵符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈;
4、在数字栈取最后结果并输出。
五、程序清单
//100+（-100）-（-10^2）=100
//（（（2016-2017+（（（2015-2014））））））=0
//-1+（（（（（（（（（1^0））））））））+100%10^2=0
#include
#include
#include
#include
#include
#include
usingnamespacestd;
constintMAX=105;
typedefdoubleType;
typedefstruct
{
TypeTypeStack[MAX];
charcharStack[MAX];
intTypeTop,charTop;
}Stack;
//初始化栈
voidInitStack（Stack*S）
{
S->charTop=S->TypeTop=0;
}
//判断charStack是否为空
boolIsEmpty_Char（StackS）
{
returnS.charTop==0;
}
//判断TypeStack是否为空
boolIsEmpty_Type（StackS）
{
returnS.TypeTop==0;
}
//判断charStack是否为满
boolIsFull_Char（StackS）
{
returnS.charTop==MAX;
}
//判断TypeStack是否为满
boolIsFull_Type（StackS）
{
returnS.TypeTop==MAX;
}
voidPush_Char（Stack*S,charch）
{
//charStack不为满则入栈，否则输出提示
if（!
IsFull_Char（*S））
S->charStack[S->charTop++]=ch;
else
cout<<"TheCharStackIsFull!
"<}
voidPush_Type（Stack*S,Typea）
{
//TypeStack不为满则入栈，否则输出提示
if（!
IsFull_Type（*S））
S->TypeStack[S->TypeTop++]=a;
else
cout<<"TheTypeStackIsFull!
"<}
charPop_Char（Stack*S）
{
if（!
IsEmpty_Char（*S））
{
S->charTop--;
returnS->charStack[S->charTop];
}
else
cout<<"TheCharStackIsEmpty!
"<return-1;
}
TypePop_Type（Stack*S）
{
if（!
IsEmpty_Type（*S））
{
S->TypeTop--;
returnS->TypeStack[S->TypeTop];
}
else
cout<<"TheTypeStackIsEmpty!
"<return-1;
}
charTop_Char（StackS）
{
if（!
IsEmpty_Char（S））
returnS.charStack[--S.charTop];
else
cout<<"TheCharStackIsEmpty!
"<return-1;
}
TypeTop_Type（StackS）
{
if（!
IsEmpty_Type（S））
returnS.TypeStack[--S.TypeTop];
else
cout<<"TheTypeStackIsEmpty!
"<return-1;
}
TypeCalculate（Typeleft,Typeright,charop）
{
Typevalue=0;
switch（op）
{
case'+':
value=left+right;break;
case'-':
value=left-right;break;
case'*':
value=left*right;break;
case'/':
if（right!
=0）
value=left/right;
else
cout<<"被除数不克不及为零!
"<break;
case'%':
if（right!
=0）
value=（int）left%（int）right;
else
cout<<"被余数不克不及为零!
"<break;
case'^':
value=pow（left,right）;
/*value=1;
if（right>=0）
while（right--）
value*=left;
else
{
right=-right;
while（right--）
value/=left;
}*/
}
returnvalue;
}
voidComputer（char*mid_equotion,Typelen）
{
Typeright,left,result;
char*p_mid_equotion=mid_equotion;
charafter_equotion='';
mapOper;
Oper['#']=1;Oper['（']=2;Oper['+']=3;
Oper['-']=3;Oper['*']=4;Oper['/']=4;
Oper['%']=4;Oper['^']=5;Oper['）']=6;
StackMyStack;
InitStack（&MyStack）;
Push_Char（&MyStack,'#'）;
chartop_oper,current_oper;
for（;*p_mid_equotion!
='\0';）
{
top_oper=Top_Char（MyStack）;
current_oper=*p_mid_equotion;
if（!
Oper[current_oper]）
{
Push_Type（&MyStack,strtod（p_mid_equotion,&p_mid_equotion））;
continue;
}//endif
else//为操纵符
{
if（Oper[current_oper]>Oper[top_oper]）
{
if（current_oper!
='）'）
Push_Char（&MyStack,current_oper）;
else
{
while（top_oper!
='（'）
{
right=Pop_Type（&MyStack）;
if（!
IsEmpty_Type（MyStack））
left=Pop_Type（&MyStack）;
else
left=0;
Push_Type（&MyStack,Calculate（left,right,Top_Char（MyStack）））;
Pop_Char（&MyStack）;
top_oper=Top_Char（MyStack）;
}
Pop_Char（&MyStack）;
}//endelse
}//endif
else
{
if（current_oper=='（'）
{
Push_Char（&MyStack,current_oper）;
if（*（p_mid_equotion+1）=='-'）
Push_Type（&MyStack,0）;
}
else
{
right=Pop_Type（&MyStack）;
if（!
IsEmpty_Type（MyStack））
left=Pop_Type（&MyStack）;
else
left=0;
Push_Type（&MyStack,Calculate（left,right,top_oper））;
Pop_Char（&MyStack）;
continue;
}
}//endelse
}//endelse
p_mid_equotion++;
}//endfor
top_oper=Pop_Char（&MyStack）;
while（top_oper!
='#'）
{
right=Pop_Type（&MyStack）;
if（!
IsEmpty_Type（MyStack））
left=Pop_Type（&MyStack）;
else
left=0;
Push_Type（&MyStack,Calculate（left,right,top_oper））;
top_oper=Pop_Char（&MyStack）;
}
//cout<printf（"TheResult=%lf\n\n",（result=Pop_Type（&MyStack）））;
}
intmain（）
{
chars[MAX]="";
Typei=0;
cout<<"请输入你要求值的表达式!
（以-1结束）\n";
while（cin>>s&&strcmp（s,"-1"）!
=0）
{
Computer（s,strlen（s））;
cout<<"请输入你要求值的表达式!
（以-1结束）\n";
}
return0;
}
六、程序执行结果及其分析
对“+”,“-”,“*”,“/”,“%”,“^”运算的实现
可运算多位数和小数，求余，求平方，括号里包含负数如（-1），及首个数字为负数如-1+1
升级会员 