Fork me on GitHub

栈的简单应用

发表于 | 分类于 | | 本文总阅读量 次
本文记录了栈的三个简单应用：1.括号匹配；2.汉诺塔；3.迷宫老鼠问题。

1. 栈的应用汇总

1.1. 括号匹配

问题描述：判断一个字符串的左右括号是否匹配。
输入是一个字符串，输出是 true 或者 false。

求解策略：如果从左到右地扫描一个字符串，那么每一个右括号都与最近扫描的那个未匹配的左括号相匹配。我们可以从左到右扫描，将扫描到的左括号保存在栈中。每当扫描到一个右括号，就将它与栈顶的左括号（如果存在）相匹配，并将匹配的左括号从栈顶删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <string>
#include <stack>
using namespace std;

/* 判断表达式中括号匹配 */
bool printMatchedPairs(string expr){
    stack<int> s;
    int length = expr.size();
    for (int i = 0; i < length; ++i){
        if (expr.at(i) == '(')
            s.push(i);
        else if (expr.at(i) == ')'){
            if (s.empty())
                return false;
            else
                s.pop();
        }
    }
    if (!s.empty())
        return false;
    return true;
}
int main(int argc, char **argv){
    // 括号匹配
    string expr;
    cin >> expr;
    cout << expr << " matched is " << printMatchedPairs(expr) << endl;
    return 1;
}

时间复杂度：上述代码的时间复杂度为 O(n)，其中 n 为输入表达式的长度。

1.2. 汉诺塔（Towers of Hnoi）

问题描述：假设有 n 个碟子和 3 座塔。初始时所有碟子从大到小堆在塔 1 上，我们要把碟子都移动到塔 2 上，另有塔 3 做为中转站。移动中要求：

  1. 每次移动一个；
  2. 任何时候都不能把大碟子压在小碟子上面。

求解策略：一个简洁的解决方法是递归。为了把最大的碟子移动到塔 2 的底部。必须把其余 n-1 个碟子移动到塔 3，然后把最大的碟子移动到塔 2。接下来是把塔 3 上的 n-1 个碟子移到塔 2。为此可以利用塔 2 和塔 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

/* 汉诺塔 */
// 直接递归
void towersOfHanoi(int n, char x, char y, char z){
    // 将塔 x 顶部的 n 个盘子移到塔 y，用 塔 z 作为中转地
    if (n == 1){
        cout << x << " -> " << y << endl;
    }else{
        towersOfHanoi(n-1, x, z, y);
        cout << x << " -> " << y << endl;
        towersOfHanoi(n-1, z, y, x);
    }
}

int main(int argc, char **argv)
{
    int num = 0;
    cim >> num;
    towersOfHanoi(num, 'a', 'b', 'c');
    return 1;
}

时间复杂度：上述程序的运行时间正比于输出的信息行数目，而信息行数目等于碟子移动的次数。分析可知，碟子移动次数的递归式 $moves(n)$：

$$moves(n) = \begin{cases}0, & \text{n is equal to 0} \ 2moves(n-1)+1, & \text{n is greater than 0}\end{cases}$$

计算这个公式，可以得到结果为 $moves(n)=2^n-1$。可以证明，$2^n-1$ 实际上是最少的移动次数。可以判定函数 towerOfHanoi 的复杂度为 $O(2^n)$。

1.3. 迷宫老鼠

问题描述：迷宫（maze）是一个矩形区域，有一个入口和一个出口。迷宫内部包含不能穿越的墙壁或障碍物。这些障碍物沿着行和列放置，与迷宫边界平行。迷宫的入口在左上角，出口在右下角。迷宫老鼠（rat in a maze）问题是要寻找一条从入口到出口的路径。路径是一个由位置组成的序列，每一个位置都没有障碍，而且除入口之外，路径上的每一个位置都是前一个位置在东南西北方向上相邻的一个位置。

假设迷宫是个 n*n 的方阵，且足够小（能够存储在目标计算机内存中）。在矩阵中，当且仅当在位置 (i, j) 处有一个障碍时，其值为1，否则其值为0。

1
2
3
4
    _________________________
入口    |||||           |||||                      入口  0 1 0 0 0 1
    |   |||||   |||||   |||||                           0 1 0 1 0 1
    |___________|||||________ 出口                      0 0 0 1 0 0  出口

求解策略：这个求解有三个步骤：输入迷宫、寻找路径和输出路径。本文只讨论寻找路径模块。

寻找路径：首先把迷宫入口作为当前位置。如果当前位置是迷宫出口，那么已经找到一条路径，寻找工作结束。如果当前位置不是迷宫出口，则在当前位置放置障碍物，以阻止寻找过程中又绕回到这个位置。然后检查相邻位置是否有空闲，如果有，就移动到一个空闲的相邻位置上，然后从这个位置开始寻找通往出口的路径。如果不成功，就选择另一个空闲的相邻位置，并从它开始寻找通往出口的路径。为了方便移动，在进入新的相邻位置之前，把当前位置保存在一个栈中。如果所有空闲的相邻位置都已经被探索过，但还未找到路径，则表明迷宫不存在从入口到出口的路径。

在迷宫的内部位置开始，有4中可能的移动方向：上下左右。从迷宫的边界开始，只有两种或三种可能的移动方向。为了避免在处理内部位置和边界位置时存在的差别，可以在迷宫周围增加一圈障碍物。对于 m*m 的数组 maze，这一圈障碍物将占据数组 maze 的第 0 行，第 m+1 行，第 0 列，第 m+1 列。这样，从迷宫的每个位置都有 4 种可能的移动方向，所以程序不需要处理边界条件，大大简化了代码设计。

每个迷宫位置都可以用行和列的下标来表示，分别称为迷宫位置的行坐标的列坐标。可以定义一个带有数据成员 row 和 col 的类 position，使用它的对象来跟踪记录迷宫位置。用数组表示栈，栈用来存储从入口到当前位置的路径。

要确定从位置 here 开始向哪一个相邻位置移动，可以用下表的偏移量表来计算。在下表中，offset[i].row 和 offset[i].col 分别是从当前位置沿方向 i 移动到下一个相邻位置时，row 和 col 坐标的增量。

移动 方向 行偏移量 列偏移量
0 右 0 1
1 下 1 0
2 左 0 -1
3 上 -1 0

为了不重蹈已经走过的位置，在每一个走过的位置 maze[i][j] 上设置障碍物（即令 maze[i][j]=1）。

title
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/* 寻找迷宫路径代码 */
typedef struct position{
    int row;
    int col;
}position;
vector<vector<bool> > maze;      // 迷宫，假设是正方形
int size = maze.size();       // 迷宫大小
bool findPath(){
    // 寻找一条从入口（1，1）到达出口（size，size）的路径
    // 如果找到，返回true，否则返回false
    stack<position> *path = new stack<position>;
    // 初始化偏移量
    position offset[4];
    offset[0].row = 0; offset[0].col = 1;   // 右
    offset[1].row = 1; offset[1].col = 0;   // 下
    offset[2].row = 0, offset[2].col = -1;  // 左
    offset[3].row = -1; offset[3].col = 0;  // 上

    // 初始化迷宫外围的障碍墙
    for (int i = 0; i <= size + 1; ++i){
        maze[0][i] = maze[size + 1][i] = 1;     // 底部和顶部
        maze[i][0] = maze[i][size + 1] = 1;     // 左和右
    }

    position here;
    here.row = 1;
    here.col = 1;
    maze[1][1] = 1;
    int option = 0;             // 防止回到入口
    int lastOption = 3;         // 下一步

    // 寻找一条路径
    while (here.row != size || here.col != size){
        // 没有达到出口，找到要移动的相邻的一步
        int r, c;
        while (option <= lastOption){
            r = here.row + offset[option].row;
            c = here.col + offset[option].col;
            if (maze[r][c] == 0) break;
            ++option;
        }
        // 相邻的一步是否找到
        if (option <= lastOption){
            // 移动到maze[r][c]
            path->push(here);
            here.row = r;
            here.col = c;
            maze[r][c] = 1;         // 设置为1，避免重复访问
            option = 0;
        }else{
            // 没有邻近的一步可走，返回
            if (path->empty())  return false;       // 没有位置可返回
            position next = path->top();
            path->pop();
            if (next.row == here.row)
                option = 2 + next.col - here.col;
            else
                option = 3 + next.row - here.row;
            here = next;
        }
    }
    return true;            // 到达出口
}

时间复杂度：程序的时间复杂度应为 O(unblocked)，其中 unblocked 是迷宫的空闲位置数目。这个复杂度为 O(szie^2) = O(m^2)。