武汉工程大学实验报告03.pdfVIP

武汉工程大学实验报告03--第1页

计算机科学与工程学院

《算法与数据结构》实验报告(三)

专业班级实验地点J008机房

学生学号指导教师姚峰

学生姓名实验时间2018-4-28

实验项目栈的应用

实验类别基础性（√）设计性（）综合性（）其它（）

（1）掌握栈的特点及其存储方法；

实验目的及要求（2）掌握栈的常见算法以及程序实现；

（3）了解递归的工作过程。

成绩评定表

类别评分标准分值得分合计

积极出勤、遵守纪律

上机表现30分

按要求完成设计任务

程序代码规范、功能正确

程序与报告70分

报告详实完整、体现收获

说明：

评阅教师：姚峰日期：20年月日

实验内容

实验内容：表达式求值问题。

这里限定的表达式求值问题是：用户输入一个包含“+”、“-”、“*”、“/”、

正整数和圆括号的合法数学表达式，计算该表达式的运算结果。

算术表达式求值过程是：STEP1：先将算术表达式转换成后缀表达式。

STEP2：然后对该后缀表达式求值。

武汉工程大学实验报告03--第1页

武汉工程大学实验报告03--第2页

实验说明：在设计相关算法中用到栈，这里采用顺序栈存储结构。

初始化运算符栈op;

将=进栈;

从exp读取字符ch;

{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为数字,将后续的所有数字构成一个整数存放到数值栈st中。

若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。

若ch为“－”,则从数值栈st中退栈两个运算数,相减后进栈st中。

若ch