1305120411-何彬-实验报告03

计算机科学与工程学院《算法与数据结构》实验报告(三)专业班级2013网络工程01实验地点423机房学生学号1305120411指导教师赵卿松学生姓名何彬实验时间2015-4-24实验项目栈的应用实验类别基础性（√）设计性（）综合性（）其它（）实验目的及要求（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：赵卿松日期：2015年4月25日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容：表达式求值问题。这里限定的表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。算术表达式求值过程是：STEP1：先将算术表达式转换成后缀表达式。STEP2：然后对该后缀表达式求值。实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。中缀表达式exp==》后缀表达式postexp伪代码如下：对后缀表达式postexp求值伪代码如下：初始化运算符栈op;将'='进栈;从exp读取字符ch;while(ch!='\0'){if(ch不为运算符)将后续的所有数字均依次存放到postexp中,并以字符'#'标志数值串结束;elseswitch(Precede(op栈顶运算符,ch)){case''://栈顶运算符优先级低将ch进栈;从exp读取下字符ch;break;case'='://只有栈顶运算符为'(',ch为')'的情况退栈;从exp读取下字符ch;break;case''://栈顶运算符应先执行,所以出栈并存放到postexp中退栈运算符并将其存放到postexp中;break;}}若字符串exp扫描完毕,则将运算符栈op中'='之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp;while(从postexp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。若ch为“－”,则从数值栈st中退栈两个运算数,相减后进栈st中。若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中(若除数为零,则提示相应的错误信息)。}若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。计算机科学与工程学院《算法与数据结构》实验报告3实验内容#includestdio.h#includestdlib.h#definemaxsize100//中缀表达式str转换为后缀表达式expvoidtrans(charstr[],charexp[]){struct{chardata[maxsize];inttop;}op;charch;inti=0,t=0;op.top=-1;ch=str[i];i++;while(ch!='\0'){switch(ch){case'(':op.top++;op.data[op.top]=ch;break;case')':while(op.data[op.top]!='('){exp[t]=op.data[op.top];op.top--;t++;}op.top--;break;case'+':case'-':while(op.top!=-1&&op.data[op.top]!='('){exp[t]=op.data[op.top];op.top--;t++;}op.top++;op.data[op.top]=ch;break;计算机科学与工程学院《算法与数据结构》实验报告4case'*':case'/':while(op.data[op.top]=='*'||op.data[op.top]=='/'){exp[t]=op.data[op.top];op.top--;t++;}op.top++;op.data[op.top]=ch;break;case'':break;default:while(ch='0'&&ch='9'){exp[t]=ch;t++;ch=str[i];i++;}i--;exp[t]='#';t++;}ch=str[i];i++;}while(op.top!=-1){exp[t]=op.data[op.top];t++;op.top--;}exp[t]='\0';}//后缀表达式的求值floatcompvalue(charexp[]){struct{floatdata[maxsize];inttop;}st;floatd;计算机科学与工程学院《算法与数据结构》实验报告5charch;intt=0;st.top=-1;ch=exp[t];t++;while(ch!='\0'){switch(ch){case'+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];st.top--;break;case'-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];st.top--;break;case'*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];st.top--;break;case'/':if(st.data[st.top]!=0)st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];else{printf(\nerror!\n);exit(0);}st.top--;break;default:d=0;while(ch='0'&&ch='9'){d=10*d+ch-'0';ch=exp[t];t++;}st.top++;st.data[st.top]=d;}ch=exp[t];t++;}returnst.data[st.top];}计算机科学与工程学院《算法与数据结构》实验报告6main(){charstr[maxsize],exps[maxsize];printf(pleaseinputaexpressions,justinclude+,-,*,/andintegers:);gets(str);//输入一个中缀表达式printf(oldis:%s\n,str);trans(str,exps);//转换printf(afteris:%s\n,exps);printf(theresultis:%g\n,compvalue(exps));//求值并输出getch();}实验内容计算机科学与工程学院《算法与数据结构》实验报告7实验总结