Checking balance of nested < >'s

[Roadrunner2015]

Hello I had a quick question about how to check the balance of brackets in an HTML file using a stack (pushing and popping). I understand pushing and popping. I get lost when it comes to the logic of having to actually check what is in the brackets, and making sure those are nested correctly.

So while

<title><b> THIS FILE </b> USES CORRECTLY NESTED TAGS </title>

is correct and

<title> <b> THIS FILE </title> IS </b> NOT NESTED CORRECTLY.

is incorrect;

How do I check for the actual tags inside the brackets, keeping in mind that there are single sided tags as well. (ex. <img src="a.jpg"/>)

[anduril462]

How would you do this by hand? Get a pencil and paper. As you come across an open tag, push it on a stack. When you come across a close tag, how would you know whether it matches the most recently opened tag? What would you look at?

As for the single-sided tags, think of it sort of as an open and close tag with no data in between, except you know the close tag is there even before you finish the open tag -- so you don't even really need to push.

Note: if this is for a personal project, or just to learn the concepts, that is fine. If you intend on using this in a professional setting, there are a number of free, open-source, permissively-licensed HTML and XML libraries, that check well-formedness for you (among other things), and have lots of other great features.

[Roadrunner2015]

I'm not sure how I could distinguish between a one sided tag and an open or close tag when coming across the first <?

Also, I am not sure how to check.. lets say... if the first <title> tag matches with the </title> tag and not just the </b> tag.

I understand the whole pushing and popping, I am confused on the logic to read in an open tag and then compare it to the next closing tag and checking that they are both "title" tags or "bold" tags.

[Roadrunner2015]

I don't see the difference in comparing

<title><b>Hey</b></title>

with

<title><b>Hey</title></b>


I understand that they are obviously different and the second example being wrong... but do i strtok() the '/' out and check for == then?

[Roadrunner2015]

here would be my stack after pushing <title> and <b>

-
-
-
<b>
<title>


I now come across </title> (its wrong!) and i pop the stack..... so from there do i strtok() the '/' out of </title> and compare <b> with <title> and if they don't match then it is wrong??

But if </b> came before i would strtok() '/' out of </b> and check if <b> and <b> match... and it would be right??

[anduril462]

here would be my stack after pushing <title> and <b>

-
-
-
<b>
<title>


I now come across </title> (its wrong!) and i pop the stack..... so from there do i strtok() the '/' out of </title> and compare <b> with <title> and if they don't match then it is wrong??

But if </b> came before i would strtok() '/' out of </b> and check if <b> and <b> match... and it would be right??

Exactly.

I'm not sure how I could distinguish between a one sided tag and an open or close tag when coming across the first <?

Also, I am not sure how to check.. lets say... if the first <title> tag matches with the </title> tag and not just the </b> tag.

I understand the whole pushing and popping, I am confused on the logic to read in an open tag and then compare it to the next closing tag and checking that they are both "title" tags or "bold" tags.

Why do you need to know at the first '<' ? What's wrong with reading all the way until the '>' that closes the tag before you do anything with it. In fact, how would you ever know anything about the tag at the point of the first '<' ?

[Roadrunner2015]

would it be better to use char *str or an array of characters? (str[xxx])

[anduril462]

would it be better to use char *str or an array of characters? (str[xxx])

Maybe. That's as specific as I can get unless you're more specific. What is the overall purpose of this program? What part of the program are you asking about (a blanket rule for the whole program is a bad idea)? What type of system are you on (small embedded that never reboots, desktop application that is "run and done") and what are the constraints, if any?

I could probably list a dozen more questions that may help decide, but this should give you an idea of the amount of context required to properly answer this question.

[Click_here]

My approach would be to create a function which looked for the next <apple> -> It's an opening, so push it on a stack.
Search for the next <banana> -> It's an opening, so push it on the stack.
Search for next one, which happens to be </banana> -> It's a closing, so I pop the last one off the stack and compare it. Because the last element put on the stack was banana, I know that no error occured.

I search for the next element which happens to be <grape> -> Opening, so on the stack it goes.

The next element found is </apple> -> Closing, so I pop the last one off the stack and compare it to "apple". You can see that the last one on was "grape", so you know that an error has occured. The next step would be to print an error message to the user saying something like, "expected "grape", but found "apple" on line nnn"