Shunting yard

shunting_yard.ex

defmodule ShuntingYard do
  @doc """
  Implementation of https://en.wikipedia.org/wiki/Shunting-yard_algorithm

  ## Examples

      iex> ShuntingYard.to_rpn(
      ...>   [
      ...>     value: 4,
      ...>     operator: :*,
      ...>     paren: :left,
      ...>     value: 5,
      ...>     operator: :+,
      ...>     value: 3,
      ...>     operator: :*,
      ...>     value: 2,
      ...>     paren: :right,
      ...>     operator: :+,
      ...>     value: 6
      ...>   ],
      ...>   operators: [+: 1, *: 2]
      ...> )
      [
        value: 4,
        value: 5,
        value: 3,
        value: 2,
        operator: :*,
        operator: :+,
        operator: :*,
        value: 6,
        operator: :+
      ]

      iex> ShuntingYard.to_rpn(
      ...>   [
      ...>     my_custom_expression: %{id: "Q1"},
      ...>     operator: :and,
      ...>     paren: :left,
      ...>     my_custom_expression: %{id: "Q2"},
      ...>     operator: :or,
      ...>     my_custom_expression: %{id: "Q3"},
      ...>     operator: :and,
      ...>     my_custom_expression: %{id: "Q4"},
      ...>     paren: :right,
      ...>     operator: :or,
      ...>     my_custom_expression: %{id: "Q5"}
      ...>   ],
      ...>   operators: [or: 1, and: 2]
      ...> )
      [
        my_custom_expression: %{id: "Q1"},
        my_custom_expression: %{id: "Q2"},
        my_custom_expression: %{id: "Q3"},
        my_custom_expression: %{id: "Q4"},
        operator: :and,
        operator: :or,
        operator: :and,
        my_custom_expression: %{id: "Q5"},
        operator: :or
      ]
  """
  @type operator :: atom()
  @type token :: {:operator, operator()} | {:paren, :left | :right} | {atom(), any()}
  @type infix_notation :: [token]
  @type rpn :: [token]
  @spec to_rpn(infix_notation(), operators: [{operator(), precedence :: number()}]) :: rpn()
  def to_rpn(tokens, operators: operators) do
    {output_queue, stack} =
      tokens
      |> add_precedence_to_operators(operators)
      |> Enum.reduce({[], []}, fn token, {output_queue, stack} = acc ->
        case token do
          {:operator, _, _} -> add_operator(token, acc)
          {:paren, :left} -> {output_queue, [token | stack]}
          {:paren, :right} -> add_right_paren(token, acc)
          {_, _} -> add_to_output_queue(token, acc)
        end
      end)

    remove_precedence_from_operators(output_queue ++ stack)
  end

  defp remove_precedence_from_operators(tokens) do
    tokens
    |> Enum.map(fn
      {:operator, _precedence, operator} -> {:operator, operator}
      token -> token
    end)
  end

  defp add_precedence_to_operators(tokens, operators) do
    tokens
    |> Enum.map(fn
      {:operator, operator} -> {:operator, Keyword.fetch!(operators, operator), operator}
      token -> token
    end)
  end

  defp add_to_output_queue(token, {output_queue, stack}) do
    {output_queue ++ [token], stack}
  end

  defp add_right_paren(token, {output_queue, stack}) do
    case stack do
      [{:paren, :left} | rest] -> {output_queue, rest}
      [{:operator, _, _} = top_op | rest] -> add_right_paren(token, add_to_output_queue(top_op, {output_queue, rest}))
    end
  end

  defp add_operator(token, {output_queue, stack}) do
    {partial_queue, stack} = pop_higher_precedence_ops_to_queue(token, {[], stack})
    {output_queue ++ partial_queue, [token | stack]}
  end

  defp pop_higher_precedence_ops_to_queue(
         {:operator, token_precedence, _operator} = token,
         {partial_queue, [{:operator, top_op_precedence, _} = top_op | rest]}
       )
       when token_precedence <= top_op_precedence do
    pop_higher_precedence_ops_to_queue(token, {partial_queue ++ [top_op], rest})
  end

  defp pop_higher_precedence_ops_to_queue(_, acc) do
    acc
  end
end