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:
- Cada símbolo de abertura
(
ou[
tem um símbolo de fechamento correspondente)
ou]
. - 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:
- Percorrer cada caractere na sequência.
- Se o caractere for um símbolo de abertura (
(
ou[
), colocá-lo na pilha. - 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.
- Verificar se a pilha está vazia. Se estiver, significa que não há um símbolo de abertura correspondente, então retornamos
- 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, retornamosFalse
.
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.