You really enjoyed parsing and manipulating HTML using regular expressions and Python in Systems Programming. It was interesting to see a declarative language that just required you to format data using some HTML tags to describe what the text meant and not worry about control flow or anything complex like that.

In fact, because of how easy it is to use your favorite $EDITOR to create some HTML documents, you decide to make your own personal website using GitHub Pages. This is a free service that let's you make a public webpage using static HTML, which provides a convenient place to highlight your projects and interests!

After writing some custom HTML though, you realize that there is one problem when it comes to writing HTML by hand... it is sometimes difficult to keep track of all of the HTML tags and make sure that they are balanced.

For instance, the following is considered balanced:

The <i>quick</i> brown fox jumps over the <b>lazy</b> dog

That is, the opening of each tag (ie. <i> or <b>) is followed by the closing of each tag (ie. </i> or </b>).

The following, however, is not balanced:

The <i><u>quick</i></u> brown fox jumps over the <b>lazy</b> dog

In this example, the <u> tag is followed by the </i> closing tag before it encounters its corresponding </u> closing tag, and is thus considered unbalanced.

Your job is to write a simple HTML linter that checks if tags are properly balanced.

Input

The input consists of a series of lines that may or may not contain multiple HTML tags.

Here is an example input:

A <tt>tag</tt>
A <tt>tag
A <b><tt>tag</tt></b>
A <b><tt>tag</b></tt>

Note: You are only concerned with the tags and not with any of the text. Likewise, there are no attributes in these tags (eg. you may assume the tags are in the form <TAG> and </TAG>.

Output

For each line of HTML, you are to determine if the tags on that line is balanced or not and report the result.

Here is the output for the example input above:

Balanced
Unbalanced
Balanced
Unbalanced

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(N), where N corresponds to the length of the input string.
Space Complexity O(N), where N corresponds to the length of the input string.

Your solution may be below the targets, but it should not exceed them.

Submission

To submit your work, follow the same procedure you used for Reading 01:

$ cd path/to/cse-34872-su21-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge03               # Create and checkout challenge03 branch

$ $EDITOR challenge03/program.cpp           # Edit your code

$ git add challenge03/program.cpp           # Stage your changes
$ git commit -m "challenge03: done"         # Commit your changes

$ git push -u origin challenge03            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge03 program.cpp ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge03/program.cpp https://dredd.h4x0r.space/code/cse-34872-su21/challenge03
{"result": "Success", "score": 6, "time": 0.016292572021484375, "value": 6, "status": 0}

Pull Request

Once you have commited your work and pushed it to GitHub, remember to create a pull request and assign it to the teaching assistant.