【实习二】栈与队列的应用.ppt

实习一、二平时成绩记录评分标准 实习一 顺序表、单链表合并拆分（=80分） 大数阶乘 实习二 火烧连营（80=分） 表达式求值或栈和队列综合运用 【实习二】 栈和队列的应用 实习二 （1）栈的应用 【实习题目】 （1）数制转换问题 （2）火烧连营 （3）算术表达式求值 （2）火烧连营 【问题描述】 “火烧连营”是三国演义中的著名典故之一广为流传，假定文本文件c1.txt是火烧连营中的军营分布图，每个字符A代表一个营帐，营帐是可燃物，其他字符代表不可燃的空白地段，文件共有40行70列。 【基本要求】 请你编写程序，读入文本文件的内容。提供MFC界面，输入任意点的x和y值（x70,y40）作为着火点，“火烧连营”后，被燃烧的营帐标上字符’X’，并把整个结果输出到文件c2.txt中。 【实现提示】 基本思想：从着火点位置开始，按四连通思想上下左右寻找其邻居点…… 实现思路：开辟一个堆栈，先将着火点压栈，然后重复以下操作：栈顶点出栈并标记‘X’，同时将符合被燃烧条件的邻居点入栈……，直到栈空为止。 输出：X序列，有哪些信誉好的足球投注网站可以燃烧的字符！ 【测试数据】 c1.txt （3）算术表达式求值 【问题描述】 对一个合法的表达式求值。 假设表达式只包含+、-、*、/ 四个双目运算符，并且允许有括号出现，运算符本身不具有二义性。 例如：3.5*(7+2) /(-6) 【基本要求】 正确解释表达式； 符合四则运算规则： 先乘除、后加减 从左到右运算 先括号内，后括号外 输出最后的计算结果 【实现关键】 两个栈的使用 两位数以上、负数、小数点？ 【实现方式】 基本：控制台程序 MFC对话框（注意ON_CONTROL_RANGE的使用） Example 可选：功能扩展 算数运算符支持：% 增加函数运算：sqrt、pow、sin、cos、tan MFC界面（仿标准型计算器） 表达式求值的几点提示 1、使用两个工作栈： 一个栈OPTR：存放运算符；stackchar 另一个栈OPND：存放操作数；stackdouble 2、运算符之间的优先关系 可用二维数组 算符优先顺序 + - * / ( ) # + - * / ( = ) # = 示例：运算符优先级比较 char MyCalculator::Comp(const char left,const char right) //此函数用来比较两个符号的优先级 { char t[9]={+,-,*,/,%,^,(,),#}; int smax[9][9]=/*+*/{1,1,2,2,2,2,2,1,1, /*-*/ 1,1,2,2,2,2,2,1,1, /***/ 1,1,1,1,1,2,2,1,1, /*/*/ 1,1,1,1,1,2,2,1,1, /*%*/ 1,1,1,1,1,2,2,1,1, /*^*/ 1,1,1,1,1,1,2,1,1, /*(*/ 2,2,2,2,2,2,2,3,0, /*)*/ 1,1,1,1,1,1,0,1,1, /*#*/ 2,2,2,2,2,2,2,0,3}; int j,k; for(int i=0;i9;i++) { if(left==t[i]) j=i; if(right==t[i]) k=i; } switch(smax[j][k]) { case 1:return ; case 2:return ; case 3:return =; default: …… } } 实习二 （2）栈与队列的综合应用 1、停车场问题 2、魔王语言解释器 3、用栈模拟队列 ——实习二 的选做内容 【问题描述】 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车