C++ — создание HTML-валидатора с использованием стека
Я получил задание от своего лектора сделать HTML-валидатор с использованием стеков. Я не могу понять алгоритм, чтобы сделать это, поскольку стеки могут выполнять только LIFO, что я должен сделать, чтобы проверить, был ли тег закрыт или нет? Является ли это возможным? Любой ответ будет полезен, так как я застрял на несколько дней. Заранее спасибо!
Кстати, мой лектор дал мне пример для запуска:
<html>
<head>
<title>
Example
</title>
</head>
<body>
<h1>Hello, world</h1>
</body>
</html>
Ответы 1
В стеке вы помещаете новые элементы сверху и удаляете их, извлекая самый последний элемент. Таким образом, вы можете помещать открывающие теги в стек до тех пор, пока не появится закрывающий тег, а затем проверить элемент в верхней части стека, если он соответствует закрывающему тегу. Если после закрывающего тега появляется еще один открывающий тег, просто поместите его в стек еще раз и продолжайте до тех пор, пока не достигнете последнего элемента в стеке. Если каждый элемент имеет соответствующий закрывающий тег, HTML-документ должен быть действительным.
Псевдокод:
while (has_unresolved_tags) {
if (is_opening_tag) {
stack.push(opening_tag);
} else {
// peek the last element of the stack
if (stack.peek() == closing tag of opening tag) {
stack.pop()
} else {
// not a valid html document, exit
}
}
Спасибо. Ваш псевдокод работает! Я реализовал это, проверив, пуст ли стек, и поместил его в стек, если он был.