[理学]表达式求解 迷宫求解.doc

课 程 设 计 报 告 课程名称 数据结构 课题名称 表达式求解 迷宫求解 专 业 信息与计算科学 班 级 学 号 姓 名 指导教师 年 月 日  湖南工程学院 课 程 设 计 任 务 书 课程名称 数据结构 课 题 表达式求值 迷宫求解 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期 2009 年 5 月 15 日 任务完成日期 年 月 日 一、设计内容与设计要求 课题1表达式求值 问题描述：设计一编译器，对读入的表达式能根据人们的约定予以正确解释，并计算结果。 设计要求：（1）表达式中应包含数值常量、四则运算符、括号等。 （2）对不合理的解释应有反应。 设计提示：（1）可用两个栈（操作数栈及运算符栈）来存储原始数据及中间结果。 （2）对表达式进行语法检查。 （3）用一一维数组约定运算符的位置，用一二维数组存放运算符间的优先关系。 测试数据：3+a*9 2+(1*(7-8)*5 7*(5+6-4*2/(2*7))+9/4-5 课题4 迷宫问题 问题描述：用计算机模拟解决“迷宫问题”，求出其中一条通道。用数组MAZE[1...M,1..N]表示迷宫，有的可以通行（0表示），有的是路障（1表示），MAZE[1][1]为迷宫入口,MAZE[M][N]为迷宫出口,用非递归算法求出一条通路。 设计要求：用“■”标示所输出的路径(见运行示例)否则说明没有通路,继续生成迷宫,直到有通路。 算法提示：实现这一算法的具体方法很多（如堆栈,队列等）,但基本思想一般是回溯法使用MAZE[M][N]表示迷宫（如图２），为判定过程中是否越界，在其外围加一圈１作为路障，mark[M][N]作为标志数组，move[8][2]是行列增量数组（见图１－２）；建堆栈．约定（i,j）表示I行j列,direction 表示方向, 从入囗开始探索路径：沿０－１八个方向依次试探，若某方向可通（为０），则该点连同方向入堆栈，从该点继续试探；若八个方向都不通，则取出堆栈顶点，从其标记的方向开始试探其余方向；直至找到出口（有通路）或堆栈为空(没有通路). 下面是利用一随机函数生成的0/1方阵及运行示例: 二、进度安排 日 期 上午 下午 15周星期一 课题讲解 明确任务查资料 15周星期二 上机调试 上机调试 15周星期三 上机调试 上机调试 16周星期二 上机调试 上机调试 16周星期五 上机调试及答辩 答辩 目录 1 表达式求值 1.1问题分析…………………………………………………………… 1.2算法描述…………………………………………………………… 1.3运行结果…………………………………………………………… 1.4设计体会…………………………………………………………… 2 迷宫求解 2.1问题分析…………………………………………………………… 2.2算法描述…………………………………………………………… 2.3运行结果…………………………………………………………… 2.4设计体会…………………………………………………………… 1表达式求值 1.1问题分析 设计一个编译器，能对一个含有数值常量，四则运算符，括号的表达式根据人们给予约定计算正确的结果，并且对于不合理的表达式有所反应。关于表达式求值，输入的数据用栈这一数据结构储存，建立一个数据栈（OPND），用来存储表达式中的数据；一个运算符栈（OPTR），用来存储表达式中的四则运算符；用一个二维数组约定运算符之间的优先级别。通过对两个栈进行元素的进栈与出栈以及中间结果的计算，得到输入表达式的值。 1.2算法描述 表达式求值是栈应用的一个典型列子，我采用的是一种简单直观、广为使用的算法，通常称为“算符优先法”。任何一个表达式都是由操作数、运算符和界限符组成的，其中操作数是是用户从键盘终端输入的整型变量，运算符为‘+’、‘-’，‘*’，‘/’，界限符有左右括号和表达式结束符。在本程序中，我把运算符和界限符统称为算符，他们构