何彬实验报告(共8页).doc
精选优质文档-倾情为你奉上计算机科学与工程学院算法与数据结构实验报告(三)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名何彬实验时间2015-4-24实验项目栈的应用实验类别基础性（） 设计性（） 综合性（） 其它（ ）实验目的及要求（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明： 评阅教师： 赵卿松 日 期： 2015 年 4 月 25 日实 验 内 容实验内容：表达式求值问题。这里限定的表达式求值问题是： 用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。算术表达式求值过程是： STEP 1：先将算术表达式转换成后缀表达式。 STEP 2：然后对该后缀表达式求值。实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。初始化运算符栈op;将'='进栈;从exp读取字符ch;while (ch!='0') if (ch不为运算符)将后续的所有数字均依次存放到postexp中,并以字符'#'标志数值串结束; else switch(Precede(op栈顶运算符,ch) case '<': /栈顶运算符优先级低 将ch进栈; 从exp读取下字符ch; break; case '=': /只有栈顶运算符为'(',ch为')'的情况 退栈; 从exp读取下字符ch; break; case '>': /栈顶运算符应先执行,所以出栈并存放到postexp中 退栈运算符并将其存放到postexp中; break; 若字符串exp扫描完毕,则将运算符栈op中'='之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp; 中缀表达式exp =后缀表达式postexp伪代码如下：对后缀表达式postexp求值伪代码如下：while (从postexp读取字符ch,ch!='0') 若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。 若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。 若ch为“”,则从数值栈st中退栈两个运算数,相减后进栈st中。 若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。 若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中(若除数为零,则提示相应的错误信息)。若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。实 验 内 容#include<stdio.h>#include <stdlib.h>#define maxsize 100/中缀表达式str转换为后缀表达式expvoid trans(char str,char exp) struct char datamaxsize;int top;op;char ch;int i=0,t=0;op.top=-1;ch=stri;i+;while(ch!='0') switch(ch) case '(': op.top+;op.dataop.top=ch;break;case ')':while(op.dataop.top!='(')expt=op.dataop.top;op.top-;t+;op.top-;break;case '+':case '-': while(op.top!=-1&&op.dataop.top!='(') expt=op.dataop.top; op.top-; t+; op.top+;op.dataop.top=ch;break;case '*':case '/': while(op.dataop.top='*'|op.dataop.top='/') expt=op.dataop.top;op.top-;t+;op.top+;op.dataop.top=ch;break;case ' ':break;default:while(ch>='0'&&ch<='9') expt=ch;t+;ch=stri;i+;i-;expt='#'t+;ch=stri;i+;while(op.top!=-1) expt=op.dataop.top;t+;op.top-;expt='0'/后缀表达式的求值float compvalue(char exp) struct float datamaxsize;int top;st;float d;char ch;int t=0;st.top=-1;ch=expt;t+;while(ch!='0') switch(ch) case '+':st.datast.top-1=st.datast.top-1+st.datast.top; st.top-;break;case '-':st.datast.top-1=st.datast.top-1-st.datast.top; st.top-;break;case '*': st.datast.top-1=st.datast.top-1*st.datast.top; st.top-;break;case '/':if(st.datast.top!=0)st.datast.top-1=st.datast.top-1/st.datast.top;elseprintf("nerror! n");exit(0);st.top-;break;default: d=0;while(ch>='0'&&ch<='9') d=10*d+ch-'0'ch=expt;t+;st.top+;st.datast.top=d;ch=expt;t+;return st.datast.top;main() char strmaxsize,expsmaxsize;printf("please input a expressions,just include +,-,*,/and integers:"); gets(str);/输入一个中缀表达式printf("old is: %sn",str);trans(str,exps);/转换printf("after is: %sn",exps);printf("the result is: %gn",compvalue(exps); /求值并输出 getch();实 验 内 容实 验 总 结专心-专注-专业
