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

61
 public:
62
  bool isValid(string code) {
63
    vector<Tag> tags;
64
    int n = code.length();
65
    int i = 0;
66
    while (i < n) {
67
      int k = i;
68
      while (k < n && code[k] != '<') {
69
        k++;
70
      }
71
      if (k > i) {
72
        if (i == 0) return false;
73
        i = k;
74
        if (i == n) return false;
75
      } else {
76
        if (code[k + 1] == '!') {
77
          if (i == 0) return false;
78
          auto cdata = parseCData(code, k);
79
          if (!cdata.second) return false;
80
          i = cdata.first;
81
          if (i == n) return false;
82
        } else {
83
          auto tag = parseTag(code, i);
84
          if (!tag.second) return false;
85
          if (i == n && tag.first.isStart) return false;
86
          tags.push_back(tag.first);
87
        }
88
      }
89
    }
90
    if (tags.size() < 2) return false;
91
    int m = tags.size();
92
    if (tags[0].value != tags[m - 1].value || !tags[0].isStart || tags[m - 1].isStart) {
93
      return false;
94
    }
95
    return isValid(tags, 1, m - 2);
96
  }
97
};