栈的经典应用之括号匹配

缘起

进入第二阶段修行之后，又开始捡起当时刷oj的习惯（毕竟有一颗去大厂的心）. 无奈大约2年半一直沉溺于java的前端+后端, 无暇顾及算法. 于是重新开始捡起毕竟有一些痛苦. 但是一定要忍住. 现在的计划是把下面两本书扫完, 掌握基本的数据结构和算法板子之后，就重新开始刷oj和算法竞赛书籍.

  1. 清华大学计算机系列教材:数据结构(C++语言版)(第3版) 邓俊辉
  2. 啊哈,算法

前者是主流的大学教材, 还是要过一遍的（当时看的是严蔚敏奶奶的~ 但是太老了，而且想用C++ 而不是C）

而且里面谈及的数据结构比较全. 有跳表、伸展树等高级数据结构.

但是其实大学教材写的一般比较”高大上”. 其实这里想吐槽一下, 1 中大量使用了模板类. 为的是让写的代码能更加的通用. 但是作者有没有想过没有? 这是算法课诶~ 不是软件工程课诶~ 算法最重要的是讲清楚思想. 其实通用性完全可以后期通过软工课程进行包装的. 不需要在这里写的这么完备. 我是有一定的算法基础才来看这本书的(毫无自吹想法，勿喷). 我认为小白会望而却步. 而且也不利于提炼打比赛用的算法板子. 所以才有了第二本书. 这本书其实我看过, 里面用的是相当基础的数据结构就把复杂算法实现了一遍, 并且是从例子（类似于acm的题目）出发的. 不至于枯燥.

所以我阅读第一本书的思路是看思想, 然后到往上找看的顺眼的板子实现. 因为不能ac的算法都是耍流氓. 所以这两本书都是以扫为主. 弄清思想即可，不想手把手的敲（因为不能ac，所以不知道你这样敲下的算法有没有bug），没有意义. 大量oj训练才是学习算法的王道. 当然，要结合一下java，重点关注一下hashmap的实现（高级java面试必问，当时我说只知道是红黑树+链表实现的. 相当的无力感）

最后说一下算法在IT中的作用， 我一直这么认为, 架构是军师，算法是将军. 前者运筹帷幄，后者攻城拔寨. 所以你说哪个重要，哪个不重要呢? 都很重要. 而且我偏向于后者. 其实我一直想干的事情是阅读一些经典的java框架的代码, 然后看看能不能杂糅一些高效的算法进去，改造成适宜企业的更加顺手的框架. 这就是我想做的事情.

好了, 言归正传. 我们看看教材1的栈这一章的经典应用——括号匹配算法.

需求就是给出一个带”[{(“表达式字符串. 要判定是否合法. 例如

(1+2*4 是不合法的

(1+2)*4 是合法的

分析

使用栈来维护输入的字符串中的([{}]), 来的是左[小、中、大]括号就压栈, 来的是右[小、中、大]括号就弹栈, 一旦来的右边的没遇到匹配的, 就判定不合法. 如果匹配的话, 就弹栈（类似于消消乐）. 如果一直没报错, 就代表正确.

代码如下

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
#include <iostream>
#include <stack>
using namespace std;

bool valid(char bracket[]) {
    // 维护括号的栈
    stack<char> s;
    int i = 0;
    while(bracket[i]) { // c/c++ 语法就是简洁,喜欢
        switch(bracket[i]) {
        case '{':
        case '[':
        case '(':
                // 碰到左边的就压栈
            s.push(bracket[i]);
            break;
        case ')':
                // 遇到右边的括号就开始玩消消乐, 如果玩不了，就报错
            if(s.empty() || s.top() != '(') {
                return false;
            }
                // 能玩，就消掉了
            s.pop();
            break;
        case ']':
            if(s.empty() || s.top() != '[') {
                return false;
            }
            s.pop();
            break;
        case '}':
            if(s.empty() || s.top() != '{') {
                return false;
            }
            s.pop();
            break;
                // 其他字符统统忽略
        default:
            break;
        }
        i++;
    }
    return true;
}

int main() {
    char bracket[100];
    cout << "请输入括号表达式: " << endl;
    // 读取一行
    cin.getline(bracket, 100);
    bool result = valid(bracket);
    cout << (result?"合法":"不合法") << endl;
    return 0;
}