5.9 如何判定括号合法性

本文对应的力扣题目：

20.有效的括号

给你输入一个字符串，其中包含 [](){} 六种括号，请你判断这个字符串组成的括号是否合法，函数签名如下：

bool isValid(string s);

5.9.1 处理一种括号

那么根据这个思路，我们可以写出算法：

bool isValid(string str) {
    // 待匹配的左括号数量
    int left = 0;
    for (char c : str) {
        if (c == '(')
            left++;
        else // 遇到右括号
            left--;

        if (left < 0)
            return false;
    }
    return left == 0;
}

5.9.2 处理多种括号

bool isValid(string str) {
    stack<char> left;
    for (char c : str) {
        if (c == '(' || c == '{' || c == '[') {
            // 左括号直接入栈
            left.push(c);
        } else {
            // 字符 c 是右括号
            if (!left.empty() && leftOf(c) == left.top())
                left.pop();
            else
                // 和最近的左括号不匹配
                return false;
        }
    }
    // 是否所有的左括号都被匹配了
    return left.empty();
}

// 返回对应的左括号类型
char leftOf(char c) {
    if (c == '}') return '{';
    if (c == ')') return '(';
    return '[';
}