Given a string representing a code snippet, implement a tag validator to parse the code and return whether it is valid.

A code snippet is valid if all the following rules hold:


	The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
	A closed tag (not necessarily valid) has exactly the following format : &lt;TAG_NAME&gt;TAG_CONTENT&lt;/TAG_NAME&gt;. Among them, &lt;TAG_NAME&gt; is the start tag, and &lt;/TAG_NAME&gt; is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
	A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.
	A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched &lt;, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.
	A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
	A &lt; is unmatched if you cannot find a subsequent &gt;. And when you find a &lt; or &lt;/, all the subsequent characters until the next &gt; should be parsed as TAG_NAME (not necessarily valid).
	The cdata has the following format : &lt;![CDATA[CDATA_CONTENT]]&gt;. The range of CDATA_CONTENT is defined as the characters between &lt;![CDATA[ and the first subsequent ]]&gt;.
	CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.


&nbsp;
Example 1:

Input: code = "&lt;DIV&gt;This is the first line &lt;![CDATA[&lt;div&gt;]]&gt;&lt;/DIV&gt;"
Output: true
Explanation: 
The code is wrapped in a closed tag : &lt;DIV&gt; and &lt;/DIV&gt;. 
The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata. 
Although CDATA_CONTENT has an unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as a tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.


Example 2:

Input: code = "&lt;DIV&gt;&gt;&gt;  ![cdata[]] &lt;![CDATA[&lt;div&gt;]&gt;]]&gt;]]&gt;&gt;]&lt;/DIV&gt;"
Output: true
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -&gt; "&lt;DIV&gt;"
end_tag -&gt; "&lt;/DIV&gt;"
tag_content could also be separated into : text1|cdata|text2.
text1 -&gt; "&gt;&gt;  ![cdata[]] "
cdata -&gt; "&lt;![CDATA[&lt;div&gt;]&gt;]]&gt;", where the CDATA_CONTENT is "&lt;div&gt;]&gt;"
text2 -&gt; "]]&gt;&gt;]"
The reason why start_tag is NOT "&lt;DIV&gt;&gt;&gt;" is because of the rule 6.
The reason why cdata is NOT "&lt;![CDATA[&lt;div&gt;]&gt;]]&gt;]]&gt;" is because of the rule 7.


Example 3:

Input: code = "&lt;A&gt;  &lt;B&gt; &lt;/A&gt;   &lt;/B&gt;"
Output: false
Explanation: Unbalanced. If "&lt;A&gt;" is closed, then "&lt;B&gt;" must be unmatched, and vice versa.


&nbsp;
Constraints:


	1 &lt;= code.length &lt;= 500
	code consists of English letters, digits, '&lt;', '&gt;', '/', '!', '[', ']', '.', and ' '.


class Solution:
    def isValid(self, code: str) -> bool:
        if code[0] != '<' or code[-1] != '>': return False
        i, n = 0, len(code)
        stk = []
        while i < n:
            if code[i] == '<':
                if i != 0 and code[i: i + 9] == '<![CDATA[':
                    if not stk: return False
                    j = i + 9
                    while j + 3 <= n and code[j: j + 3] != ']]>': j += 1
                    if code[j: j + 3] == ']]>': i = j + 3
                    else: return False
                else:
                    start = i
                    isend = False
                    i += 1
                    if i >= n: return False
                    if code[i] == r'/':
                        isend = True
                        i += 1
                    if i >= n: return False
                    tag = ''
                    while i < n and code[i] != '>':
                        if not code[i].isupper(): return False
                        tag += code[i]
                        i += 1
                    if i >= n or len(tag) == 0 or len(tag) > 9: return False
                    if isend:
                        if not stk or stk[-1] != tag: return False
                        stk.pop(-1)
                    else:
                        if start != 0 and not stk: return False
                        stk.append(tag)
                    i += 1
            else:
                if not stk: return False
                while i < n and code[i] != '<': i += 1
        return not stk
class Solution {
    // for the ease to check CDATA starting tag
    private static final char[] CDATA_TAG = {'[','C','D','A','T','A','['};
    public boolean isValid(String code) {
        // make sure it is possible to have a start tag and an end tag
        if (!code.startsWith("<") || !code.endsWith(">")) {
            return false;
        }
        Deque<String> stack = new ArrayDeque<>();
        for (int i = 0; i < code.length(); ++i) {
            char ch = code.charAt(i);
            // if it is a special tag
            if (ch == '<') {
                if (i == code.length() - 1) {
                    return false;
                }
                ch = code.charAt(++i);
                // is end tag
                if (ch == '/') {
                    // we should have a start tag to match the end tag
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // get the end tag
                    StringBuilder sb = new StringBuilder();
                    // build tag and move i to the > for the next round
                    i = buildTag(code, i + 1, sb);
                    // if tag is unmatch, return false
                    if (!stack.pop().equals(sb.toString())) {
                        return false;
                    }
                    // if no start tag left and we are not at the end. The rest content is not enclosed. -> false
                    if (stack.isEmpty() && i < code.length() - 1) {
                        return false;
                    }
                } else if (ch == '!') { // is CDATA tag
                    // check if CDATA is encoded in a tag
                    if (stack.isEmpty()) {
                        return false;
                    }
                    // check CDATA and move i to the end of ]]> for the next round
                    i = validAndMoveCDATA(code, i + 1);
                    // the above function return -1 if CDATA is not valid
                    if (i < 0) {
                        return false;
                    }
                } else { // start tag
                    // TAG_NAME should not empty
                    if (ch == '>') {
                        return false;
                    }
                    StringBuilder sb = new StringBuilder();
                    i = buildTag(code, i , sb);
                    // TAG_NAME should less than 9
                    if (sb.isEmpty() || sb.length() > 9) {
                        return false;
                    }
                    stack.push(sb.toString());
                }
            }
        }
        return stack.isEmpty();
    }

    private int buildTag(String code, int start, StringBuilder sb) {
        int i = start;
        // we only go to 10 because the max length is 9
        for (; i < start + 10 && i < code.length(); ++i) {
            char ch = code.charAt(i);
            // find the end;
            if (ch == '>') {
                break;
            }
            // TAG_NAME should be in uppercase only
            if (!Character.isUpperCase(ch)) {
                // clear the string builder for invalid TAG_NAME
                sb.setLength(0);
                break;
            }
            sb.append(ch);
        }
        return i;
    }

    private int validAndMoveCDATA(String code, int start) {
        // the length of [CDATA[]]> is 10 we need at least 10 characters left
        if (code.length() - start < 10) {
            return -1;
        }
        // check the start part
        int i = start;
        for (int j = 0; j < CDATA_TAG.length; ++j) {
            char ch = code.charAt(i++);
            if (ch != CDATA_TAG[j]) {
                return -1;
            }
        }
        // keep the last two characters for identifying the end
        char prev0 = '\0';
        char prev1 = '\0';

        for (; i < code.length(); ++i) {
            char ch = code.charAt(i);
            if (ch == '>' && prev1 == ']' && prev0 == ']') {
                return i;
            }
            prev0 = prev1;
            prev1 = ch;
        }
        // no end found
        return -1;
    }
}
class Solution {
    class Tag {
    public:
        string value;
        bool isStart;
        Tag():value(""), isStart(true){}
        Tag(string value, bool isStart):value(value), isStart(isStart){}
    };

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

        const string endPattern = "]]>";
        int end = s.find(endPattern, pos);
        if (end == -1) {
            return {pos, false};
        }
        return {end+3, true};
    }

    pair<Tag, bool> parseTag(string& s, int& pos) {
        //cout << "Parse tag " << s.substr(pos) << endl;
        Tag res;
        if (pos+1 == s.length()) return {res, false};
        if (s[pos+1] == '/') {
            res.isStart = false;
            pos++;
        }
        pos++;
        int end = s.find(">", pos);
        if (end == -1 || end-pos < 1 || end-pos > 9) return {res, false};
        string name = s.substr(pos, end-pos);
        for (char& c : name) {
            if (c < 'A' || c > 'Z') return {res, false};
        }
        res.value = name;
        pos = end+1;
        return {res, true};
    }
    bool isValid(vector<Tag>& tags, int start, int end) {
        //cout << start << " " << end << endl;
        if (start > end) return true;
        if (!tags[start].isStart) return false;
        int k = start+1;
        int c = 1;
        while (k <= end && c > 0) {
            if (tags[k].value == tags[start].value) {
                c += (tags[k].isStart) ? 1 : -1;
            }
            k++;
        }
        if (c != 0) return false;
        k--;
        return isValid(tags, start+1, k-1) && isValid(tags, k+1, end);
    }
public:
    bool isValid(string code) {
        vector<Tag> tags;
        int n = code.length();
        int i = 0;
        while (i < n) {
            int k = i;
            while (k < n && code[k] != '<') {
                k++;
            }
            if (k > i) {
                if (i == 0) return false;
                i = k;
                if (i == n) return false;
            } else {
                if (code[k+1] == '!') {
                    if (i == 0) return false;
                    auto cdata = parseCData(code, k);
                    if (!cdata.second) return false;
                    i = cdata.first;
                    if (i == n) return false;
                } else {
                    auto tag = parseTag(code, i);
                    if (!tag.second) return false;
                    if (i == n && tag.first.isStart) return false;
                    tags.push_back(tag.first);
                }
            }
        }
        if (tags.size() < 2) return false;
        int m = tags.size();
        if (tags[0].value != tags[m-1].value || !tags[0].isStart || tags[m-1].isStart){
            return false;
        }
        return isValid(tags, 1, m-2);
    }
};
class Solution {
    class Tag {
    public:
        string value;
        bool isStart;
        Tag():value(""), isStart(true){}
        Tag(string value, bool isStart):value(value), isStart(isStart){}
    };
    
    pair<int, bool> parseCData(string& s, int pos) {
        //cout << "Parse cdata " << s.substr(pos) << endl;  
        const string startPattern = "<![CDATA[";
        if (s.find(startPattern, pos) != pos) {
            return {pos, false};
        }
        
        const string endPattern = "]]>";
        int end = s.find(endPattern, pos);
        if (end == -1) {
            return {pos, false};
        }
        return {end+3, true};
    }
    
    pair<Tag, bool> parseTag(string& s, int& pos) {
        //cout << "Parse tag " << s.substr(pos) << endl;
        Tag res;
        if (pos+1 == s.length()) return {res, false};
        if (s[pos+1] == '/') {
            res.isStart = false;
            pos++;
        }
        pos++;
        int end = s.find(">", pos);
        if (end == -1 || end-pos < 1 || end-pos > 9) return {res, false};
        string name = s.substr(pos, end-pos);
        for (char& c : name) {
            if (c < 'A' || c > 'Z') return {res, false};
        }
        res.value = name;
        pos = end+1;
        return {res, true};
    }
    bool isValid(vector<Tag>& tags, int start, int end) {
        //cout << start << " " << end << endl;
        if (start > end) return true;
        if (!tags[start].isStart) return false;
        int k = start+1;
        int c = 1;
        while (k <= end && c > 0) {
            if (tags[k].value == tags[start].value) {
                c += (tags[k].isStart) ? 1 : -1;
            }
            k++;
        }
        if (c != 0) return false;
        k--;
        return isValid(tags, start+1, k-1) && isValid(tags, k+1, end);
    }
public:
    bool isValid(string code) {
        vector<Tag> tags;
        int n = code.length();
        int i = 0;
        while (i < n) {
            int k = i;
            while (k < n && code[k] != '<') {
                k++;
            }
            if (k > i) {
                if (i == 0) return false;
                i = k;
                if (i == n) return false;
            } else {
                if (code[k+1] == '!') {
                    if (i == 0) return false;
                    auto cdata = parseCData(code, k);
                    if (!cdata.second) return false;
                    i = cdata.first;
                    if (i == n) return false;
                } else {
                    auto tag = parseTag(code, i);
                    if (!tag.second) return false;
                    if (i == n && tag.first.isStart) return false;
                    tags.push_back(tag.first);
                }
            }
        }
        if (tags.size() < 2) return false;
        int m = tags.size();
        if (tags[0].value != tags[m-1].value || !tags[0].isStart || tags[m-1].isStart){
            return false;
        }
        return isValid(tags, 1, m-2);
    }
};
Tag Validator