Question

Please solve the following problem with programming using proper data structures. (Programming Language: Python)

A similar application to the parentheses matching problem comes from hypertext markup language (HTML). In HTML, tags exist in both opening and closing forms and must be balanced to properly describe a web document. This very simple HTML document:

Example>

Hello, world

is intended only to show the matching and nesting structure for tags in the language. Write a program that can check an HTML document for proper opening and closing tags.

To simplify the problem, we suppose the opening and closing tags are provided in separate lines without indentation (shown in the green box on the right above).

Consult the example on parentheses matching in lecture slides or the more general balanced symbol example in section 3.7 of the book at:

http://interactivepython.org/runestone/static/pythonds/BasicDS/BalancedSymbols(AGeneralCase).html.

Create a Stack abstract data type

The Stack class should include the following methods:

• push(item) function to add a new item to the stack
• pop() function to remove the top item from the stack
• peek() to return the top item in the stack
• is_empty() to test whether the stack is empty
• size() to tell the size (number of items) in the stack

Create a html_checker function

The function:

• Takes a string of HTML code as argument;
• Returns true if all tags are balanced; false if otherwise.

Here is what the function should do:

• Create a new Stack object;
• Use the split() method of a string to split it into text lines;
• Create a loop to read the text lines, and for each text line:
  • If the text line matches an opening tag (e.g.

    ), add the tag name (e.g. “h1”) to the stack;

  • If the text line is ordinary content without a HTML tag, skip the line;
  • If the text line is a closing tag (e.g. ), check whether the stack is empty():
    • The HTML code is unbalanced if stack is currently empty;
    • If not empty, use pop() to read and remove the top item from stack:
      • The top item/tag matches the current closing tag, then the HTML code is balanced (true);
      • Otherwise, the HTML code is unbalanced (false).

Program Execution

Create two variables, one with balanced HTML code and the other with unbalanced HTML code. Run the html_checker function with each of the two variables as argument to test the program.

Bonus:

Create a loop to read user input for multiple lines of HTML code (until the user hits a special key to signal the end) and run html_checker function on that input text.

Answer 1

Screenshot

----------------------------------------------------------

Program

#Create a class stack
class Stack:
     #Constructor
     def __init__(self):
         self.elements = []
     #Add element to stack
     def push(self, element):
         self.elements.append(element)
     #Remove from stack
     def pop(self):
         return self.elements.pop()
     #Get top element from stack
     def peek(self):
         return self.elements[len(self.elements)-1]
     #Check empty
     def is_empty(self):
         return self.elements == []
     #Check size of stack
     def size(self):
         return len(self.elements)
     #Override toString
     def __str__(self):
         if len(self.elements)==0:
             return ''
         tempString=''
         for i in range(len(self.elements)):
             tempString+=str(self.elements[i])+' '
         return tempString
#Method to check tag
def html_checker(htmlString):
    #Create a stack
    stack = Stack()
    #Create a list for each line
    lst = list()
    #Loop to get each line
    for line in htmlString:
        line = line.rstrip()
        lst.append(line)
    ind = 0
    #Check stach emty or balanced
    while ind < len(lst):
        for chr in lst[index]:
            if chr == '<':
                stack.push(ch)
            elif chr == '>':
                if stack.is_empty():
                    return False
                else:
                    stack.pop()
        ind += 1
    #If not empty return false
    return stack.is_empty()
#Test
def main():
    #Two string to check
   str1="<h1>This is a Heading</h1>"
   str2="<h1This is a Heading</h1>"
   if(html_checker(str1)):
       print("str1 Correct format")
   else:
       print("str1 Wrong format")

   if(html_checker(str2)):
       print("str2 Correct format")
   else:
       print("str2 Wrong format")
   str3=""
   inp=""
   print("Enter html instructions: ")
   while inp!="quit":
       inp=input()
       str3+=inp
     
   if(html_checker(str3)):
       print("str3 Correct format")
   else:
       print("str3 wrong format")
main()

-------------------------------------------------------

Output

str1 Correct format
str2 Wrong format
Enter html instructions:
<h1>This is a Heading</h1>
<p>This is a paragraph./p>
quit
str3 wrong format