🏴 English version of this text here!
Eu comecei a estudar a linguagem Elixir e decidi resolver alguns exercícios de programação pra conseguir entender melhor alguns conceitos.
Como eu acabei gostando da minha solução, decidi fazer esse post explicando o pensamento por trás dela. Sugestões pra melhorar ainda mais o código ou pra melhor seguir os padrões e convenções do Elixir são mais do que bem-vindos! (:
O Problema
Quero fazer uma função que recebe uma string de entrada, supostamente uma expressão matemática ou um trecho de código, e que me diga se todos os seus abre parênteses/colcehetes/chaves são corretamente fechados.
Algumas expressões de exemplo:
1 * 2 (3 + [4 / 5])
# deveria retornar true
9 / [(8 + 7] - 6)
# deveria retornar false
Faça um plano
Antes de começar a escrever código, eu acho que é uma boa ideia resolver o problema de maneira teórica, para aí sim tentar implementá-lo.
Pra esse exercício, eu acredito que usar o conceito de pilha seja uma boa ideia.
Basicamente, uma pilha é um conjunto de itens que tem duas operações: push e pop.
- O push vai colocar um novo item no conjunto
- O pop vai remover o último item adicionado
Ou seja, a pilha segue o princípio do "Last In, First Out" (LIFO), ou seja, "o último a entrar será o primeiro a sair".
Mas como podemos usar uma pilha aqui? Bom, minha solução teórica seria de iterar sobre todos os caracteres na string de entrada e:
- Se for uma "abertura" (
(
,[
ou{
), colocamos na pilha - Se for um "fechamento" (
)
,]
ou}
), temos que verificar o último item adicionado na pilha. Se forem correspondentes ((
com)
, por exemplo), nós removemos ele da pilha (pop) e seguimos a iteração. Do contrário, a string de entrada era inválida - Se for outra coisa, ignoramos
Se iterarmos sobre a expressão inteira e nunca acharmos um erro, isso significa que todos os fechamentos tiveram uma abertura apropriada, mas isso não significa necessariamente que a string era válida. Veja esse exemplo:
1 + (2 * [3]
Aqui, todos os fechamentos tiveram uma abertura correta, mas nem todas as aberturas foram fechadas.
Isso significa que, caso sobrevivamos à iteração, temos que verificar também se no final a nossa pilha está vazia. Se sim, então todas as aberturas foram corretamente fechadas. Se não, o valor de entrada era inválido.
A Implementação
Boa, temos um plano. Agora, temos que traduzir isso para Elixir.
Pra começar, vou criar um módulo chamado Parens
com a função check
, que vai receber uma string.
Essa função check
terá que iterar sobre todos os caracteres desse valor de entrada, então podemos separar essa string usando a função split/2
, do módulo String
. Nosso primeiro trecho de código então é algo assim:
defmodule Parens do
def check(expression) do
expression
|> String.split("")
end
end
Usei aqui o operador pipe |>
. O que ele faz é que ele usa o que vem antes como o primeiro argumento do que vier depois. Nesse caso, expression
será o primeiro argumento para String.split
.
O segundo argumento nesse caso é uma string vazia, o que significa que vamos separar expression
em todos os caracteres.
O resultado final será uma lista, tipo assim:
"a + b * (c / d)" |> String.split("")
# ["", "a", " ", "+", " ", "b", " ", "*", " ", "(", "c", " ", "/", " ", "d", ")", ""]
Na nossa solução teórica, todos os caracteres diferentes de aberturas/fechamentos deveriam ser ignorados. Podemos removê-los da nossa lista agora usando um filter (filtro). Pra fazer isso, podemos chamar Enum.filter/2
, que recebe dois argumentos.
O primeiro deve ser algo "enumerável", que significa que deve ser algo que implementa o "protocolo" Enum.
Felizmente, listas fazem isso, então podemos usar nosso resultado como primeiro argumento do filtro.
O segundo argumento é uma função que recebe um elemento da nossa lista e decide se ele deveria ou não estar no resultado filtrado. Mais especificamente, essa função vai retornar um valor, e se ele for falsy (false
ou nil
), o filtro vai remover esse item do resultado final. Do contrário, ele vai estar na lista resultante.
No nosso caso, essa função vai ter que verificar cada elemento e dizer se ele é ou uma abertura ou um fechamento, que são os únicos caracteres que nos importam. Uma maneira de se fazer isso é assim:
fn x -> x in ["{", "[", "(", "}", "]", ")"] end
Essa função anônima vai receber algo (x) e ver se essa coisa pertence ou não àquela lista especificada, que contém somente os caracteres importantes (aberturas e fechamentos).
Também poderíamos usar a notação de captura, assim:
&(&1 in ["{", "[", "(", "}", "]", ")"])
Essa notação é parecida, mas ao invés de declarar o x, a gente usa &1, &2, &3... para todos os argumentos que podem chegar.
Beleza, então nosso código até aqui está assim:
defmodule Parens do
def check(expression) do
expression
|> String.split("")
|> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
end
end
O próximo passo é iterar sobre nossa listra resultante (depois do filtro) e usar a nossa estratégia da pilha.
Pra fazer isso, decidi criar uma função privada chamada iterate
, onde vou recursivamente andar sobre nossos elementos, levando a pilha de um lado para o outro, até termos verificado todos os nossos elementos.
Já que eu vou precisar da pilha, essa função terá uma aridade de 2, ou seja, ela terá 2 argumentos.
A primeira coisa que eu faço quando estou pensando sobre recursão é de escrever a condição de parada. Nesse caso, a função deveria parar assim que a nossa lista de caracteres estiver vazia.
Vou usar a funcionalidade maravilhosa de pattern matching aqui pra fazer isso:
defp iterate([], stack), do: stack
Isso significa que essa função só vai ser executada quando o primeiro elemento for uma lista vazia, e o segundo elemento pode ser qualquer coisa aqui (que será colocado numa variável chamada stack
, que significa pilha em inglês).
Nesse caso, a função não está fazendo nada, apenas retornando a pilha. Mais tarde podemos verificar se ela está vazia ou não.
Um ponto muito importante pra perceber aqui é que também temos que passar a pilha quando chamamdos a função iterate
pela primeira vez. Nossa pilha começa vazia, então nossa pipeline ficou assim:
def check(expression) do
expression
|> String.split("")
|> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
|> iterate([])
end
Obs: Também podemos usar um valor padrão aqui, mas deixarei assim.
Agora, a parte difícil. Depois de escrever a condição de parada da nossa recursão, temos que escrever o passo recursivo (ou passos).
Vamos relembrar nosso plano outra vez. Temos que olhar pra cada elemento, e se for uma abertura, colocamos na pilha e seguimos em frente. Vamos fazer essa parte primeiro.
Eu amo pattern matching, então vou estar usando aqui de novo. E pra ajudar-nos ainda mais, também usarei algumas guardas (ou guard, em inglês), pra decidir se a função será executada ou não:
defp iterate([head | tail], stack) when head in ["{", "[", "("] do
end
Essa função somente será executada se a variável head
estiver naquela lista de aberturas. Mas de onde essa variável está vindo?
Estamos fazendo o pattern matching do primeiro argumento com [head | tail]
, então essa função vai precisar que o primeiro argumento seja uma lista que tenha um primeiro elemento. Esse elemento então vai ser vinculado/ligado (bind) a head
. O resto da lista será vinculado a tail
. Sempre que estiver em dúvida, podemos abrir o shell interativo do Elixir e fazer alguns testes.
Escreva iex
no terminal e aperte enter, e tente alguns códigos como esses:
[head | tail] = [1,2,3,4]
head
#=> 1
tail
#=> [2,3,4]
[head2 | tail2] = [0]
head2
#=> 0
tail2
#=> []
[head3 | tail3] = []
# Vai levantar um "matching error"!
Os conceitos de "cabeça" e "cauda" de uma lista são bastante importantes (head e tail, respectivamente). O primeiro elemento de uma lista é sua cabeça, e a cauda será o resto da lista. Perceba que a cauda é também uma lista!
Okay, de volta pra nossa função. O que ela deveria fazer se o elemento sendo verificado for uma abertura?
Ela deveria colocar na pilha (push) e seguir iterando. Podemos fazer isso simplesmente chamando iterate
com os argumentos certos.
Como já verificamos o primeiro elemento, temos que passar a lista sem o primeiro elemento, certo? E isso é exatamente o que tail
é! Ótimo, mas como podemos adicionar (fazer o push) esse elemento na pilha?
O Elixir oferece uma maneira muito fácil de colocar um item no começo de uma lista, e é simplesmente assim:
[elemento_novo | pilha]
Isso é uma lista cuja cabeça é elemento_novo
, e a cauda é pilha
. Sempre podemos ir no iex e fazer alguns experimentos:
[1 | 9,8,7]
#=> [1,9,8,7]
Então, nossa função pode ficar meio assim:
defp iterate([head | tail], stack) when head in ["{", "[", "("],
do: iterate(tail, [head | stack])
Quando head
for uma abertura, a gente chama iterate
passando tail
como primeiro argumento e a pilha com um novo elemento adicionado como segundo elemento.
Legal! Agora que temos essa parte feita, vamos recapitular:
Já sabemos parar a recursão;
Já lidamos com os casos dos caracteres que não são nem aberturas, nem fechamentos;
Já sabemos adicionar um item na pilha e seguir adiante;
Agora temos que fazer alguma coisa quando o elemento é um fechamento. Quando isso acontece, a ideia era olhar o último item adicionado na nossa pilha, que por construção, vem a ser exatamente a cabeça da nossa pilha!
A próxima parte do código foi fortemente refatorada, mas eu vou mostrar como eu fiz inicialmente.
Pra cada fechamento possível, eu fiz uma declaração específica, fazendo o pattern match na cabeça dos elementos que vão ser iterados, assim:
defp iterate(["}" | tail], stack)
defp iterate(["]" | tail], stack)
defp iterate([")" | tail], stack)
E daí pra cada uma delas, eu fiz um if/else simples:
defp iterate(["}" | tail], stack) do
if hd(stack) == "{" do
iterate(tail, tl(stack))
else
false
end
end
Primeiro de tudo, aqui eu usei as funções hd
e tl
, que retornam a cabeça e a cauda de uma lista, respectivamente. Seria a mesma coisa que escrever isso:
defp iterate(["}" | tail], [stack_head | stack_tail]) do
if stack_head == "{" do
iterate(tail, stack_tail)
else
false
end
end
Essa função, então, só vai executar se o primeiro elemento da lista for exatamente }
. Daí a gente verifica se o último elemento adicionado na pilha, sua cabeça (estamos adicionando as coisas "pela cabeça" na lista!) é {
, que seria a correspondência correta.
Se for, temos que fazer o pop desse elemento, era o nosso plano. Perceba que a versão "popada" da pilha é simplesmente sua cauda, então é por isso que não passamos a pilha pra próxima iteração, e sim sua cauda (representada por stack_tail
, veja o pattern matching nos argumentos da função).
Se não for a correspondência correta, a gente sabe que a string de entrada não era válida, então estou retornando false
aqui.
Note que a parte do else
não é realmente necessária, pois se não entrássemos na parte do if
, o valor retornado seria nil
, mas vou deixar assim por enquanto. Depois podemos refatorar (:
Isso parece uma boa "versão alpha" da nossa função iterate
. O que está faltando é verificar no final se a nossa pilha está vazia ou não após a condição de parada.
Poderíamos usar aqui Enum.empty?
, que receberia a pilha e verificaria se está vazia ou não (true
se estiver vazia, false
caso contrário).
Uma outra maneira de fazer isso seria adicionar uma comparação com []
ou na condição de parada, ou na pipeline da nossa função check
. Vou fazer a segunda opção primeiro pra poder falar rapidinho do módulo Kernel
.
O módulo Kernel
tem todas as funções "nativas", que podemos chamar sem escrever um módulo. Ou seja, se você quiser somar dois inteiros, podes fazer dos dois jeitos:
1+2
#=> 3
Kernel.+(1,2)
#=> 3
A comparação ==
também faz parte do módulo Kernel
, então podemos fazer assim:
def check(expression) do
expression
|> String.split("")
|> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
|> iterate([])
|> Kernel.==([])
end
Isso vai pegar o que quer que seja que tenha retornado de iterate
e passar como primeiro argumento de Kernel.==
. O segundo argumento é []
, então vamos retornar a comparação entre o resultado de iterate
com []
.
Se a entrada for uma expressão inválida, iterate
pode retornar false
, e daí a comparação com []
também será falsa.
Outra possibilidade é que iterate
vai retornar uma pilha não vazia, ou seja, uma lista com algum elemento. Neste caso, a comparação com []
também será falsa.
Isso até resolve o problema, mas pra mim é bastante feio.
Pra começo de conversa, às vezes iterate
retorna um booleano, mas às vezes retorna uma lista, seja vazia ou não.
Agora que eu já escrevi um pouquinho sobre o módulo Kernel
, acho que podemos não utilizá-lo aqui (:
Pra evitá-lo, podemos simplesmente colocar a comparação na nossa condição de parada:
defp iterate([], stack), do: stack == []
Outro jeito é de usar o pattern matching no segundo argumento, também!
defp iterate([], []), do: true
defp iterate([], _stack), do: false
Se o primeiro argumento for uma lista vazia e o segundo, também, retornamos true
.
Se o primeiro argumento for uma lista vazia e o segundo for qualquer coisa, retornamos false
.
O underline(_) em _stack
denota que que essa variável não será usada. Poderíamos escrever simplesmente _
, sem a palavra "stack" junto, mas acho que quando não é óbvio o que pode ser esse segundo parâmetro, é uma boa ideia dar um nome melhor para a variável, em nome da legibilidade.
Okay, então isso aparentemente funciona, certo?
Se tentarmos rodar nosso código agora, de vez em quanto tomaremos um erro!
Pra testá-lo, podemos usar nosso módulo dentro do iex. Pra fazer isso, salve o código em um arquivo, por exemplo, parens.ex
. Agora, execute iex parens.ex
. Conseguimos agora usar o módulo Parens
, que criamos, dentro do iex!
Se tentarmos verificar uma string onde um fechamento foi encontrado num momento em que não há nenhuma abertura na nossa pilha, estaríamos tentando pegar a cabeça de uma lista vazia, o que levanta um erro para nós. Podes verificar com esses exemplos:
Parens.check("a}")
#> Levanta um erro!
Parens.check("(a}")
#=> false
Podemos arrumar isso se verificarmos se a pilha está vazia antes de tentarmos pegar a cabeça.
Ou...
Poderíamos simplesmente declarar uma função fazendo pattern matching no segundo argumento para uma lista vazia quando o elemento a ser analisado é um fechamento, assim:
defp iterate([head | _], []) when head in ["}", "]", ")"], do: false
A guarda vai garantir que o elemento em questão é um fechamento, e quando a pilha está vazia, retornamos direto false
antes de tentar pegar a cabeça de uma lista vazia (que jogaria um erro em nós).
A primeira versão da nossa solução, portanto, poderia ser isso:
defmodule Parens do
def check(expression) do
expression
|> String.split("")
|> Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
|> iterate([])
end
defp iterate([], []), do: true
defp iterate([], _stack), do: false
defp iterate([head | tail], stack) when head in ["{", "[", "("],
do: iterate(tail, [head | stack])
defp iterate([head | _], []) when head in ["}", "]", ")"],
do: false
defp iterate(["}" | tail], stack) do
if hd(stack) == "{" do
iterate(tail, tl(stack))
else
false
end
end
defp iterate(["]" | tail], stack) do
if hd(stack) == "[" do
iterate(tail, tl(stack))
else
false
end
end
defp iterate([")" | tail], stack) do
if hd(stack) == "(" do
iterate(tail, tl(stack))
else
false
end
end
end
Show! Então agora nosso código realmente funciona!
Mas ele não me passa uma vibe muito boa...
Refatoração!
Primeiro, estamos usando listas como ["{", "[", "("]
, ["{", "[", "("]
e ["{", "[", "(", "}", "]", ")"]
algumas vezes, que poderiam ser extraídas para atributos de módulo.
Um atributo de módulo é um valor que pode ser usado por qualquer método dentro de um módulo. Pra definí-los, podemos escrever algo como @nome_do_atributo
logo em seguida o seu valor.
No nosso caso, podemos fazer algo assim:
defmodule Parens do
@opener ["{", "[", "("]
@closer ["}", "]", ")"]
end
Com essa pequena adição, podemos reescrever nossas guardas e nosso filtro, desta maneira:
Enum.filter(&(&1 in ["{", "[", "(", "}", "]", ")"]))
Enum.filter(&(&1 in @opener || &1 in @closer))
defp iterate([head | tail], stack) when head in ["{", "[", "("]
defp iterate([head | tail], stack) when head in @opener,
defp iterate([head | _], []) when head in ["}", "]", ")"], do: false
defp iterate([head | _], []) when head in @closer, do: false
Isso é legal, mas ainda temos 3 grandes funções que são basicamente a mesma coisa, que são as que decidem o que fazer quando o elemento checado é um fechamento.
Vou escrever aqui a maneira como podemos melhorá-las, usando apenas um outro atributo de módulo e uma única função, e vou explicar depois o que ela faz:
defmodule Parens do
@pairs %{"{" => "}", "[" => "]", "(" => ")"}
defp iterate([head | tail], [stack_head | stack_tail]) when head in @closer,
do: @pairs[stack_head] == head && iterate(tail, stack_tail)
end
Primeiro, eu criei o atributo @pairs
, que é um mapa. Cada chave desse mapa é um caracter de abertura que é mapeado para o seu caracter de fechamento correspondente (mapas são como hashes e dicionários, se você está vindo do Ruby ou Python).
Então, eu fiz uma outra definição para iterate/2
que tem uma guarda. Essa guarda vai nos assegurar que a variável head
(elemento a ser verificado) é um caracter de fechamento (então é ou )
, ou ]
, ou }
).
Eu também usei uma operação booleana &&
aqui:
@pairs[stack_head] == head && iterate(tail, stack_tail)
Se o lado esquerdo dessa operação for falsy, então este valor é retornado e o lado direito não é executado (o que para a nossa recursão).
Se o lado esquerdo for truthy, então seja lá o que for que está do lado direito é retornado. Nesse caso, o lado direito é uma chamada recursiva da nossa própria função iterate
, continuando o ciclo.
Agora olhemos para @pairs[stack_head]
. Lembra que @pairs
é um mapa? Ou seja, se tivéssemos, por exemplo, @pairs["{"]
, isso retornaria "}"
.
Se seja lá o que for que estiver na cabeça da nossa pilha for um caracter de abertura, então estamos mapeando-o para o seu respectivo fechador quando consultamos o valor de @pairs[stack_head]
. Se esse fechador for o mesmo que está na variável head
, então essa comparação retorna true
, que fará com que aquela operação booleana retorne o lado direito, isto é, a chamada recursiva da função, passando o resto da lista (tail
) e a versão "popada" da pilha (stack_tail
).
Se o que estiver na cabeça da pilha não for uma abertura, @pairs[stack_head]
vai retornar nil
, e nil == head
vai ser falso, logo, a recursão morre aí.
Também pode acontecer que o que está na cabeça da pilha é uma abertura, mas @pairs[stack_head]
não é igual a head
. Logo, a comparação vai ser falsa também. Esse é o caso em que estamos tentando fechar algo que ainda não foi aberto, e como deu falso naquela comparação, a recursão para por aí.
Portanto, isso basta para verificar se os caracteres correspondem e parar a recursão caso contrário.
Então, a nossa segunda versão do programa seria:
defmodule Parens do
@pairs %{"{" => "}", "[" => "]", "(" => ")"}
@opener ["{", "[", "("]
@closer ["}", "]", ")"]
def check(expression) do
expression
|> String.split("")
|> Enum.filter(&(&1 in @opener || &1 in @closer))
|> iterate([])
end
defp iterate([], []), do: true
defp iterate([], _stack), do: false
defp iterate([head | tail], stack) when head in @opener,
do: iterate(tail, [head | stack])
defp iterate([head | _], []) when head in @closer, do: false
defp iterate([head | tail], [stack_head | stack_tail]) when head in @closer,
do: @pairs[stack_head] == head && iterate(tail, stack_tail)
end
Isso é tudo por hoje
Obrigado por lerem isso. Estou gostando bastante de Elixir! Pattern matching é bastante poderoso e divertido, também.
Por favor, corrijam erros que eu possa ter feito (:
Espero que vocês tenham aprendido algo hoje, e que tenham um bom dia.
Top comments (0)