1
class Solution {
2
    class Tag {
3
    public:
4
        string value;
5
        bool isStart;
6
        Tag():value(""), isStart(true){}
7
        Tag(string value, bool isStart):value(value), isStart(isStart){}
8
    };
9

10
    pair<int, bool> parseCData(string& s, int pos) {
11
        //cout << "Parse cdata " << s.substr(pos) << endl;  
12
        const string startPattern = "<![CDATA[";
13
        if (s.find(startPattern, pos) != pos) {
14
            return {pos, false};
15
        }
16

17
        const string endPattern = "]]>";
18
        int end = s.find(endPattern, pos);
19
        if (end == -1) {
20
            return {pos, false};
21
        }
22
        return {end+3, true};
23
    }
24

25
    pair<Tag, bool> parseTag(string& s, int& pos) {
26
        //cout << "Parse tag " << s.substr(pos) << endl;
27
        Tag res;
28
        if (pos+1 == s.length()) return {res, false};
29
        if (s[pos+1] == '/') {
30
            res.isStart = false;
31
            pos++;
32
        }
33
        pos++;
34
        int end = s.find(">", pos);
35
        if (end == -1 || end-pos < 1 || end-pos > 9) return {res, false};
36
        string name = s.substr(pos, end-pos);
37
        for (char& c : name) {
38
            if (c < 'A' || c > 'Z') return {res, false};
39
        }
40
        res.value = name;
41
        pos = end+1;
42
        return {res, true};
43
    }
44
    bool isValid(vector<Tag>& tags, int start, int end) {
45
        //cout << start << " " << end << endl;
46
        if (start > end) return true;
47
        if (!tags[start].isStart) return false;
48
        int k = start+1;
49
        int c = 1;
50
        while (k <= end && c > 0) {
51
            if (tags[k].value == tags[start].value) {
52
                c += (tags[k].isStart) ? 1 : -1;
53
            }
54
            k++;
55
        }
56
        if (c != 0) return false;
57
        k--;
58
        return isValid(tags, start+1, k-1) && isValid(tags, k+1, end);
59
    }
60
public:
61
    bool isValid(string code) {
62
        vector<Tag> tags;
63
        int n = code.length();
64
        int i = 0;
65
        while (i < n) {
66
            int k = i;
67
            while (k < n && code[k] != '<') {
68
                k++;
69
            }
70
            if (k > i) {
71
                if (i == 0) return false;
72
                i = k;
73
                if (i == n) return false;
74
            } else {
75
                if (code[k+1] == '!') {
76
                    if (i == 0) return false;
77
                    auto cdata = parseCData(code, k);
78
                    if (!cdata.second) return false;
79
                    i = cdata.first;
80
                    if (i == n) return false;
81
                } else {
82
                    auto tag = parseTag(code, i);
83
                    if (!tag.second) return false;
84
                    if (i == n && tag.first.isStart) return false;
85
                    tags.push_back(tag.first);
86
                }
87
            }
88
        }
89
        if (tags.size() < 2) return false;
90
        int m = tags.size();
91
        if (tags[0].value != tags[m-1].value || !tags[0].isStart || tags[m-1].isStart){
92
            return false;
93
        }
94
        return isValid(tags, 1, m-2);
95
    }
96
};
97