栈：平衡符号

0020. 有效的括号 (opens new window)

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

解析

遍历字符串，每遇到一个左括号时，将与其匹配的右括号入栈；当遇到右括号时，与栈顶元素比较配对，不一致则匹配失败。

代码

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> pairs = {
            {'(', ')'}, {'{', '}'}, {'[', ']'}
        };
        stack<char> stk;
        for (int i = 0; i < s.length(); i++) {
            if (pairs.find(s[i]) != pairs.end()) {
                stk.push(pairs[s[i]]);
            } else {
                if (stk.empty() || stk.top() != s[i]) {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }
};

func isValid(s string) bool {
    pairs := map[byte]byte{
        '(': ')', '{': '}', '[': ']',
    }
    var stk []byte
    for i := 0; i < len(s); i++ {
        if p, ok := pairs[s[i]]; ok {
            stk = append(stk, p)
        } else {
            if len(stk) == 0 || stk[len(stk)-1] != s[i] {
                return false
            }
            stk = stk[:len(stk)-1]
        }
    }
    return len(stk) == 0
}

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            '(': ')', '{': '}', '[': ']'
        }
        stk = []
        for i in range(len(s)):
            if s[i] in pairs:
                stk.append(pairs[s[i]])
            else:
                if not stk or stk[-1] != s[i]:
                    return False
                stk = stk[:-1]
        return not stk

0591. 标签验证器 (opens new window)

题目

给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：

1. 代码必须被合法的闭合标签包围。否则，代码是无效的。
2. 闭合标签（不一定合法）要严格符合格式：<TAG_NAME>TAG_CONTENT</TAG_NAME>。其中，<TAG_NAME> 是起始标签，</TAG_NAME> 是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都是合法的，闭合标签才是合法的。
3. 合法的 TAG_NAME 仅含有大写字母，长度在范围 [1,9] 之间。否则，该 TAG_NAME 是不合法的。
4. 合法的 TAG_CONTENT 可以包含其他合法的闭合标签，cdata （请参考规则7）和任意字符（注意参考规则1）除了不匹配的<、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，TAG_CONTENT 是不合法的。
5. 一个起始标签，如果没有具有相同 TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
6. 一个 <，如果你找不到一个后续的 > 与之匹配，是不合法的。并且当你找到一个 < 或 </ 时，所有直到下一个 > 的前的字符，都应当被解析为 TAG_NAME（不一定合法）。
7. cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]> 之间的字符。
8. CDATA_CONTENT 可以包含任意字符。cdata 的功能是阻止验证器解析 CDATA_CONTENT，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。

解析

题目很长，其实简单来说就是下面两个规则：

• TAG 必须包含 Start Tag & End Tag，Ex：<ABC> </ABC>；
• 如果出现 <![CDATA["，中间的内容完全不用管，直到出现 "]]> 表示结束。

所以重点在于 "<" 这个符号出现，后面会有 3 种情况：

• <!：表示有可能是 CDATA；
• </：表示有可能是 End Tag；
• <X：表示有可能是 Start Tag。

下面只需要分类讨论即可。

代码

class Solution {
public:
    bool isValid(string code) {
        stack<string> stk;
        for (int i = 0; i < code.length(); ) {
            // 未被标签包围，无效
            if (i > 0 && stk.empty()) {
                return false;
            }
            if (code.find("<![CDATA[", i) == i) {
                i = code.find("]]>", i + 9);
                // 标签缺失，无效
                if (i == code.npos) {
                    return false;
                }
                i += 3;
            } else if (code.find("</", i) == i) {
                int j = i + 2;
                i = code.find(">", j);
                // 标签缺失 / 标签空 / 标签过长，无效
                if (i == code.npos || i == j || i - j > 9) {
                    return false;
                }
                // 标签含小写字母，无效
                for (int k = j; k < i; k++) {
                    if (!isupper(code[k])) return false;
                }
                string s = code.substr(j, i++ - j + 1);
                // 标签匹配失败，无效
                if (stk.empty() || stk.top() != s) {
                    return false;
                }
                stk.pop();
            } else if (code.find("<", i) == i) {
                int j = i + 1;
                i = code.find(">", j);
                // 标签缺失 / 标签空 / 标签过长，无效
                if (i == code.npos || i == j || i - j > 9) {
                    return false;
                }
                // 标签含小写字母，无效
                for (int k = j; k < i; k++) {
                    if (!isupper(code[k])) return false;
                }
                string s = code.substr(j, i++ - j + 1);
                stk.push(s);
            } else {
                i++;
            }
        }
        return stk.empty();
    }
};