栈结构演示程序.docx

算法与数据结构设计报告2012/2013学年第二学期题目：栈结构演示程序专业软件工程学生姓名班级学号指导教师指导单位计算机科学与技术系0期2013年6月评分细那么评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度答复下列问题准确度简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格栈结构演示程序一、课题名称栈结构演示程序。二、课题内容和要求理解栈的结构特点和元素的进栈、出栈等操作，并以表达式计算为例，通过图形方式对进栈、出栈操作进行模拟演示。表达式计算是程序设计编译中的的一个最根本的问题，在表达式求值过程中用到栈。在高级语言程序设计中存在各种表达式，表达式由操作数、操作符、和界限符组成。一个表达式中如果操作符在两个操作数之间，那么称之为中缀表达式。尽管中缀表达式是最普遍使用的书写形式，但在程序设计中常用后缀形式求值，原因是后缀表达式中无括号，计算时无需考虑操作符的优先级。后缀表达式的计算过程为：从左往右依次扫描后缀表达式，遇到操作数就进栈，遇到操作符就从栈中弹出两个操作数，执行该操作符所规定的运算，并将结果进栈。如此下去，直到遇到结束符“旷结束。现在用图形方式，对进栈、出栈操作进行演示。三、需求分析本课题的根本设计要求用堆栈实现，因此建立一个堆栈类，作为操作的根本。由于是对计算过程进行战士,涉及到表达式的计算。而具体的计算过程需要用到后缀表达式，因此需要有一个模块将中缀表达式转换成后缀表达式。定义一个CaICUlatOr类实现计算过程，并在计算过程中，实现对堆栈的输出和展示。因此本程序主要分为三个模块：堆栈类的建立、中缀表达式转换成后缀表达式、后缀表达式的计算及计算过程的展示。四、概要设计在此说明每个局部的算法设计说明（可以是描述算法的流程图,使用ViSiO画图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变号和成员函%原型声明）。开始InfixToPostfix函数将输入的中缀表达式转换成后缀表达式（正文格式：宋体，小五、详细设计（格式Calcul对后缀过程中出atnr半涌讨RnnW结束勺数实现F在计算J图形输阐各个算法实现的源程序（可以是一组源程序，每个功能模块采用不同的函数实现），源程序要按照写程序的规那么来编写。要结构清晰，重点函数的重点变量，重点功能局部要加上清晰的程序注释。（正文格式：宋体，小4号，不加粗，两端对齐，L5倍行距）Stack,h:ttinclude<iostream>usingnamespacestd;classCalculator;template<classT>classStack(public:virtualboolIsEmpty()const=0;virtualboolIsFullOconst=O;virtualboolTop(T&x)const=0;virtualboolPush(Tx)=0;virtualboolPop()=0;virtualvoidClearO=O;；template<classT>classSeqStack:publicStack<T>(public:SeqStack(intmSize);"zSeqStackOdeletes;boolIsEmptyOconstreturntop-l;boolIsFul1()constreturntop-maxTop;boolTop(T&x)const;boolPush(Tx);boolPop();voidClearOtop=-l;friendCalculator;private:inttop;intmaxTop;T*s;)；template<classT>SeqStack<T>:SeqStack(intmSize)(maxTop-mSize-1;s=newTmSize;top=-l;)template<classT>boolSeqStack<T>:Top(T&x)constif(IsEmpty()CoUt<<"Empty”<<endl;returnfalse;)X=Stop;returntrue;)template<classT>boolSeqStack<T>:Push(Tx)(if(IsFull()(cout<<7z0verflow/z<<endl;returnfalse;)S+top=X;returntrue;)template<classT>boolSeqStack<T>:Pop()(if(IsEmptyO)(cout<<z,underflow7z<<endl;returnfalse;)top;returntrue;)Calculator,h:Itinclude"stack.h#include<cmath>include<cstring>constintSIZE=30;char*InfixToPostfix();intisp(charch);inticp(charch);classCalculator(public:Calculator(intmaxSize):s(maxSize);voidRun();voidClearOs.Clear();)private:SeqStack<double>s;voidPushOperancKdouble);boolGetOperands(double&,double&);voidDoOperator(char);；voidCalculator:PushOperand(doubleop)(s.Push(op);cout<<z,<<op。进栈<<|<<for(inti=s.top;i>-l;i-)cout<<s.si<<z,；cout<<endl;)boolCalculator:GetOperands(double&opl,double&op2)(if(!s.Top(opl)(Cerr“Missingoperand!z,<<endl;returnfalse;)S.PopO;if(!s.Top(op2)(CelT<<"MissingOPerand!”<<endl;returnfalse;)s.PopO;returntrue;)voidCalculator:DoOperator(charoper)(boolresult;doubleoperl,oper2;result=GetOperands(operl,oper2);if(result)switch(oper)(case'+,:s.Push(oper2+operl);cout<<z,”<<oper2<<""<<operl<<"出栈，计算“<<oper2<<"+"<<operl<<",结果"<<oper2+operl<<进栈<<"<<"；for(intj=s.top;j>-l;j)(cout<<s.sj<<z,”;)cout<<endl;)break;case'-,:s.Push(oper2-operl);cout<<,z"<<oper2<<""<<oPerI<<"出栈，计算“<<oper2<<"-"<<operl<X",结果"<<oper2-operl<<“进栈|"<<"for(inti=s.top;i>-l;i-)(cout<<s.si<<")cout<<endl;)break;case,*':s.Push(oper1*oper2);cout<<zz"<<oper2<<""<<operl<<"出栈，计算“<<oper2<<"*"<<operl<<","<<”结果"<<oper2*operl<<“进栈<<|<<；for(intm=s.top;m>-l;m-)(cout<<s,sm<<*；)cout<<endl;)break;case',:if(fabs(operl)<le6)(cerr<<zzI)ividebyO!zz<<endl;Clear();)elses.Push(oper2operl);COUt<<""<<oper2<<、"<<operl<<"出栈，计算“<<oper2<<""<<operl<<","<<结果"<<oper2/OPer1«进栈<<|"<<"；for(intc=s.top;c>-l;c-)cout<<s.sc<<")cout<<endl;)break;，公，case:s.Push(pow(oper2,oper1);cout<<z,”<<oper2<<""<<operl<<"出栈，计算<<oper2<<""<<operl<<",”<<结果<<POW(OPer2,oper1)<<进栈<<"|"<<"；for(intd=s.top;d>-l;d-)(cout<<s.sd<<z,”;)cout<<endl;)break;)elseClear();)voidCalculator:Run()(charc;doublenewop;char*postfix=InfIxToPostfix();cout<<postfix<<endl;inti=O;c二postfixi;COUt<<<<endl;操作cout<<z,扫描项"<<endl;whiIe(c!='#')COUt<<<<endl;COUt<<"<<c<<"|；switch(c)(case,+,:case,->:case'*':case,:case,r:DoOperator(c);break;default:cin.putback(c);cin>>newop;PushOperand(newop);break;)c=postfix+i;/cout<<"z,<<end)COUt<<“<<endl;CoUt<<U|<<遇到结束符，弹出结果"<<endl;COUt<<<<endl;if(s.Top(newop)cout<<newop<<endl;)char*InfixToPostfix()SeqStack<char>s(SIZE);charch,y;s.Push('#');inti=O;char*Postfix=newcharSIZE*sizeof(char);for(intj=0;j<SIZE;j+)(Postfixj=,0,;)whiIe(cin>>ch,ch!=')(if(isdigit(ch)isalpha(ch)(Postfixi+=ch;)elseifO,=ch)(for(s.Top(y),s.PopO;y!='s.Top(y),s.Pop()Postfixi+=y;)else(for(s.Top(y),s.PopO;icp(ch)<=isp(y);s.Top(y),s.PopO)(Postfixi+=y;)s.Push(y);s.Push(ch);)whiIe(!s.IsEmptyO)(s.Top(y);s.PopO;if(,#'!=y)Postfixi+=y;)Postfixi=，#，;/cout<<Postfix<<endl;returnPostfix;)inticp(charch)(switch(ch)(case,#':return0;case'(,:return7;case,*':case',:return4;case'+,:case,-,:return2;case,),:return1;default:COUt<<"EorInput!zz<<endl;returnO;)intisp(charch)(switch(ch)(case,#':returnO;case'(,:return1;case,*':case,:return5;case'+,:case,->:return3;case')':return7;default:cout<</zErrorInput!z,<<endl;)return0;)Main,cpp:#includecalculator.hvoidmain()CalculatorCal(SIZE);Cal.Run();六、测试数据及其结果分析（格式：宋体，4号，加粗，两端对齐）测试数据，应准备多组测试数据，对测试输出的结果进行分析。如上图所示，输入的中缀表达式会先转换成后缀表达式，然后实现计算过程及其图形输出七、调试过程中的问题调试过程中遇到的问题主要是输出时格式控制问题，在每次将每次的计算过程用表格展示时，由于是动态输出，每次输入的结果都不一样，所以是每次输出整齐统一就需要特别加以控制，这也是在调试过程中遇到的最大问题。八、程序设计总结总结可以包括：程序设计过程的收获、遇到的问题，遇到问题解决问题过程的思考、程序调试能力的思考，对该课程组织和考核方式的建议等。通过这次的程序设计，加深了对堆栈及其用途的理解，在调试过程中也学会了输出格式控制。最初的时候，程序只能对后缀表达式进行计算过程展示，这样就有一定的缺乏，不符合大家平时的输入习惯，后来增加了一个模块，将中缀表达式转换成后缀表达式，方便了计算，程序也更容易理解。拿到一个问题，首先要了解需要解决哪些局部，通过对问题的分解，通过一个个模块，实现对每个小问题解决，同时在每个模块设计过程中，要注意方法的统一，以便于最后的综合。