Escreva uma função em Python que receba uma sequencia de parênteses e colchetes e retorne True se ela está bem formada ou False, caso contrario.

Passo 1

Beleza, vamos lá! O exercício pede para a gente escrever uma função em Python que recebe uma sequência de parênteses e colchetes e retorna True se essa sequência está bem formada, ou seja, se todos os parênteses e colchetes estão corretamente abertos e fechados. Se não estiverem, a função deve retornar False.
Para resolver isso, vamos precisar entender:
  • Estruturas de Dados Básicas: Vamos usar uma pilha (stack) para acompanhar os símbolos abertos e fechados.
  • Lógica de Comparação: Precisamos verificar se cada par de símbolos está corretamente pareado.

Passo 2

Primeiro, vamos entender o que significa uma sequência de parênteses e colchetes estar bem formada. Isso quer dizer que:
  1. Cada símbolo de abertura ( ou [ tem um símbolo de fechamento correspondente ) ou ].
  2. Os símbolos fechados fecham os abertos na ordem correta, ou seja, o último símbolo aberto deve ser o primeiro a ser fechado.
Por exemplo:
  • "()" está bem formada.
  • "[()]" está bem formada.
  • "([)]" não está bem formada porque o [ foi aberto primeiro, mas o ) fechou antes do ].

Passo 3

Vamos usar uma pilha para resolver esse problema. A pilha é uma estrutura de dados que funciona no modo LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser removido. Isso é perfeito para acompanhar os símbolos que foram abertos e precisam ser fechados na ordem correta.
Aqui está o passo a passo de como vamos usar a pilha:
  1. Percorrer cada caractere na sequência.
  2. Se o caractere for um símbolo de abertura (( ou [), colocá-lo na pilha.
  3. Se for um símbolo de fechamento () ou ]):
    • Verificar se a pilha está vazia. Se estiver, significa que não há um símbolo de abertura correspondente, então retornamos False.
    • Se a pilha não estiver vazia, removemos o último símbolo aberto da pilha e verificamos se ele corresponde ao símbolo de fechamento atual.
  4. Depois de percorrer toda a sequência, se a pilha estiver vazia, significa que todos os símbolos foram fechados corretamente, então retornamos True. Caso contrário, retornamos False.

Passo 4

Vamos implementar isso em Python. Primeiro, precisamos definir nossa função e inicializar uma pilha. Em Python, podemos usar uma lista para simular uma pilha:
def esta_bem_formada(sequencia):
    pilha = []
    # Dicionário para mapear símbolos de fechamento aos de abertura
    correspondencias = {')': '(', ']': '['}
    
    for char in sequencia:
        if char in correspondencias.values():  # Se for um símbolo de abertura
            pilha.append(char)
        elif char in correspondencias:  # Se for um símbolo de fechamento
            if not pilha:
                return False
            topo = pilha.pop()
            if correspondencias[char] != topo:
                return False
        else:
            # Ignora outros caracteres que não sejam parênteses ou colchetes
            continue
    
    return not pilha  # Retorna True se a pilha estiver vazia

Passo 5

Vamos testar a função para ver se funciona corretamente:
print(esta_bem_formada("()"))        # Deve retornar True
print(esta_bem_formada("(()))"))     # Deve retornar False
print(esta_bem_formada("[()]"))      # Deve retornar True
print(esta_bem_formada("([)]"))      # Deve retornar False
print(esta_bem_formada("{[()]}"))    # Ignora chaves e retorna True

Resposta

A função acima verifica se uma sequência de parênteses e colchetes está bem formada. Ela retorna True para sequências bem formadas e False caso contrário.

Exercícios relacionados