实验2 栈的应用-算术表达式计算.doc

浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验二 栈的应用-算术表达式的计算 学生姓名 蓝礼巍 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1进一步掌握栈的基本操作的实现。2掌握栈在算术表达式的计算方面的应用。二. 实验内容1. 编写程序利用栈将中缀表达式转换成后缀表达式，即从键盘输入任一个中缀表达式（字符串形式），转换成后缀表达式后，将后缀表达式输出。假设：中缀表达式包含圆括号 ( ) 及双目运算符 +、-、*、/、（乘方）。要求：把栈的基本操作的实现函数存放在头文件stack1.h中（栈元素的类型为char），在主文件test6_2.cpp中包含将中缀表达式S1转换成后缀表达式S2的转换函数void Change( char *S1, char *S2 ) 及主函数，在主函数中进行输入输出及转换函数的调用。2. 选做：编写利用栈对后缀表达式进行求值的函数double Compute(char *str)，以计算从前述程序得到的后缀表达式的值。要求：把栈的基本操作的实现函数存放在头文件stack2.h中（栈元素的类型为double），在主文件test6_2.cpp中添加后缀表达式求值函数，并在主函数中增加调用求值函数及输出结果值的语句。 3. 填写实验报告，实验报告文件取名为report2.doc。4. 上传实验报告文件report2.doc与源程序文件stack1.h、stack2.h（若有）及test6_2.cpp到Ftp服务器上你自己的文件夹下。三. 函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路Void InitStack2(Stack2 &S)初始化void Push(Stack1 &S,ElemType1 item)元素插入ElemType1 Pop(Stack1 &S)删除栈顶并返回ElemType1 Peek(Stack1 &S)读取元素bool EmptyStack(Stack1 &S)判断是否为空void ClearStack(Stack1 &S)清除栈四. 实验结果与分析包括运行结果截图等五. 心得体会记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。【附录-源程序】Cpp：#include#include#includetypedef char ElemType1;struct Stack1ElemType1 *stack;int top;int MaxSize;#includestack1.htypedef double ElemType2;struct Stack2ElemType2 *stack;int top;int MaxSize;#includestack2.hint precedence(char op)switch(op)case +:case -:return 1;case *:case /: return 2;case (:case :default:return 0;void Change(char *S1,char *S2)Stack1 R;InitStack(R);Push(R,);int i=0,j=0;char ch=S1i;while(ch!=0)if(ch= )ch=S1+i;else if(ch=()Push(R,ch);ch=S1+i;else if(ch=)while(Peek(R)!=()S2j+=Pop(R);Pop(R);ch=S1+i;else if(ch=+|ch=-|ch=*|ch=/)char w=Peek(R);while(precedence(w)=precedence(ch)S2j+=w;Pop(R);w=Peek(R);Push(R,ch);ch=S1+i;elseif(ch9)&ch!=.)cout中缀表达式错误！=0&ch=9)|ch=.)S2j+=ch;ch=S1+i;S2j+= ;ch=Pop(R);while(ch!=)if(ch=()cerrexpression error!endl;exit(1);elseS2j+=ch;ch=Pop(R);S2j+=0;double Compute(char *str)Stack2 S;InitStack2(S);double x,y;int i=0;while(stri)if(stri= )i+;continue;switch(stri) case +: x=Pop2(S)+Pop2(S); i+; break; case -: x=Pop2(S); x=Pop2(S)-x; i+; break; case *: x=Pop2(S)*Pop2(S); i+; break; case /: x=Pop2(S); if(x!=0.0) x=Pop2(S)/x; else cerrDivide by 0=48&stri=48&stri=57) y=y+(stri-48)/j; i+; j=j*10; x=x+y; Push2(S,x);if(EmptyStack2(S)cerrStack is emptyendl;exit(1);x=Pop2(S);if(EmptyStack2(S)return x;elsecerrexpression errorendl;exit(1);ClearStack2(S);void main(void)char x100,y100;double r;cout请输入一个中缀算数表达式：x;Change(x,y);cout对应的后缀算数表达式为：endl;coutyendl;r=Compute(y);cout后缀表达式为：rendl;H1：void InitStack(Stack1 &S)S.MaxSize=10;S.stack=new ElemType1S.MaxSize;if(!S.stack)cerr动态存储分配失败endl;exit(1);S.top=-1;void Push(Stack1 &S,ElemType1 item)if(S.top=S.MaxSize-1)int k=sizeof(ElemType1);S.stack=(ElemType1*)realloc(S.stack, 2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;S.top+;S.stackS.top=item;ElemType1 Pop(Stack1 &S)if(S.top=-1)cerrStack is emptyendl;exit(1);S.top-;return S.stackS.top+1;ElemType1 Peek(Stack1 &S)if(S.top=-1)cerrStack is emptyendl;exit(1);return S.stackS.top;bool EmptyStack(Stack1 &S)return S.top=-1;void ClearStack(Stack1 &S)if(S.stack)delete S.stack;S.stack=0;S.top=-1;S.MaxSize=0;H2void InitStack2(Stack2 &S)S.MaxSize=10;S.stack=new ElemType2S.MaxSize;if(!S.stack)cerr动态存储分配失败endl;exit(1);S.top=-1;void Push2(Stack2 &S,ElemType2 item)if(S.top=S.MaxSize-1)int k=sizeof(ElemType2);S.stack=(ElemType2*)realloc(S.stack, 2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;S.top+;S.stackS.top=item;ElemType2 Pop2(Stack2 &S)if(S.top=-1)cerrStack is emptyendl;exit(1);S.top-;return S.stackS.top+1;ElemType2 Peek2(Stack2 &S)if(S.top=-