Neste tutorial, você aprenderá a verificar parênteses válidos em Python.
Dada uma sequência de parênteses, verificar se a combinação de parênteses é válida é uma pergunta popular de entrevista de codificação. E nos próximos minutos, você aprenderá a técnica para resolver essa questão e também codificará uma função Python para validar uma determinada string.
últimas postagens
O que é o problema dos parênteses válidos?
Vamos começar nossa discussão respondendo à pergunta: qual é o problema dos parênteses válidos?
Dada uma string contendo os caracteres parênteses simples, chaves e colchetes: () [] {}, você deve verificar se a combinação de parênteses fornecida é válida.
Uma string de parênteses válida satisfaz as duas condições a seguir:
Aqui estão alguns exemplos de strings de parênteses válidas e inválidas.
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
Em nossa abordagem de solução de problemas, a pilha é a estrutura de dados que desempenhará um papel fundamental. Vamos revisar o básico de uma pilha na próxima seção.
A estrutura de dados da pilha revisitada
A pilha é uma estrutura de dados LIFO (last in first out), onde você pode adicionar elementos ao topo da pilha e também removê-los do topo da pilha.
Quando você adiciona um elemento ao topo da pilha, você executa uma operação push, quando você remove um elemento do topo da pilha, você executa uma operação pop.
Usaremos as duas regras a seguir para criar um conjunto de operações que podemos realizar na string de parênteses.
- Empurre todos os suportes de abertura para a pilha.
- Se você encontrar um colchete de fechamento, retire o topo da pilha.
Vamos prosseguir para resolver o problema de verificação de parênteses válidos.
Como verificar se há parênteses válidos
Juntando todas as observações dos exemplos acima, temos o seguinte.
Verifique o comprimento da string de parênteses: Se ímpar, a string é inválida
Como todo colchete de abertura deve ter um colchete de fechamento, uma string válida deve conter um número par de caracteres. Se o comprimento da string for ímpar, você pode concluir imediatamente que há uma combinação inválida de parênteses.
# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"
# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"
# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"
Em seguida, vamos ver como podemos resolver quando o número de caracteres na string é par
O comprimento da string de parênteses é par: o que vem depois?
Passo 1: Atravesse a corda da esquerda para a direita. Vamos chamar a string test_str e os caracteres individuais na string char.
Etapa 2: se o primeiro caractere de caractere for um colchete de abertura (, {, ou [, push it to the top of the stack and proceed to the next character in the string.
Step 3: Now, check if the next character (char) is an opening or a closing bracket.
Step 3.1: If it’s an opening bracket, push it again onto the stack.
Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.
Step 4: Here again, there are 3 possibilities based on the value popped off the stack:
Step 4.1: If is an opening bracket of the same type, loop back to step 3.
Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.
Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.
Valid Parentheses String Examples Walkthrough
Now let’s take three examples and walk through the above steps.
📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.
#1. As a first example, let test_str = “{()”.
- { is the first character, and it’s an opening bracket, so you push it to the stack.
- The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
- The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
- At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.
#2. In this second example, let test_str = “()]”
- O primeiro caractere ( é um colchete de abertura; empurre-o para a pilha.
- O segundo caractere ) é um colchete de fechamento; pop off the stack top, que por acaso é ) – um colchete de abertura do mesmo tipo. Prossiga para o próximo caractere.
- O terceiro caractere ]é um colchete de fechamento e você deve sair do topo da pilha novamente. No entanto, como você pode ver, a pilha está vazia – o que significa que não há colchetes de abertura correspondentes [. Hence, this string is invalid.
#3. In this final example, test_str = “{()}”.
- The first two characters {( are opening brackets, so push them onto the stack.
- The third character is a closing ), so pop off the stack top – (.
- The next character } is a closing curly brace, and when you pop the stack top, you get { – an opening curly brace.
- After you have traversed the entire string, the stack is empty and test_str is valid! ✅
📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!
In the next section, let’s see how to translate our concept to Python code.
Python Program to Check for Valid Parentheses
In Python, you can use the list to emulate a stack.
You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.
The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.
So you now know how to implement the push and pop operations on a Python list, emulating the stack.
As a next step, let’s answer the question: how to differentiate between opening and closing brackets?
Well, you can use a Python dictionary – with the opening brackets ‘{‘, ‘[‘, ‘(‘ as the keys of the dictionary and the corresponding closing brackets ‘}’, ‘]’, ‘)’ como os valores. Você pode usar o método .keys() para acessar chaves individuais no dicionário.
Vamos usar tudo o que aprendemos para escrever a definição da função is_valid().
Entendendo a definição da função
Leia a seguinte célula de código que contém a definição da função. Você pode ver que usamos as etapas do fluxograma em conjunto com a explicação acima.
Além disso, também adicionamos um docstring Incluindo:
- uma breve descrição da função
- os argumentos na chamada da função
- os valores de retorno da função
▶ Você pode usar help(is_valid) ou is_valid.__doc__ para recuperar a docstring.
def isValid(test_str):
'''Check if a given parentheses string is valid.
Args:
test_str (str): The parentheses string to be validated
Returns:
True if test_str is valid; else False
'''
# len(test_str) is odd -> invalid!
if len(test_str)%2 != 0:
return False
# initialize parentheses dict
par_dict = {'(':')','{':'}','[':']'}
stack = []
for char in test_str:
# push opening bracket to stack
if char in par_dict.keys():
stack.append(char)
else:
# closing bracket without matching opening bracket
if stack == []:
return False
# if closing bracket -> pop stack top
open_brac = stack.pop()
# not matching bracket -> invalid!
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. Ele retorna True ou False dependendo se a string test_str é válida ou não.
- Aqui, pilha é a lista Python que emula a pilha.
- E par_dict é o dicionário Python, com colchetes de abertura como as chaves e colchetes 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 na string, stack == [] verifica se a pilha está vazia. Se sim, test_str é válido e a função retorna True. Caso contrário, a função retorna False.
Agora, vamos em frente e fazer algumas chamadas de função para verificar se nossa função funciona 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 funciona conforme o esperado!
Conclusão 🧑💻
Aqui está um resumo rápido do que você aprendeu.
- Em primeiro lugar, você foi apresentado 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.
- Em seguida, você aprendeu como validar uma combinação de parênteses usando um dicionário Python: com colchetes de abertura, as chaves e os colchetes de fechamento correspondentes como valores.
- Finalmente, você definiu a função Python para verificar se uma determinada string de parênteses é 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 codificação!🎉