Tag Validator

hard stack string

Problem

Validate an HTML-like tag string: must be a single outermost tag, every <TAG> needs </TAG>, tags 1-9 uppercase letters, and CDATA sections [CDATA[...]] are opaque.

Inputcode = '<DIV>This is the first line <![CDATA[<div>]]></DIV>'

OutputTrue

DIV opens and closes; CDATA inside is opaque.

input

def is_valid(code):
    import re
    if not code.startswith('<') or not code.endswith('>'): return False
    stack = []; i = 0
    while i < len(code):
        if stack and code.startswith('<![CDATA[', i):
            j = code.find(']]>', i)
            if j == -1: return False
            i = j + 3; continue
        if code.startswith('</', i):
            j = code.find('>', i)
            if j == -1: return False
            name = code[i+2:j]
            if not stack or stack.pop() != name: return False
            if not stack and j != len(code) - 1: return False
            i = j + 1; continue
        if code[i] == '<':
            j = code.find('>', i)
            if j == -1: return False
            name = code[i+1:j]
            if not re.fullmatch('[A-Z]{1,9}', name): return False
            stack.append(name); i = j + 1; continue
        if not stack: return False
        i += 1
    return not stack

function isValid(code) {
  if (!code.startsWith('<') || !code.endsWith('>')) return false;
  const stk = []; let i = 0;
  while (i < code.length) {
    if (stk.length && code.startsWith('<![CDATA[', i)) {
      const j = code.indexOf(']]>', i); if (j === -1) return false;
      i = j + 3; continue;
    }
    if (code.startsWith('</', i)) {
      const j = code.indexOf('>', i); if (j === -1) return false;
      const n = code.slice(i+2, j);
      if (!stk.length || stk.pop() !== n) return false;
      if (!stk.length && j !== code.length - 1) return false;
      i = j + 1; continue;
    }
    if (code[i] === '<') {
      const j = code.indexOf('>', i); if (j === -1) return false;
      const n = code.slice(i+1, j);
      if (!/^[A-Z]{1,9}$/.test(n)) return false;
      stk.push(n); i = j + 1; continue;
    }
    if (!stk.length) return false;
    i++;
  }
  return stk.length === 0;
}

boolean isValid(String code) {
    if (!code.startsWith("<") || !code.endsWith(">")) return false;
    Deque<String> stk = new ArrayDeque<>(); int i = 0;
    while (i < code.length()) {
        if (!stk.isEmpty() && code.startsWith("<![CDATA[", i)) {
            int j = code.indexOf("]]>", i); if (j == -1) return false; i = j + 3; continue;
        }
        if (code.startsWith("</", i)) {
            int j = code.indexOf('>', i); if (j == -1) return false;
            String n = code.substring(i+2, j);
            if (stk.isEmpty() || !stk.pop().equals(n)) return false;
            if (stk.isEmpty() && j != code.length()-1) return false;
            i = j + 1; continue;
        }
        if (code.charAt(i) == '<') {
            int j = code.indexOf('>', i); if (j == -1) return false;
            String n = code.substring(i+1, j);
            if (!n.matches("[A-Z]{1,9}")) return false;
            stk.push(n); i = j + 1; continue;
        }
        if (stk.isEmpty()) return false;
        i++;
    }
    return stk.isEmpty();
}

bool isValid(string code) {
    if (code.empty() || code[0] != '<' || code.back() != '>') return false;
    stack<string> stk; int i = 0, n = code.size();
    while (i < n) {
        if (!stk.empty() && i + 8 < n && code.substr(i, 9) == "<![CDATA[") {
            int j = code.find("]]>", i); if (j == string::npos) return false; i = j + 3; continue;
        }
        if (code.substr(i, 2) == "</") {
            int j = code.find('>', i); if (j == string::npos) return false;
            string t = code.substr(i+2, j-i-2);
            if (stk.empty() || stk.top() != t) return false; stk.pop();
            if (stk.empty() && j != n - 1) return false;
            i = j + 1; continue;
        }
        if (code[i] == '<') {
            int j = code.find('>', i); if (j == string::npos) return false;
            string t = code.substr(i+1, j-i-1);
            if (t.empty() || t.size() > 9) return false;
            for (char c : t) if (!isupper(c)) return false;
            stk.push(t); i = j + 1; continue;
        }
        if (stk.empty()) return false;
        i++;
    }
    return stk.empty();
}

Explanation

Validating nested tags is a classic stack job: every time a tag opens we remember its name, and every closing tag must match the most recently opened one — exactly what a stack's top gives us.

We scan the string with an index i and branch on what we see. A <![CDATA[ block is opaque, so we just skip ahead to its ]]> ending. A closing tag </NAME> must pop a name equal to NAME, otherwise it is invalid. An opening tag <NAME> must have a name of 1–9 uppercase letters, and we push it.

Several guard conditions keep things strict: the whole string must start with < and end with >; plain text is only allowed while the stack is non-empty (we must be inside a tag); and once the stack empties, we must be at the very end, ensuring there is a single outermost tag.

Example: <DIV>This is the first line <![CDATA[<div>]]></DIV>. We push DIV, treat the text as content, skip the CDATA block as opaque (so the fake <div> inside is ignored), then </DIV> pops and matches. The stack is empty at the end → valid.

If at the end the stack is empty and every check passed, the markup is well-formed.

Time: O(n) Space: O(n)