Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Matching HTML Tags

+1 voto
59 visitas
perguntada Out 27, 2020 em Programação Computacional por Andrei Leite (21 pontos)  

(GOODRICH, Michael T., TAMASSIA, Roberto e GOLDWASSER, Michael H. Data Structures & Algorithms in Python, página 251, exercício C-6.19)

No Fragmento de Código 6.5, assumimos que as tags de abertura em HTML têm a forma <nome>, assim como <li>. De maneira mais geral, HTML permite que atributos opcionais sejam expressos como parte de uma opening tag. A forma geral utilizada é <name attribute1 = "value1" attribute2 = "value2">; por exemplo, uma tabela pode receber uma borda e preenchimento adicional adotando a seguinte opening tag: . Modifique o Fragmento de Código 6.5 para que ele possa corresponder adequadamente às tags, mesmo quando uma opening tag pode incluir mais que um desses atributos.

Compartilhe

1 Resposta

+1 voto
respondida Out 27, 2020 por Andrei Leite (21 pontos)  
editado Dez 17, 2020 por Andrei Leite

O objetivo da questão é generalizar o código 6.5 escrito pelo autor que tem como objetivo verificar se os delimitadores utilizados em linguagens como HTML estão sendo utilizados corretamente.

Uma página HTML é construída usando tags, que é um comando em uma página da web que diz ao navegador para fazer algo. As tags são iniciadas pelo sinal < e finalizadas com o sinal >. Para entendermos melhor, analizemos um exemplo de um programa em HTML:

<!DOCTYPE HTML>
<html lang="en">
  <head>
    <title>My First Web Page</title>
  </head>
  <body>
    Hello World!
  </body>
</html>

Perceba que, nesse caso, <head> marca o início de uma parte do documento HTML. Por sua vez, </head> marca o fim dessa parte do documento. Portanto, tudo está escrito entre esses dois marcadores pertence a essa parte do documento.

O que se pede na questão é que o código seja generalizado para que sirva também para códigos como: <html lang="en">, que além da tag html tem também uma especificação: lang="en". Perceba que entre html e lang existe um espaço. Isso será utilizado na resolução do problema.

Começamos a resolução do problema definindo uma pilha, que é uma coleção de objetos que são inseridos e removidos de acordo com o princípio último a entrar, primeiro a sair (Last In First Out - LIFO).

class Pilha:

    def __init__(self):
        'Create an empty stack'
        self.lista=[]

    def __len__(self):
        return len(self.lista)

    def is_empty(self):
        return len(self.lista)==0

    def push(self,x):
        self.lista.append(x)

    def top(self):
        if self.is_empty():
           raise Empty('A pilha está vazia')
        else:
            return self.lista[-1]

    def pop(self):
        if self.is_empty():
            raise Empty('A pilha está vazia')
        else:
            return self.lista.pop()

Agora, iremos definir a função que irá verificar se as tags estão corretamente escritas, denominada pelo autor is_matched_html:

def is_matched_html(raw):
    pilha = Pilha()
    n = raw.find('<')          #Identifica se existe algum < no texto e retorna somente a posição do primeiro < que for identificado.
    if n==-1:
        return False
    else:
        while n!=-1:                # -1 é o valor que find() retorna se não encontrar < no texto. Então o loop irá continuar enquanto houver < no texto
            x = raw.find('>',n+1)   #Procura se há no texto algum > após a posição j. Inicia a busca em j+1 e vai até o final do texto' 
            if x==-1:               
                return False         #Significa que não tem > no texto, de forma que existe um < que não foi devidamente fechado com >
            b=raw.find(' ',n+1)     # Busca a string espaço após <. Se houver, retornará a posição. Caso contrário, retorna -1
            if b>=0 and b<x:    #Condicional: buscamos um espaço antes de <. Se houver, tag será a palavra até o espaço
                tag=raw[n+1:b]
            else:
                tag=raw[n+1:x]       # Caso a opção anterior não seja verdadeira, é porque não tem opções na tag e ela será todo o texto entre <>
            if not tag.startswith('/'):       # Se for verdadeiro é porque esta é uma opening tag, uma vez que não inicia com /
                pilha.push(tag)
            else:                       # O programa chegará nesse ponto se houver uma tag e ela iniciar com /
                if pilha.is_empty():      
                    return False        # Caso a pilha esteja vazia, não havera uma opening tag para dar match com a closing tag encontrada
                if tag[1:]!=pilha.pop():  #Compara a tag que inicia com / com o primeiro item da pilha. Se forem diferentes, é porque são tags diferentes e o match está errado
                    return False
            n=raw.find('<',x+1)         #Se chegar neste ponto, é por que encontrou uma opening e closing tag escritas de forma correta. O programa irá atualizar o valor de n e reiniciar o loop à procura de mais caracteres '<' no texto
        size = {"<":0,">":0}
        for letter in raw:
            if letter=="<":
                size["<"]+=1
            elif letter==">":
                size[">"]+=1
        if size["<"]!=size[">"]:
            return False
    return pilha.is_empty()

Testando se a função está correta.

 if __name__ == '__main__':

    raw1='teste'
    is_matched_html(raw1)        

    raw2='<teste'
    is_matched_html(raw2)        

    raw3='<teste>'
    is_matched_html(raw3)        

    raw4='<a></a>b>'
    is_matched_html(raw4)        

    raw5='''
    <html lang="en">
        <head>
            <title>My First Web Page</title>
        </head>
        <body>
            Hello World!
        </body>
    </html>
        '''
    is_matched_html(raw5)        

O output quando rodamos os testes acima é False para raw1 a raw4, como queríamos, e True para raw5, que é a forma correta.

comentou Dez 17, 2020 por leonardocarvalho (21 pontos)  
Boa noite, Andrei

Testei com alguns inputs diferentes para encontrar algum tipo de erro no código, colocando tags como:
1. <a><<</a>
2. <a></b>
3. <head><head>
4. <li><li>>>
5. <a><//a>

Que não seriam válidas no formato HMTL e elas funcionaram de forma correta, retornando o valor False. Porém, quando testado com uma string sem o "<" no início, o algoritmo retorna o valor True, como por exemplo em palavras "teste", "teste>", "teste/>" ou até uma string vazia, "". Como não são tags no formato correto do HTML ele deveria ter retornado False.
Para resolver esse problema, é possível colocar um condicional antes da estrutura while.

    if n == -1:
        return False

Se o método find retornar -1, quer dizer que não há nenhuma tag no formato correto dentro do argumento raw.
Outro problema também referente à tags sem "<" no início, é que, colocando algo como "<a></a>b>" ele retorna verdadeiro, porém, a "tag" b não está no formato correto. Para resolver isso, é possível contar o número de "<" e ">". Caso sejam diferentes, o conteúdo do HTML é inválido e retorna False. Utilizando um loop depois da estrutura while ter terminado, o algoritmo poderá contar o número de "<" e ">":

    size = {"<": 0, ">": 0}
    for letter in raw:
        if letter == "<":
            size["<"] += 1
        elif letter == ">":
            size[">"] += 1
    if size["<"] != size[">"]:
        return False

Achei interessante a implementação usando uma pilha para identificar se o formato do HTML está correto. Uma outra implementação possível é utilizando regex (https://docs.python.org/3/library/re.html ), literalmente "expressões regulares", que permitiriam achar o formato do HTML mais facilmente.
comentou Dez 17, 2020 por Andrei Leite (21 pontos)  
Olá Leonardo.

Muito obrigado por sua contribuição! De fato eu acabei não testando casos como os que você testou, por exemplo um texto normal como "teste".
Inseri no código sua sugestão para resolver esse problema.
Muito boa também sua sugestão para utilizar uma estrutura de dicionário para contar a quantidade de caracteres'<' e '>' no texto e retornar falso caso as quantidades não sejam iguais. Inseri também no código, assim como os testes que você fez e tinha retornado erro.
Abraço.
...