实验2栈的应⽤-算术表达式计算
浙江⼤学城市学院实验报告课程名称数据结构与算法
实验项⽬名称实验⼆栈的应⽤---算术表达式的计算学⽣姓名蓝礼巍专业班级学号实验成绩指导⽼师（签名）⽇期⼀.实验⽬的和要求
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
#include
typedef char ElemType1;struct Stack1{ElemType1 *stack;int top;int MaxSize;};
#include\"stack1.h\"typedef double ElemType2;struct Stack2{ElemType2 *stack;int top;int MaxSize;};
#include\"stack2.h\"int 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=S1[i];
while(ch!='\\0'){if(ch==' ')ch=S1[++i];else if(ch=='('){Push(R,ch);ch=S1[++i];}
else if(ch==')'){while(Peek(R)!='(')S2[j++]=Pop(R);Pop(R);ch=S1[++i];}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){ char w=Peek(R);while(precedence(w)>=precedence(ch)){S2[j++]=w;Pop(R);w=Peek(R);}
Push(R,ch);ch=S1[++i];}else{
if((ch<'0'||ch>'9')&&ch!='.'){cout<<\"中缀表达式错误！\"while((ch>='0'&&ch<='9')||ch=='.'){S2[j++]=ch;ch=S1[++i];}S2[j++]=' ';}}
ch=Pop(R);
while(ch!='@'){if(ch=='('){
cerr<<\"expression error!\"S2[j++]='\\0';}}double Compute(char *str){Stack2 S;InitStack2(S);double x,y;int i=0;while(str[i]){if(str[i]==' '){i++;continue;}
switch(str[i]){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{
cerr<<\"Divide by 0\"while(str[i]>=48&&str[i]<=57){x=x*10+str[i]-48;i++;}if(str[i]=='.'){i++;y=0;
double j=10.0;
while(str[i]>=48&&str[i]<=57){y=y+(str[i]-48)/j;i++;j=j*10;}x=x+y;}}
Push2(S,x);}
if(EmptyStack2(S)){cerr<<\"Stack is empty\"}x=Pop2(S);if(EmptyStack2(S))return x;else{
cerr<<\"expression error\"ClearStack2(S);}void main(void){
char x[100],y[100];double r;
cout<<\"请输⼊⼀个中缀算数表达式：\">x;Change(x,y);cout<<\"对应的后缀算数表达式为：\"cout<<\"后缀表达式为：\"<}H1：void InitStack(Stack1 &S){S.MaxSize=10;
S.stack=new ElemType1[S.MaxSize];if(!S.stack){
cerr<<\"动态存储分配失败\"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.stack[S.top]=item;}
ElemType1 Pop(Stack1 &S){if(S.top==-1){
cerr<<\"Stack is empty\"return S.stack[S.top+1];}ElemType1 Peek(Stack1 &S){if(S.top==-1){
cerr<<\"Stack is empty\"return S.stack[S.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;}H2
void InitStack2(Stack2 &S){
S.MaxSize=10;
S.stack=new ElemType2[S.MaxSize];if(!S.stack){
cerr<<\"动态存储分配失败\"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.stack[S.top]=item;}
ElemType2 Pop2(Stack2 &S){if(S.top==-1){
cerr<<\"Stack is empty\"return S.stack[S.top+1];}ElemType2 Peek2(Stack2 &S){if(S.top==-1){
cerr<<\"Stack is empty\"return S.stack[S.top];}bool EmptyStack2(Stack2 &S){return S.top==-1;
}
void ClearStack2(Stack2 &S){if(S.stack){delete []S.stack;S.stack=0;}S.top=-1;S.MaxSize=0;}
