Verificando parênteses, colchetes e chaves correspondentes com Elixir
Tags: elixir, algorithms, functional
Published: 2021-04-08 00:28:33

🏴󠁧󠁢󠁥󠁮󠁧󠁿 English version of this text [_here_](https://dev.to/lucassperez/verify-matching-parens-brackets-and-braces-with-elixir-dh5)!

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:
```elixir
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](https://pt.wikipedia.org/wiki/Pilha_(inform%C3%A1tica)) 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:
```elixir
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:
```elixir
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:
```elixir
"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:
```elixir
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:
```elixir
&(&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:
```elixir
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:
```elixir
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:
```elixir
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:
```elixir
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:
```elixir
[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:
```elixir
[elemento_novo | pilha]
```
Isso é uma lista cuja cabeça é `elemento_novo`, e a cauda é `pilha`. Sempre podemos ir no iex e fazer alguns experimentos:
```elixir
[1 | 9,8,7]
#=> [1,9,8,7]
```
Então, nossa função pode ficar meio assim:
```elixir
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:
```elixir
defp iterate(["}" | tail], stack)
defp iterate(["]" | tail], stack)
defp iterate([")" | tail], stack)
```
E daí pra cada uma delas, eu fiz um if/else simples:
```elixir
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:
```elixir
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:
```elixir
1+2
#=> 3
Kernel.+(1,2)
#=> 3
```
A comparação `==` também faz parte do módulo `Kernel`, então podemos fazer assim:
```elixir
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:
```elixir
defp iterate([], stack), do: stack == []
```
Outro jeito é de usar o pattern matching no segundo argumento, também!
```elixir
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:
```elixir
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:
```ex
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:
```elixir
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:
```elixir
defmodule Parens do
  @opener ["{", "[", "("]
  @closer ["}", "]", ")"]
end
```
Com essa pequena adição, podemos reescrever nossas guardas e nosso filtro, desta maneira:
```elixir
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:
```elixir
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:
```elixir
@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:
```elixir
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.