Neste guia, você aprenderá como verificar a validade de parênteses em Python.
A verificação de sequências de parênteses para determinar se a combinação é válida é um problema comum em entrevistas de programação. Nos próximos minutos, você descobrirá a técnica para resolver este problema e implementará uma função Python para validar uma string específica.
Qual é o Desafio dos Parênteses Válidos?
Vamos iniciar nossa análise respondendo: o que é exatamente o problema dos parênteses válidos?
Dada uma string composta por parênteses, chaves e colchetes: () [] {}, seu objetivo é verificar se a combinação de parênteses fornecida é válida.
Para ser considerada válida, uma string de parênteses deve atender a dois requisitos:
- Cada símbolo de abertura deve ter um símbolo de fechamento correspondente do mesmo tipo.
- Os símbolos devem ser fechados na ordem correta.
A seguir, alguns exemplos de strings de parênteses válidas e inválidas:
test_str = "{}]" --> INVÁLIDO, ] não foi aberto
test_str = "[{}]" --> VÁLIDO
test_str = "[]" --> VÁLIDO
test_str = "[]{}" --> VÁLIDO
test_str = "[{]}" --> INVÁLIDO, parênteses fechados incorretamente!
Na nossa abordagem de solução de problemas, a estrutura de dados que desempenhará um papel fundamental é a pilha. Vamos revisar os fundamentos de uma pilha na próxima seção.
Revisão da Estrutura de Dados Pilha
Uma pilha é uma estrutura de dados do tipo LIFO (último a entrar, primeiro a sair). Nela, elementos são adicionados e removidos do topo.
Ao adicionar um elemento ao topo da pilha, executamos uma operação de “push”. Ao remover um elemento do topo, executamos uma operação de “pop”.
Utilizaremos as seguintes regras para criar um conjunto de operações que podemos aplicar à string de parênteses.
- Coloque todos os parênteses de abertura na pilha.
- Se você encontrar um parêntese de fechamento, retire o elemento do topo da pilha.
Vamos agora avançar para a resolução do problema da verificação de parênteses válidos.
Como Verificar se Parênteses são Válidos
Combinando todas as observações dos exemplos anteriores, temos o seguinte:
Verifique o Tamanho da String de Parênteses: Se For Ímpar, a String é Inválida
Como cada parêntese de abertura precisa ter um parêntese de fechamento correspondente, uma string válida deve conter um número par de caracteres. Se o tamanho da string for ímpar, você pode concluir imediatamente que há uma combinação inválida de parênteses.
# len(test_str) = 3 (ímpar); ] não tem um [ de abertura
test_str = "{}]"
# len(test_str) = 3 (ímpar); ( não tem um ) de fechamento
test_str = "[(]"
# len(test_str) = 5 (ímpar); existe um ) extra
test_str = "{())}"
A seguir, vamos analisar como resolver quando o número de caracteres na string é par.
O Tamanho da String de Parênteses é Par: O Que Vem a Seguir?
Passo 1: Percorra a string da esquerda para a direita. Vamos chamar a string de `test_str` e os caracteres individuais de `char`.
Passo 2: Se o primeiro caractere (`char`) for um parêntese de abertura (, {, ou [, adicione-o ao topo da pilha e avance para o próximo caractere na string.
Passo 3: Agora, verifique se o próximo caractere (`char`) é um parêntese de abertura ou fechamento.
Passo 3.1: Se for um parêntese de abertura, adicione-o também ao topo da pilha.
Passo 3.2: Se você encontrar um parêntese de fechamento, retire o elemento do topo da pilha e siga para o passo 4.
Passo 4: Aqui, há três possibilidades baseadas no valor retirado da pilha:
Passo 4.1: Se for um parêntese de abertura do mesmo tipo, volte ao passo 3.
Passo 4.2: Se for um parêntese de abertura de um tipo diferente, você pode concluir que não se trata de uma string de parênteses válida.
Passo 4.3: A última possibilidade é a pilha estar vazia. Novamente, este é o caso de uma string inválida, pois você encontrou um parêntese de fechamento que não tem um parêntese de abertura correspondente.
Exemplos Práticos de Strings de Parênteses Válidos
Agora, vamos analisar três exemplos e percorrer os passos descritos acima.
📑 Se você já entendeu como funciona, fique à vontade para pular para a próxima seção.
#1. Como primeiro exemplo, vamos usar `test_str = “{()”`.
- { é o primeiro caractere e é um parêntese de abertura, então você o adiciona à pilha.
- O próximo caractere ( também é um parêntese de abertura, então adicione-o também à pilha.
- O terceiro caractere da string ) é um parêntese de fechamento, então você deve retirar o elemento do topo da pilha, que retorna (.
- Neste ponto, você chegou ao final da string. Mas a pilha ainda contém o { de abertura, que nunca foi fechado. Portanto, a string de parênteses `test_str` é inválida.
#2. Neste segundo exemplo, vamos usar `test_str = “()]”`
- O primeiro caractere ( é um parêntese de abertura; adicione-o à pilha.
- O segundo caractere ) é um parêntese de fechamento; retire o elemento do topo da pilha, que por coincidência é ( – um parêntese de abertura do mesmo tipo. Prossiga para o próximo caractere.
- O terceiro caractere ] é um parêntese de fechamento e você deve retirar o elemento do topo da pilha novamente. No entanto, como você pode ver, a pilha está vazia – o que significa que não há parênteses de abertura [ correspondentes. Portanto, esta string é inválida.
#3. Neste exemplo final, `test_str = “{()}”`.
- Os dois primeiros caracteres {( são parênteses de abertura, então adicione-os à pilha.
- O terceiro caractere é ), então retire o elemento do topo da pilha – (.
- O próximo caractere } é uma chave de fechamento, e ao retirar o elemento do topo da pilha, você obtém { – uma chave de abertura.
- Depois de percorrer toda a string, a pilha está vazia e `test_str` é válida! ✅
📌 Montei o seguinte fluxograma que descreve os passos do problema de verificação de parênteses válidos. Você pode salvá-lo para referência rápida!
Na próxima seção, vamos ver como traduzir nosso conceito para código Python.
Programa Python para Verificar Parênteses Válidos
Em Python, você pode usar a lista para simular uma pilha.
Você pode usar o método `.append()` para adicionar elementos ao final da lista. Isso é similar a adicionar ao topo da pilha.
O método `.pop()` retorna o último elemento da lista, o que é similar a retirar do topo da pilha – para remover o elemento adicionado mais recentemente.
Então, agora você sabe como implementar as operações de push e pop em uma lista Python, simulando a pilha.
Como próximo passo, vamos responder a pergunta: como diferenciar entre parênteses de abertura e fechamento?
Bem, você pode usar um dicionário Python – com os parênteses de abertura ‘{‘, ‘[‘, ‘(‘ como chaves do dicionário e os parênteses de fechamento correspondentes ‘}’, ‘]’, ‘)’ como valores. Você pode usar o método `.keys()` para acessar as chaves individuais do dicionário.
Vamos usar tudo o que aprendemos para escrever a definição da função `is_valid()`.
Compreendendo a Definição da Função
Leia o seguinte bloco de código que contém a definição da função. Você verá que usamos os passos do fluxograma junto com a explicação acima.
Além disso, adicionamos uma docstring contendo:
- uma breve descrição da função
- os argumentos da chamada da função
- os valores retornados pela função
▶ Você pode usar `help(is_valid)` ou `is_valid.__doc__` para recuperar a docstring.
def isValid(test_str):
'''Verifica se uma string de parênteses fornecida é válida.
Args:
test_str (str): A string de parênteses a ser validada
Returns:
True se test_str for válida; caso contrário, False
'''
# len(test_str) é ímpar -> inválida!
if len(test_str)%2 != 0:
return False
# inicializa o dicionário de parênteses
par_dict = {'(':')','{':'}','[':']'}
stack = []
for char in test_str:
# adiciona o parêntese de abertura à pilha
if char in par_dict.keys():
stack.append(char)
else:
# parêntese de fechamento sem parêntese de abertura correspondente
if stack == []:
return False
# se for parêntese de fechamento -> retira o elemento do topo da pilha
open_brac = stack.pop()
# parênteses não correspondentes -> inválido!
if char != par_dict[open_brac]:
return False
return stack == []
A função Python `is_valid` verifica se a string de parênteses é válida e funciona da seguinte maneira:
- A função `is_valid` recebe um parâmetro, `test_str`, que é a string de parênteses a ser validada. Ela retorna `True` ou `False`, dependendo se a string `test_str` é válida ou não.
- Aqui, `stack` é a lista Python que simula a pilha.
- E `par_dict` é o dicionário Python, com parênteses de abertura como as chaves e parênteses de fechamento como os valores correspondentes.
- Ao percorrer a string, se encontrarmos alguma condição que torne a string de parênteses inválida, a função retornará `False` e sairá.
- Depois de percorrer todos os caracteres da string, `stack == []` verifica se a pilha está vazia. Se sim, `test_str` é válida e a função retorna `True`. Caso contrário, a função retorna `False`.
Agora, vamos fazer algumas chamadas de função para verificar se a nossa função opera corretamente.
str1 = '{}[]'
isValid(str1)
# Output: True
str2 = '{((}'
isValid(str2)
# Output: False
str3 = '[{()}]'
isValid(str3)
# Output: True
str4 = '[{)}]'
isValid(str4)
# Output: False
str5 = '[[]}'
isValid(str5)
# Output: False
A partir do trecho de código acima, podemos concluir que a função opera conforme esperado!
Conclusão 🧑💻
Aqui está um resumo rápido do que você aprendeu:
- Primeiramente, você foi introduzido ao problema da verificação de parênteses válidos.
- Em seguida, você aprendeu uma abordagem para resolver o problema usando a pilha como a estrutura de dados escolhida.
- Depois, você aprendeu como validar uma combinação de parênteses usando um dicionário Python: com parênteses de abertura como as chaves e os parênteses de fechamento correspondentes como valores.
- Finalmente, você definiu a função Python para verificar se uma string de parênteses fornecida é válida.
Como próximo passo, tente codificar o problema no editor Python online do etechpt.com. Sinta-se à vontade para revisitar este guia se precisar de ajuda!
Confira mais tutoriais de Python. Boa programação! 🎉