delimiters.ex

defmodule BalancedDelimiters do
  @openers [
    ?(,
    ?[,
    ?{
  ] 

  @closers [
    ?),
    ?],
    ?}
  ]

  # Vamos simular uma pilha usando chamadas de função.
  #
  # O elemento no topo da pilha vai ser dado pelo segundo argumento
  # da chamada atual. Esse elemento vai representar o atual delimitador
  # de fechamento esperado.
  #
  # No início, a pilha vai estar vazia. Essa situação é representada pelo
  # segundo argumento ser `nil`.
  #
  # Nós avaliamos usando a pilha e verificamos os casos de sucesso e fracasso.
  # Os casos de sucesso e fracasso serão explicados abaixo.
  def check(string) do
    case check(string, nil) do
      {:balanced, ""} -> true
      _ -> false
    end
  end

  # Se chegamos no fim da string com pilha vazia, retornamos sucesso.
  # O sucesso será representado por um par do átomo balanced seguido da 
  # string vazia. O motivo dessa representação é que ela será útil para
  # a recursão que queremos fazer.
  def check("", nil), do: {:balanced, ""}

  # Se chegamos no fim da string e a pilha _não está_ vazia, nossa string
  # está desbalanceada.
  def check("", _expected), do: :unbalanced

  # Se a string começa com um delimitador de abertura, nós colocamos o delimitador
  # de fechamento esperado no topo da pilha (fazendo uma chamada recursiva.
  #
  # Aqui se justifica a representação de sucesso que escolhemos - quando uma chamada
  # recursiva encontra o delimitador de fechamento esperado, ela retorna o
  # trecho restante da string para podermos continuar a chamada no "nível anterior"
  # da pilha.
  #
  # Se a chamada recursiva retornar qualquer coisa que não seja `{:balanced, string}`
  # a função retorna esse valor imediatamente (essa é a semântica da palavra-chave
  # `with` em Elixir
  def check(<<char::utf8, rest::binary>>, current) when char in @openers do
    with {:balanced, remaining} <- check(rest, matching_closer(char)) do
      check(remaining, current)
    end
  end

  # Se temos um caractere na pilha e encontramos o caractere no início da
  # string, então o trecho que estávamos analisando está balanceado e retornamos
  # o trecho restante da string para o nível inferior da pilha.
  def check(<<char::utf8, rest::binary>>, expected) when char == expected do
    {:balanced, rest}
  end

  # Se encontramos um delimitador de fechamento mas ele não é esperado 
  # (se fosse esperado teria entrado no caso anterior), a string está 
  # desbalanceada.
  def check(<<char::utf8, _rest::binary>>, _expected) when char in @closers do
    :unbalanced
  end

  # Finalmente, em qualquer outro caso que não seja os casos anteriores,
  # o caractere pode ser ignorado pois não é um delimitador de abertura
  # nem de fechamento
  def check(<<_char::utf8, rest::binary>>, current) do
    check(rest, current)
  end

  def matching_closer(?(), do: ?)
  def matching_closer(?[), do: ?]
  def matching_closer(?{), do: ?}
end