数据结构与算法实验二栈的应用---算术表达式的计算.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服务器上你自己的文件夹下。二. 函数的功能说明及算法思路（算法思路见源程序的注释部分）/栈的顺序存储结构定义struct StackElemType *stack;int top;int MaxSize;/初始化栈S为空void InitStack(Stack &S)/元素item进栈，即插入到栈顶void Push(Stack &S,ElemType item)/删除栈顶元素并返回ElemType Pop(Stack &S)/读取栈顶元素的值ElemType Peek(Stack &S)/判断S是否为空，若是则返回true，否则返回falsebool EmptyStack(Stack &S)/清除栈S中的所有元素，释放动态存储空间void ClearStack(Stack &S)/将中缀算术表达式转换为后缀算术表达式void Change(char *S1,char *&S2)/返回运算符op所对应的优先级数值int Precedence(char op)/计算由str所指字符串的后缀表达式的值double Compute(char *str)四. 实验结果与分析五. 心得体会【附录-源程序】test6_2.cpp#include#include#include#includestack1.h#includestack2.hvoid main()char x30,y30;double r;while(1)cout请输入一个中缀算术表达式：;cin.getline(x,sizeof(x);Change(x,y);cout对应的后缀算术表达式为：;coutyendl;r=Compute(y);cout后缀算术表达式值为：rendlendl;stack1.htypedef char ElemType1;struct Stack1ElemType1 *stack;int top;int MaxSize;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 empty! endl;exit(1);S.top-;return S.stackS.top+1;ElemType1 Peek(Stack1 &S)if(S.top=-1)cerrStack is empty! =Precedence(ch)S2j+=w;Pop(R);w=Peek(R);Push(R,ch);/把ch运算符写入栈中ch=S1+i;elseif(ch9)&ch!=.)cout中缀表达式表示错误！=0&ch=9)|ch=.)S2j+=ch;ch=S1+i;S2j+= ;/把暂存在栈中的运算符依次退栈并写入到S2中ch=Pop(R);while(ch!=)if(ch=()cerrexpression error!endl;exit(1);elseS2j+=ch;ch=Pop(R);S2j+=0;stack2.htypedef double ElemType2;struct Stack2ElemType2 *stack;int top;int MaxSize;void InitStack(Stack2 &S)S.MaxSize=10;S.stack=new ElemType2S.MaxSize;if(!S.stack)cerr动态储存分配失败endl;exit(1);S.top=-1;void Push(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 Pop(Stack2 &S)if(S.top=-1)cerrStack is empty! endl;exit(1);S.top-;return S.stackS.top+1;ElemType2 Peek(Stack2 &S)if(S.top=-1)cerrStack is empty! endl;exit(1);return S.stackS.top;bool EmptyStack(Stack2 &S)return S.top=-1;void ClearStack(Stack2 &S)if(S.stack)delete S.stack;S.stack=0;S.top=-1;S.MaxSize=0;/计算由str所指字符串的后缀表达式的值double Compute(char *str)Stack2 S;InitStack(S);double x,y;int i=0;while(stri)if(stri= )i+;continue;switch(stri)case +:x=Pop(S)+Pop(S);i+;break;case-:x=Pop(S);x=Pop(S)-x;i+;break;case*:x=Pop(S)*Pop(S);i+;break;case/:x=Pop(S);if(x!=0)x=Pop(S)/x;elsecerrDivide by 0!=48&stri=48&stri=57)y=y+(stri-4