实验二栈的应用算术表达式的计算

1、浙江大学城市学院实验报告课程名称 数据结构与算法 实验项目名称 实验二 栈的应用-算术表达式的计算 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1进一步掌握栈的基本操作的实现。2掌握栈在算术表达式的计算方面的应用。二. 实验内容1. 编写程序利用栈将中缀表达式转换成后缀表达式，即从键盘输入任一个中缀表达式（字符串形式），转换成后缀表达式后，将后缀表达式输出。假设：中缀表达式包含圆括号 ( ) 及双目运算符 +、-、*、/、（乘方）。要求：把栈的基本操作的实现函数存放在头文件stack1.h中（栈元素的类型为char），在主文件test6_2.cpp中包含将中缀表达式S1转换成后缀表

2、达式S2的转换函数void Change( char *S1, char *S2 ) 及主函数，在主函数中进行输入输出及转换函数的调用。2. 选做：编写利用栈对后缀表达式进行求值的函数double Compute(char *str)，以计算从前述程序得到的后缀表达式的值。要求：把栈的基本操作的实现函数存放在头文件stack2.h中（栈元素的类型为double），在主文件test6_2.cpp中添加后缀表达式求值函数，并在主函数中增加调用求值函数及输出结果值的语句。 3. 填写实验报告，实验报告文件取名为report2.doc。4. 上传实验报告文件report2.doc与源程序文件stack

3、1.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是

4、否为空，若是则返回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<iostream.h&g

5、t;#include<stdlib.h>#include<math.h>#include"stack1.h"#include"stack2.h"void main()char x30,y30;double r;while(1)cout<<"请输入一个中缀算术表达式："cin.getline(x,sizeof(x);Change(x,y);cout<<"对应的后缀算术表达式为："cout<<y<<endl;r=Compute(y);cout<

6、;<"后缀算术表达式值为："<<r<<endl<<endl;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(S

7、tack1 &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)cerr<<"Stack is empty! "<<endl;exit(1);S.top-;return S.stackS.top+1

8、;ElemType1 Peek(Stack1 &S)if(S.top=-1)cerr<<"Stack is empty! "<<endl;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;/返回运算符op所对应的优先级数值int Precedence(char op)swit

9、ch(op)case'+':case'-':return 1;case'*':case'/':return 2;case'':return 3;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')/对于空

10、格字符不做任何处理，顺序读取下一个字符if(ch=' ')ch=S1+i;/对于左括号，直接进栈else if(ch='(')Push(R,ch);ch=S1+i;/对于右括号，使括号内的仍停留在栈中的运算符依次出栈并写入S2else if(ch=')')while(Peek(R)!='(')S2j+=Pop(R);Pop(R);/删除栈顶的左括号ch=S1+i;/对于运算符，使暂存于栈顶且不低于ch优先级的运算符依次出栈并写入S2else if(ch='+'|ch='-'|ch='*

11、9;|ch='/'|ch='')char w=Peek(R);while(Precedence(w)>=Precedence(ch)S2j+=w;Pop(R);w=Peek(R);Push(R,ch);/把ch运算符写入栈中ch=S1+i;elseif(ch<'0'|ch>'9')&&ch!='.')cout<<"中缀表达式表示错误！"<<endl;exit(1);while(ch>='0'&&ch&

12、lt;='9')|ch='.')S2j+=ch;ch=S1+i;S2j+=' '/把暂存在栈中的运算符依次退栈并写入到S2中ch=Pop(R);while(ch!='')if(ch='(')cerr<<"expression error!"<<endl;exit(1);elseS2j+=ch;ch=Pop(R);S2j+='0'stack2.htypedef double ElemType2;struct Stack2ElemType2 *stack;in

13、t 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);

14、S.MaxSize=2*S.MaxSize;S.top+;S.stackS.top=item;ElemType2 Pop(Stack2 &S)if(S.top=-1)cerr<<"Stack is empty! "<<endl;exit(1);S.top-;return S.stackS.top+1;ElemType2 Peek(Stack2 &S)if(S.top=-1)cerr<<"Stack is empty! "<<endl;exit(1);return S.stackS.top;b

15、ool 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)+P

16、op(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;elsecerr<<"Divide by 0!"<<endl;exit(1);i+;break;case'':x=Pop(S);x=pow(Pop(S),x);i+;break;default:x=0;while(stri>=48&&stri<=57)x=x*10+stri-48;i+;if(stri='.')i+;y=0;double j=10.0;while(stri>