Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <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
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
public class Solution {
private Stack<string> stack = new Stack<string>();
private bool containsTag = false;
private bool IsValidTagName(string s, bool ending) {
if (ending) {
if (stack.Count > 0 && stack.Peek() == s) stack.Pop();
else return false;
} else {
containsTag = true;
stack.Push(s);
}
return true;
}
public bool IsValid(string code) {
string pattern = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*";
if (!Regex.IsMatch(code, pattern)) return false;
for (int i = 0; i < code.Length; i++) {
bool ending = false;
if (stack.Count == 0 && containsTag) return false;
if (code[i] == '<') {
if (code[i + 1] == '!') {
i = code.IndexOf("]]>", i + 1);
if (i == -1) return false;
continue;
}
if (code[i + 1] == '/') {
i++;
ending = true;
}
int closeIndex = code.IndexOf('>', i + 1);
if (closeIndex == -1 || !IsValidTagName(code.Substring(i + 1, closeIndex - (i + 1)), ending)) return false;
i = closeIndex;
}
}
return stack.Count == 0;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private stack<string> stack = new stack<string>();
private bool containsTag = false;
private bool IsValidTagName(string s, bool ending) {
if (ending) {
if (stack.size() > 0 && stack.Peek() == s) stack.pop();
else return false;
} else {
containsTag = true;
stack.push(s);
}
return true;
}
public bool IsValid(string code) {
string pattern = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*";
if (!Regex.IsMatch(code, pattern)) return false;
for (int i = 0; i < code.size(); i++) {
bool ending = false;
if (stack.size() == 0 && containsTag) return false;
if (code[i] == '<') {
if (code[i + 1] == '!') {
i = code.IndexOf("]]>", i + 1);
if (i == -1) return false;
continue;
}
if (code[i + 1] == '/') {
i++;
ending = true;
}
int closeIndex = code.IndexOf('>', i + 1);
if (closeIndex == -1 || !IsValidTagName(code.Substring(i + 1, closeIndex - (i + 1)), ending)) return false;
i = closeIndex;
}
}
return stack.size() == 0;
}
}Java решение
сопоставлено/оригиналimport java.util.regex.*;
public class Solution {
Stack<String> stack = new Stack<>();
boolean containsTag = false;
public boolean isValidTagName(String s, boolean ending) {
if (ending) {
if (!stack.isEmpty() && stack.peek().equals(s)) stack.pop();
else return false;
} else {
containsTag = true;
stack.push(s);
}
return true;
}
public boolean isValid(String code) {
if (!Pattern.matches("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*", code))
return false;
for (int i = 0; i < code.length(); i++) {
boolean ending = false;
if (stack.isEmpty() && containsTag) return false;
if (code.charAt(i) == '<') {
if (code.charAt(i + 1) == '!') {
i = code.indexOf("]]>", i + 1);
continue;
}
if (code.charAt(i + 1) == '/') {
i++;
ending = true;
}
int closeIndex = code.indexOf('>', i + 1);
if (closeIndex < 0 || !isValidTagName(code.substring(i + 1, closeIndex), ending))
return false;
i = closeIndex;
}
}
return stack.isEmpty();
}
}JavaScript решение
сопоставлено/оригиналclass Solution {
constructor() {
this.stack = [];
this.containsTag = false;
}
isValidTagName(s, ending) {
if (ending) {
if (this.stack.length > 0 && this.stack[this.stack.length - 1] === s) {
this.stack.pop();
} else {
return false;
}
} else {
this.containsTag = true;
this.stack.push(s);
}
return true;
}
isValid(code) {
const regex = /<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/;
if (!regex.test(code)) {
return false;
}
for (let i = 0; i < code.length; i++) {
let ending = false;
if (this.stack.length === 0 && this.containsTag) {
return false;
}
if (code[i] === '<') {
if (code[i + 1] === '!') {
i = code.indexOf("]]>", i + 1);
if (i === -1) {
return false;
}
continue;
}
if (code[i + 1] === '/') {
i++;
ending = true;
}
const closeIndex = code.indexOf('>', i + 1);
if (closeIndex === -1 || !this.isValidTagName(code.slice(i + 1, closeIndex), ending)) {
return false;
}
i = closeIndex;
}
}
return this.stack.length === 0;
}
}Python решение
сопоставлено/оригиналimport re
class Solution:
def __init__(self):
self.stack = []
self.contains_tag = False
def is_valid_tag_name(self, s, ending):
if ending:
if self.stack and self.stack[-1] == s:
self.stack.pop()
else:
return False
else:
self.contains_tag = True
self.stack.append(s)
return True
def isValid(self, code: str) -> bool:
pattern = re.compile(r"<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*")
if not pattern.fullmatch(code):
return False
i = 0
while i < len(code):
ending = False
if not self.stack and self.contains_tag:
return False
if code[i] == '<':
if code[i + 1] == '!':
i = code.find("]]>", i + 1)
if i == -1:
return False
continue
if code[i + 1] == '/':
i += 1
ending = True
close_index = code.find('>', i + 1)
if close_index == -1 or not self.is_valid_tag_name(code[i + 1:close_index], ending):
return False
i = close_index
i += 1
return not self.stackGo решение
сопоставлено/оригиналpackage main
import (
"regexp"
"strings"
)
type Solution struct {
stack []string
containsTag bool
}
func (s *Solution) isValidTagName(tag string, ending bool) bool {
if ending {
if len(s.stack) > 0 && s.stack[len(s.stack)-1] == tag {
s.stack = s.stack[:len(s.stack)-1]
} else {
return false
}
} else {
s.containsTag = true
s.stack = append(s.stack, tag)
}
return true
}
func (s *Solution) IsValid(code string) bool {
regex := "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
matched, _ := regexp.MatchString(regex, code)
if !matched {
return false
}
for i := 0; i < len(code); i++ {
ending := false
if len(s.stack) == 0 && s.containsTag {
return false
}
if code[i] == '<' {
if code[i+1] == '!' {
i = strings.Index(code[i+1:], "]]>") + i + 2
if i == -1 {
return false
}
continue
}
if code[i+1] == '/' {
i++
ending = true
}
closeIndex := strings.Index(code[i+1:], ">") + i + 1
if closeIndex == -1 || !s.isValidTagName(code[i+1:closeIndex], ending) {
return false
}
i = closeIndex
}
}
return len(s.stack) == 0
}Algorithm
Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.
Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.
В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.