I received an assignment from my lecturer to make an HTML Validator using stacks. I fail to wrap my head around the algorithm to do so, since stacks can only do LIFO, what am I supposed to do to check if a tag has been closed or not? Is it possible? Any answer would be helpful, since I've been stuck for a few days now. Thanks in advance!
Btw, my lecturer gave me an example to run:
<html>
<head>
<title>
Example
</title>
</head>
<body>
<h1>Hello, world</h1>
</body>
</html>
CodePudding user response:
In a stack you push new elements on top and remove them by popping the most recent element. So you could push opening tags on the stack until there is a closing tag, then check the element on the top of the stack if it matches the closing tag. If another opening tag appears after the closing tag, simply push it on the stack again and continue this until reaching the last element on the stack. If every element has a matching closing tag, the html document should be valid.
Pseudo code:
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
}
}