栈结构演示程序

算法与数据结构设计报告〔2012/2013学年第二学期〕题目：栈结构演示程序专业软件工程学生姓名班级学号指导教师指导单位计算机科学与技术系日期2013年6月评分细那么评分项优秀良好中等差遵守机房规章制度上机时的表现学习态度程序准备情况程序设计能力团队合作精神课题功能实现情况算法设计合理性用户界面设计报告书写认真程度内容详实程度文字表达熟练程度答复下列问题准确度简短评语教师签名：年月日评分等级备注评分等级有五种：优秀、良好、中等、及格、不及格栈结构演示程序一、课题名称栈结构演示程序。二、课题内容和要求理解栈的结构特点和元素的进栈、出栈等操作，并以表达式计算为例，通过图形方式对进栈、出栈操作进行模拟演示。表达式计算是程序设计编译中的的一个最根本的问题，在表达式求值过程中用到栈。在高级语言程序设计中存在各种表达式，表达式由操作数、操作符、和界限符组成。一个表达式中如果操作符在两个操作数之间，那么称之为中缀表达式。尽管中缀表达式是最普遍使用的书写形式，但在程序设计中常用后缀形式求值，原因是后缀表达式中无括号，计算时无需考虑操作符的优先级。后缀表达式的计算过程为：从左往右依次扫描后缀表达式，遇到操作数就进栈，遇到操作符就从栈中弹出两个操作数，执行该操作符所规定的运算，并将结果进栈。如此下去，直到遇到结束符“#”结束。现在用图形方式，对进栈、出栈操作进行演示。三、需求分析本课题的根本设计要求用堆栈实现，因此建立一个堆栈类，作为操作的根本。由于是对计算过程进行战士，涉及到表达式的计算。而具体的计算过程需要用到后缀表达式，因此需要有一个模块将中缀表达式转换成后缀表达式。定义一个Calculator类实现计算过程，并在计算过程中，实现对堆栈的输出和展示。因此本程序主要分为三个模块：堆栈类的建立、中缀表达式转换成后缀表达式、后缀表达式的计算及计算过程的展示。四、概要设计在此说明每个局部的算法设计说明〔可以是描述算法的流程图,使用Visio画图〕，每个程序中使用的存储结构设计说明〔如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明〕。开始开始堆栈类SeqStack的建立堆栈类SeqStack的建立InfixToPostfixInfixToPostfix函数将输入的中缀表达式转换成后缀表达式Calculator类通过Run函数实现对后缀表达式的计算，并在计算过程中实现对计算过程的图形输出Calculator类通过Run函数实现对后缀表达式的计算，并在计算过程中实现对计算过程的图形输出结束结束〔正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距〕五、详细设计〔格式：宋体，4号，加粗，两端对齐〕各个算法实现的源程序〔可以是一组源程序，每个功能模块采用不同的函数实现〕，源程序要按照写程序的规那么来编写。要结构清晰，重点函数的重点变量，重点功能局部要加上清晰的程序注释。〔正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距〕Stack.h:#include<iostream>usingnamespacestd;classCalculator;template<classT>classStack{ public: virtualboolIsEmpty()const=0; virtualboolIsFull()const=0; virtualboolTop(T&x)const=0; virtualboolPush(Tx)=0; virtualboolPop()=0; virtualvoidClear()=0;};template<classT>classSeqStack:publicStack<T>{ public: SeqStack(intmSize); ~SeqStack(){delete[]s;} boolIsEmpty()const{returntop==-1;} boolIsFull()const{returntop==maxTop;} boolTop(T&x)const; boolPush(Tx); boolPop(); voidClear(){top=-1;} friendCalculator; private: inttop; intmaxTop; T*s;};template<classT>SeqStack<T>::SeqStack(intmSize){ maxTop=mSize-1; s=newT[mSize]; top=-1;}template<classT>boolSeqStack<T>::Top(T&x)const{ if(IsEmpty()) { cout<<"Empty"<<endl;returnfalse; } x=s[top]; returntrue;}template<classT>boolSeqStack<T>::Push(Tx){ if(IsFull()) { cout<<"Overflow"<<endl;returnfalse; } s[++top]=x; returntrue;}template<classT>boolSeqStack<T>::Pop(){ if(IsEmpty()) { cout<<"underflow"<<endl;returnfalse; } top--; returntrue;}Calculator.h:#include"stack.h"#include<cmath>#include<cstring>constintSIZE=30;char*InfixToPostfix();intisp(charch);inticp(charch);classCalculator{public: Calculator(intmaxSize):s(maxSize){}; voidRun(); voidClear(){s.Clear();}private: SeqStack<double>s; voidPushOperand(double); boolGetOperands(double&,double&); voidDoOperator(char);};voidCalculator::PushOperand(doubleop){ s.Push(op); cout<<""<<op<<"进栈"<<"|"<<""; for(inti=s.top;i>-1;i--) cout<<s.s[i]<<""; cout<<endl;}boolCalculator::GetOperands(double&op1,double&op2){ if(!s.Top(op1)) { cerr<<"Missingoperand!"<<endl; returnfalse; } s.Pop(); if(!s.Top(op2)) { cerr<<"Missingoperand!"<<endl; returnfalse; } s.Pop(); returntrue;}voidCalculator::DoOperator(charoper){ boolresult; doubleoper1,oper2; result=GetOperands(oper1,oper2); if(result) switch(oper) {case'+': {s.Push(oper2+oper1); cout<<""<<oper2<<"、"<<oper1<<"出栈，计算"<<oper2<<"+"<<oper1<<","<<"结果"<<oper2+oper1<<"进栈"<<"|"<<""; for(intj=s.top;j>-1;j--) { cout<<s.s[j]<<""; } cout<<endl; } break;case'-': {s.Push(oper2-oper1); cout<<""<<oper2<<"、"<<oper1<<"出栈，计算"<<oper2<<"-"<<oper1<<","<<"结果"<<oper2-oper1<<"进栈"<<"|"<<""; for(inti=s.top;i>-1;i--) { cout<<s.s[i]<<""; } cout<<endl; } break;case'*': {s.Push(oper1*oper2); cout<<""<<oper2<<"、"<<oper1<<"出栈，计算"<<oper2<<"*"<<oper1<<","<<"结果"<<oper2*oper1<<"进栈"<<"|"<<""; for(intm=s.top;m>-1;m--) { cout<<s.s[m]<<""; } cout<<endl; } break;case'/': {if(fabs(oper1)<1e-6) { cerr<<"Divideby0!"<<endl; Clear(); } elses.Push(oper2/oper1); cout<<""<<oper2<<"、"<<oper1<<"出栈，计算"<<oper2<<"/"<<oper1<<","<<"结果"<<oper2/oper1<<"进栈"<<"|"<<""; for(intc=s.top;c>-1;c--) { cout<<s.s[c]<<""; } cout<<endl; } break;case'^': {s.Push(pow(oper2,oper1)); cout<<""<<oper2<<"、"<<oper1<<"出栈，计算"<<oper2<<"^"<<oper1<<","<<"结果"<<pow(oper2,oper1)<<"进栈"<<"|"<<""; for(intd=s.top;d>-1;d--) { cout<<s.s[d]<<""; } cout<<endl; } break; } elseClear();}voidCalculator::Run(){ charc; doublenewop; char*postfix=InfixToPostfix(); cout<<postfix<<endl; inti=0; c=postfix[i]; cout<<"-------------------------------------------------------------------------------"<<endl; cout<<"扫描项|操作|栈"<<endl; while(c!='#') { cout<<"-------------------------------------------------------------------------------"<<endl; cout<<""<<c<<"|"; switch(c) { case'+': case'-': case'*': case'/': case'^':DoOperator(c);break; default:cin.putback(c); cin>>newop; PushOperand(newop);break; } c=postfix[++i]; //cout<<"-----------------------------------------------------------"<<endl; } cout<<"-------------------------------------------------------------------------------"<<endl; cout<<"#|"<<"遇到结束符，弹出结果|"<<endl; cout<<"-------------------------------------------------------------------------------"<<endl; if(s.Top(newop)) cout<<newop<<endl;}char*InfixToPostfix(){ SeqStack<char>s(SIZE); charch,y; s.Push('#'); inti=0; char*Postfix=newchar[SIZE*sizeof(char)]; for(intj=0;j<SIZE;j++) { Postfix[j]='\0'; } while(cin>>ch,ch!='#') { if(isdigit(ch)||isalpha(ch)) { Postfix[i++]=ch; } else if(')'==ch) { for(s.Top(y),s.Pop();y!='(';s.Top(y),s.Pop()) Postfix[i++]=y; } else { for(s.Top(y),s.Pop();icp(ch)<=isp(y);s.Top(y),s.Pop()) { Postfix[i++]=y; } s.Push(y); s.Push(ch); } } while(!s.IsEmpty()) { s.Top(y); s.Pop(); if('#'!=y) Postfix[i++]=y; } Postfix[i]='#';// cout<<Postfix<<endl; returnPostfix;}inticp(charch){ switch(ch) { case'#': return0; case'(': return7; case'*': case'/': return4; case'+': case'-': return2; case')': return1; default: cout<<"ErrorInput!"<<endl; } return0;}intisp(charch){ switch(ch) { case'#': return0