堆栈和队列的应用

时间：2024-10-12 07:03:55

目的：
1、计算数学表达式的值。 输入数学表达式，输出表达式的计算结果。
数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(”、“)”构成，例如 2 + 3 * ( 4 + 5 ) – 6 / 4。假定 表达式输入格式合法。
2、以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。 设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
迷宫根据一个迷宫数据文件建立。迷宫数据文件由一个包含 0、1 的矩阵组成。迷宫的通路可以使用通路上各点的坐标序列进行展示(使用图形展示最佳)。
3、设计电路布线最短路径。

要计算表达式，可以把问题分为两个：

  • 要把字符串转为数字
  • 要给符号安排合适的优先级并正确处理括号

把字符串转为数字可以用C标准库中的atoi()函数(#include <cstdlib>)，也可以用C++标准库中的stringstream(#include <sstream>)，而我是直接自己写了一个简单的函数，只能用于处理正整数，而且不会合适的报错，但在所给要求还是下够用了。

int getValue(string str)
{
  //获得数字应该有的值
    int multi = 1;
    int value = 0;
    for (int i = () - 1; i >= 0; i--) {
        value += ((i) - '0')*multi;
        multi *= 10;
    }
    return value;
}

要对表达式进行解析和计算，可以参考我的这篇文章，也可以像我在这里所用的方法一样，通过对每个优先级的符号进行分析，按优先级进行运算。
具体来说，就是通过栈来存储左括号位置，当找到一个对应右括号位置时对栈顶左括号和右括号中的内容进行再次分析，直到获得没有包含括号的内容，对它进行先乘除再加减的四则运算。再把运算结果替代左括号和右括号中的内容拼接到字符串中，一直到栈为空，再对剩下的字符串直接进行四则运算，得出结果。压缩包中有具体的代码，在这里就不贴了。

寻找迷宫通路也可以栈来求解。通过栈保存已经走过的路径，并在四周查找能继续走的格子，找到就入栈，继续查找下一个能走的格子；找不到就从栈中删除当前位置并查找上一个格子附近有没有可以走的格子。当找到终点时，返回查找成功，当栈为空时，返回查找失败。

bool FindPath()
{
    path = new Stack<Position>(m*n - 1);

    Position offset[4];
    offset[0].row =

相关文章