长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告

布局阅读如实报告学年编号学号名称实验名称：堆栈实现和应用：算术表达式计算实验日期2016年12月2日实验报告编写内容一、实验环境二、实验目的三、实验内容四、解释数据结构和算法思想五、进程列表六、方案执行结果和分析计算机科学技术和2016年制一、实验环境Microsoft Visual C，32位操作系统下的Window平台二、实验目的了解堆栈的实施和使用情况三、实验内容1.实现堆栈的存储结构实现堆栈基本操作的相关算法使用堆栈解决*算术表达式计算问题四、解释数据结构和算法思想顺序读取中间表达式：1，如果出现数字，则将数字放入数字堆栈2、找到操作符时与操作符堆栈顶部进行比较：If(当前运算符优先级大于运算符堆栈顶部的优先级)If(非) 运算符)将当前操作符放入操作符堆栈。ElseWhile(操作符堆栈顶部不相等(“)使用运算符堆栈顶部和数字堆栈中的两个数字进行运算，然后将结果按数字堆栈。ElseIf (not(运算符)While(操作符堆栈顶部不相等(“)使用运算符堆栈顶部和数字堆栈中的两个数字进行运算，然后将结果按数字堆栈。Continue(直到当前操作符的优先级高于堆栈顶部操作符)Else将当前操作符放入操作符堆栈。3，While(运算符堆栈不为空)计算运算符堆栈顶部和数字堆栈中的两个数字，然后将结果按数字堆栈。4、从数字堆栈中获取最终结果并输出。五、进程列表/10 * 8 2 16.3 5 *(5.2 * 5 3.01)/4-(-10)0.100060 4.0046-40=666.66666/100 (-100)-(-10 2)=100/(2016-2017(2015-2014)=0/-1(1 0)100 2=0)#include#include#include#include#include#includeUsing namespace STDConst int MAX=105Typedef double TypeTypedef structtype TypeStackMAX；char charStackMAX；Int type top，chart Stack/初始化堆栈Void InitStack(Stack *S)S-S-charTop=S-type top=0；/charStack是否为空Bool IsEmpty_Char(Stack S)return s . chartop=0；/TypeStack是否为空Bool IsEmpty_Type(Stack S)return S . type top=0；/charStack是否已满Bool IsFull_Char(Stack S)Return S.charTop=MAX/TypeStack是否已满Bool IsFull_Type(Stack S)Return S . TypeTop=MAXVoid Push_Char(Stack *S，char ch)/charStack未满时进入堆栈。否则，输出提示If(！IsFull_Char(*S)s-char stacks-chart=ch；ElseCout The CharStack Is Full！EndlVoid Push_Type(Stack *S，Type a)/TypeStack未满时进入堆栈。否则，将导出提示If(！IsFull_Type(*S)S-TypeStackS-type top=a；ElseCout The TypeStack Is Full！EndlChar Pop_Char(Stack *S)If(！IsEmpty_Char(*S)s-chart-；return s-char stacks-charop；ElseCout The CharStack Is Empty！Endlreturn-1；Type Pop_Type(Stack *S)If(！IsEmpty_Type(*S)s-type top-；return S-TypeStackS-TypeTop；ElseCout The TypeStack Is Empty！Endlreturn-1；Char Top_Char(Stack S)If(！IsEmpty_Char(S)return s . char stack-s . charop；ElseCout The CharStack Is Empty！Endlreturn-1；Type Top_Type(Stack S)If(！IsEmpty_Type(S)return s . type stack-s . type top；ElseCout The TypeStack Is Empty！Endlreturn-1；Type calculate (type left、type right、char op)type value=0；交换机(op)Case :value=left rightBreakcase-: value=left-right；BreakCase * :value=left * rightBreakCase /:if(right！=0)value=left/right；ElseCout 被除数不能为零！EndlBreak盘柜3360中频(right！=0)value=(int)left %(int)right；Else“Cout”不能等于零EndlBreakCase : value=pow (left，right)；/* value=1；If(right=0)While(right -)Value *=leftElseright=-right；While(right -)value/=left； */Return valueVoid计算机(char * mid _ quotion，type len)Type right、left、resultChar * p _ mid _ eqion=mid _ eqionchar after _ equotion=；贴图operoper#=1；oper(=2；oper=3；oper-=3；oper*=4；oper/=4；oper%=4；oper=5；oper)=6；Stack MyStackinit stack(my stack)；Push_Char(MyStack，#)；Char top_oper，current _ operfor(；* p _ mid _ ekion！= 0；)，以获取详细信息Top _ oper=Top _ Char(my stack)；Current _ oper=* p _ mid _ eqionIf(！Opercurrent_oper)Push _ type (mystack，strtod (p _ mid _ ekquotion，p _ mid _ ekquotion)；Continue/end ifElse/是运算符if(opercurrent _ operopertop _ oper)If(current_oper！=)Push_Char(MyStack，current _ oper)；ElseWhile(top_oper！=()right=Pop _ Type(my stack)；If(！IsEmpty_Type(MyStack)left=Pop _ Type(my stack)；Elseleft=0；Push _ type (mystack，calculate (left，right，top _ char (mystack):pop _ Char(my stack)；Top _ oper=Top _ Char(my stack)；pop _ Char(my stack)；/end else/end ifElseIf(current_oper=()Push_Char(MyStack，current _ oper)；if(*(p _ mid _ quotion 1)=-)Push_Type(MyStack，0)；Elseright=Pop _ Type(my stack)；If(！IsEmpty_Type(MyStack)left=Pop _ Type(my stack)；Elseleft=0；Push _ type (mystack，calculate (left，right，top _ oper)；pop _ Char(my stack)；Continue/end else/end elseP _ mid _ eqion/end fortop _ oper=Pop _ Char(my stack)；While(top_oper！=#)right=Pop _ Type(my stack)；If(！IsEmpty_Type(MyStack)left=Pop _ Type(my stack)；Elseleft=0；Push _ type (mystack，calculate (left，right，top _ oper)；top _ oper=Pop _ Char(my stack)；/cout set precision(6) nthe result=(result=pop _ type(my stack)endl；printf(“the result=% lf n n”，(result=pop _ type(my stack)；Int mai