591.标签验证器

链接：591.标签验证器
难度：Hard
标签：栈、字符串
简介：给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。

题解 1 - cpp

• 编辑时间：2022-05-02
• 内存消耗：6.5MB
• 编程语言：cpp
• 解法介绍：栈存每一层，再遍历字符串。

#ifdef DEBUG
#define log(fmt, args...) \
    { printf(fmt, ##args); }
#else
#define log(fmt, args...)
#endif
class Solution {
   public:
    int i = 0, n;
    bool check = true;
    stack<string> s;
    string code;
    bool isValid(string code) {
        this->code = code;
        n = code.size();
        log("n = %d\n", n);
        // 最外层一定要是tag
        if (code[0] != '<' || code[n - 1] != '>') return false;
        while (i < n) {
            // 检测tag开始
            if (code[i] == '<') {
                // 检测CDATA
                if (i + 1 < n && code[i + 1] == '!') {
                    // CDATA一定要在tag里
                    if (s.empty()) return false;
                    analysisCDATATag();
                    log("end analysisCDATATag : i = %d\n", i);
                    if (!check) return false;
                } else {
                    // 检测tag
                    analysisTag();
                    log("end analysisTag : i = %d\n", i);
                    // 如果栈空了，但检测没结束，就有问题
                    if (!check || s.empty() && i != n) return false;
                }
            }
            // 直接到下一个<
            while (i < n && code[i] != '<') i++;
        }
        log("end check");
        // 最后看看是不是栈空
        return s.empty();
    }
    void analysisTag() {
        // 先拿到结尾下标
        int end = i;
        while (end < n && code[end] != '>') end++;
        // 没结尾就不对了
        if (end == n) {
            check = false;
            return;
        }
        // 看看是endTag还是startTag
        if (i + 1 < n && code[i + 1] == '/') {
            // endTag先过滤斜线
            i += 1;
            string tag = analysisCommonTag(end);
            // 跳跃
            i = end + 1;
            // 如果tag解析不出来就不对了
            if (tag != "") {
                log("find end  tag : %s\n", tag.data());
                // 如果endTag解析出来了但栈空或栈顶没匹配的也不对
                if (s.empty() || s.top() != tag) check = false;
                // 对了就出栈
                else
                    s.pop();
                return;
            } else
                check = false;
        } else {
            // 解析startTag
            string tag = analysisCommonTag(end);
            i = end + 1;
            if (tag != "") {
                log("find start tag : %s\n", tag.data());
                // 对了就入栈
                s.push(tag);
                return;
            } else
                check = false;
        }
    }
    string analysisCommonTag(int end) {
        string ans = "";
        // 长度 [1, 9]
        if (end == i + 1 || end - i - 1 > 9) return "";
        // 都是大写字符
        for (int start = i + 1; start < end; start++) {
            if (!isupper(code[start])) return "";
            ans += code[start];
        }
        return ans;
    }
    string startWith_cdata = "<![CDATA[";
    string endWith_cdata = "]]>";
    void analysisCDATATag() {
        log("anasysisCDATATAG, i = %d\n", i);
        // 先看看能不能匹配开始标记
        int start = i, startMatchCnt = 0;
        while (start < n && startMatchCnt != startWith_cdata.size()) {
            if (code[start] == startWith_cdata[startMatchCnt])
                startMatchCnt++;
            else
                break;
            start++;
        }
        // 匹配不上就错了
        if (start == n || startMatchCnt != startWith_cdata.size()) {
            check = false;
            return;
        }
        // 再看看能不能匹配结束标记
        log("find start = %d\n", start);
        int end = start, endMatchCnt = 0;
        // 一直循环找]开头的进行尝试
        while (true) {
            endMatchCnt = 0;
            while (end < n && code[end] != endWith_cdata[0]) end++;
            while (end < n && endMatchCnt != endWith_cdata.size()) {
                if (code[end] == endWith_cdata[endMatchCnt])
                    endMatchCnt++;
                else
                    break;
                end++;
            }
            log("end = %d\n", end);
            if (end == n || endMatchCnt == endWith_cdata.size()) break;
        }
        // 匹配不上就错了
        // 匹配上就跳跃了
        if (end == n) {
            check = false;
        } else {
            log("find cdata tag : start = %d, end = %d\n", start, end);
            i = end;
        }
    }
};