# HTML Parser How would you parse out HTML tags from a string? **Example:** ``` input:

My First Heading

My first paragraph.

--- output: [('h1', 'My First Heading'), ('p', 'My first paragraph.'), ('body', '\n\n

My First Heading

\n

My first paragraph.

\n\n'), ('html', '\n\n\n

My First Heading

\n

My first paragraph.

\n\n\n'), ``` **Note:** This is not meant to be a completely robust implementation. It obviously does not parse every aspect of html. **The Idea:** The key is to identify the grammar of an html tag, and use a stack to facilitate the deconstruction of the string. An html tag has the following simple grammar: `html ::= '<' tag '>' exp ''` where tag and exp are arbitrary strings. Each token can be uniquely identified on the basis of what came before it within the stack. **Complexity:** O(n) time and O(n) space (consider the html string: `'b'`) ```python from enum import Enum class Token(Enum): OPEN1 = 1 OPEN2 = 2 CLOSE1 = 3 CLOSE2 = 4 def html_parser(html_str): init_html = len("") assert(html_str[0:init_html] == "") html_str = html_str[init_html:] tag_expr = [] s = [] for i, char in enumerate(html_str): # this if statement is ultimately just a placeholder for the second statement if char == '<' and i+1 < len(html_str) and html_str[i+1] != '/': s.append((i, Token.OPEN1)) # this will be used to identify the start of the expression elif char == '>' and len(s) != 0 and s[-1][1] == Token.OPEN1: s.pop() s.append((i, Token.CLOSE1)) # this identifies the end of the expression elif char == '<' and i+1 < len(html_str) and s[-1][1] == Token.CLOSE1: tmp_expr = html_str[s[-1][0] + 1:i] s.pop() s.append((i, Token.OPEN2)) # this identifies the tag name (see that the first tag name is ignored) elif char == '>' and len(s) != 0 and s[-1][1] == Token.OPEN2: tmp_tag = html_str[s[-1][0] + 2:i] tag_expr.append((tmp_tag, tmp_expr)) s.pop() return tag_expr ``` **Testing** ```python ex_doc1 = \ """

My First Heading

My first paragraph.

""" print(html_parser(ex_doc1)) ex_doc2 = \ """

This paragraph contains a lot of lines in the source code, but the browser ignores it.

This paragraph contains a lot of spaces in the source code, but the browser ignores it.

The number of lines in a paragraph depends on the size of the browser window. If you resize the browser window, the number of lines in this paragraph will change.

""" print(html_parser(ex_doc2)) ```