栈与队列在‘火烧连营’模拟及算术表达式求值中的应用

"实习二栈及队列的应用.ppt" 是一份教学课件，主要讲解了栈和队列在实际问题中的应用。 【栈的应用】 在这个实习项目中，栈被用于解决“火烧连营”的问题。这是一个典型的深度优先搜索（DFS）问题，通过模拟火势蔓延的过程来标记被燃烧的营帐。具体步骤如下： 1. 首先，读取40行70列的文本文件，其中每个字符代表一个营帐，用特定字符表示可燃的营帐，其他字符表示不可燃的区域。 2. 用户通过MFC界面输入起火点的坐标(x, y)，满足0 < x < 70, 0 < y < 40。 3. 创建一个栈，将起火点压入栈中，然后进入循环过程。 4. 在循环中，每次从栈顶取出一个点，将其标记为'X'，表示已被烧毁。 5. 搜索栈顶点的四个相邻方向（上、下、左、右），如果找到可燃的营帐，则将其压入栈中，继续进行标记。 6. 这一过程持续到栈为空，即所有与起火点相连的可燃营帐都被标记完毕。 7. 最后，将更新后的整个布局写回文件，展示被烧毁的营帐情况。 【队列的应用】 虽然题目中没有明确提到队列，但队列同样适用于此类问题，采用广度优先搜索（BFS）策略。在火烧连营问题中，可以使用队列来存储待检查的营帐，按照先进先出（FIFO）的原则，依次处理队列中的点，达到相同的效果。 【算术表达式求值】 该实习项目还涵盖了计算合法表达式的值，这涉及到运算符的优先级和结合性。对于给定的表达式，如3.5*(7+2)/(-6)，遵循以下规则： 1. 支持四种基本运算：加法（+）、减法（-）、乘法（*）、除法（/）以及扩展的模运算（%）。 2. 运算符优先级：乘法和除法优先于加法和减法；同一优先级的运算符从左到右顺序计算。 3. 括号用于改变运算顺序，括号内的表达式优先计算。 4. 提供函数运算，如平方根函数sqrt()。 实现这个功能需要一个解析器来分析表达式，可能使用到逆波兰表示法（Reverse Polish Notation, RPN）或递归下降解析等方法。首先，将表达式转化为中缀表达式，然后根据运算符优先级和括号规则进行计算，最后输出计算结果。在这个例子中，计算结果为-2.1666666666666665。