Задача: 591. Tag Validator
Сложность: hard

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

👨‍💻 Алгоритм:

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

class Solution {
    private $stack = [];
    private $containsTag = false;

    private function isValidTagName($s, $ending) {
        if ($ending) {
            if (!empty($this->stack) && end($this->stack) === $s) {
                array_pop($this->stack);
            } else {
                return false;
            }
        } else {
            $this->containsTag = true;
            $this->stack[] = $s;
        }
        return true;
    }

    public function isValid($code) {
        $regex = "/<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/";
        if (!preg_match($regex, $code)) {
            return false;
        }

        $i = 0;
        while ($i < strlen($code)) {
            $ending = false;
            if (empty($this->stack) && $this->containsTag) {
                return false;
            }
            if ($code[$i] === '<') {
                if ($code[$i + 1] === '!') {
                    $i = strpos($code, "]]>", $i + 1);
                    if ($i === false) {
                        return false;
                    }
                    continue;
                }
                if ($code[$i + 1] === '/') {
                    $i++;
                    $ending = true;
                }
                $closeIndex = strpos($code, '>', $i + 1);
                if ($closeIndex === false || !$this->isValidTagName(substr($code, $i + 1, $closeIndex - $i - 1), $ending)) {
                    return false;
                }
                $i = $closeIndex;
            }
            $i++;
        }
        return empty($this->stack);
    }
}

Ставь 👍 и забирай 📚 Базу знаний