《实验04 栈的应用---算术表达式的计算》由会员分享，可在线阅读，更多相关《实验04 栈的应用---算术表达式的计算（8页珍藏版）》请在金锄头文库上搜索。
1、浙江大学城市学院实验报告浙江大学城市学院实验报告课程名称课程名称 数据结构与算法 实验项目名称实验项目名称 实验四 栈的应用-算术表达式的计算 学生姓名学生姓名 专业班级专业班级 学号学号 实验成绩实验成绩 指导老师（签名指导老师（签名 ） 日期日期 一一. . 实验目的和要求实验目的和要求1进一步掌握栈的基本操作的实现。 2掌握栈在算术表达式的计算方面的应用。二二. 实验内容实验内容1. 编写程序对后缀表达式进行求值（利用栈） ，即输入任一个后缀表达式， 输出该后缀表达式的值。要求：把栈的基本操作的实现函数存放在文件 stack.h 中，在主程序文件 test4.cpp 中包含后缀表达式求值
2、函数 double Compute(char *str)与主函数。主函数可以参考如下: void main() char str50; printf(“请输入一个后缀表达式：“); gets(str); printf(“后缀表达式值为：%fn“, Compute(str) ); 2填写实验报告，实验报告文件取名为 report4.doc。 3上传实验报告文件 report4.doc 与源程序文件 stack.h 及 test4.cpp 到 Ftp 服务器上你自己的文件夹下。三三. 函数的功能说明及函数的功能说明及算法思路算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路 void C
3、hange( char *S1, char *S2 )：中缀表达式转化为后缀表达式 double Compute(char *str):：后缀表达式求值 void InitStack (Stack void Change( char *S1, char *S2 ); double Compute(char *str); void main() char str50,str250; printf(“请输入一个中缀表达式：“); gets(str); Change( str, str2 ); printf(“表达式值为：%fn“, Compute(str2) );double Compute(ch
4、ar *str) double x, y, j; int i=0; Stack1 S; InitStack1(S);while (stri) /扫描表达式中的每个字符 if (stri= ) /跳过空格 i+; continue;switch (stri) case +: x=Pop1(S) + Pop1(S); i+; break; case *: x=Pop1(S) * Pop1(S); i+; break; case -: x=Pop1(S); x=Pop1(S) - x; i+; break; case /: x=Pop1(S); if (x=0.0) cerr=48 S2j+=w;w
5、=Peek2(S);Push2(S, ch);ch=S1+i;else / ch 只可能是数字或 .while ( (ch=0 ch=S1+i; S2j+= ; /数值后面插入一个空格 /while/扫描完 S1 后，把栈中剩余的运算符依次出栈，写入到 S2 中ch=Pop2(S);while ( ch!=) S2j+=ch;ch=Pop2(S); S2j=0; int Precedence(char ch) if(ch=+)|(ch=-) return 1; else if(ch=*)|(ch=/) return 2; else return 0; Stack.hStack.htypedef
6、 double ElemType1; typedef char ElemType2;struct Stack1ElemType1 *stack;/ 存栈元素int top; / 栈顶指示器int MaxSize; / 栈的最大长度 ; void InitStack1 (Stack1 S.stack=(ElemType1 *)malloc(S.MaxSize *sizeof(ElemType1); if(!S.stack) cout“分配空间失败“endl; exit(1); S.top=-1; int EmptyStack1 (Stack1 S) /若栈 S 为空栈返回 1，否则返回 0 re
7、turn S.top=-1; void Push1(Stack1 S.MaxSize*=2; S.top+; S.stackS.top=item; ElemType1 Pop1(Stack1 if(S.top=-1) cout“表达式错误“endl; exit(1); S.top-; temp=S.stackS.top+1; return temp; ElemType1 Peek1(Stack1 S) /取栈 S 的当前栈顶元素并返回 return S.stackS.top; void ClearStack1 (Stack1 struct Stack2 ElemType2 *stack;/ 存
8、栈元素int top; / 栈顶指示器int MaxSize; / 栈的最大长度 ; void InitStack2 (Stack2 S.stack=(ElemType2 *)malloc(S.MaxSize *sizeof(ElemType2); if(!S.stack) cout“分配空间失败“endl; exit(1); S.top=-1; int EmptyStack2 (Stack2 S) /若栈 S 为空栈返回 1，否则返回 0 return S.top=-1; void Push2(Stack2 S.MaxSize*=2; S.top+; S.stackS.top=item; ElemType2 Pop2(Stack2 if(S.top=-1) cout“表达式错误“endl; exit(1); S.top-; temp=S.stackS.top+1; return temp; ElemType2 Peek2(Stack2 S) /取栈 S 的当前栈顶元素并返回 return S.stackS.top; void ClearStack2 (Stack2
