Shunting yard algorithm in Elixir

shunting_yard.ex

defmodule ShuntingYard do

    @moduledoc """

    Shunting yard algorithm as explained at https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    Supports an use-case of mine where all operators are left-associative, 
    and no functions are present in the expression

    iex> c("shunting_yard.ex")

    ## Example: 
    
    ```
    iex> tokens = [
        %{type: :num, value: "3"}, 
        %{type: :op, value: "*"}, 
        %{type: :num, value: "2"}, 
        %{type: :op, value: "+"},
        %{type: :left, value: "("}, 
        %{type: :num, value: "4"},
        %{type: :op, value: "*"},
        %{type: :num, value: "5"}, 
        %{type: :right, value: ")"},
    ]

    iex> tokens |> ShuntingYard.parse |> Enum.map(fn %{value: x} -> x end)
    ["3", "2", "*", "4", "5", "*", "+"]
    ```
    """

    @precendence %{"+" => 1, "-" => 1, "*" => 2, "/" => 2}

    defp add_predence_key_to_operators(tokens) do
        Enum.map(tokens, &add_precedence_key_if_operator/1)
    end

    defp add_to_queue(token, output_queue, call_id) do
        t = token.value
        output_queue ++ [token]
    end

    defp add_precedence_key_if_operator(token) do
        if token.type == :op do
            Dict.put_new(token, "precendence", @precendence[token.value])
        else
            token
        end
    end

    defp has_parens(stack) do
        count = stack |> 
        Enum.filter(fn %{type: x} -> x == :left || x == :right end) |> 
        Enum.count()
        count != 0
    end

    def run do
        # Debugging
        tokens = [
            %{type: :num, value: "3"}, 
            %{type: :op, value: "*"}, 
            %{type: :num, value: "2"}, 
            %{type: :op, value: "+"},
            %{type: :left, value: "("}, 
            %{type: :num, value: "4"},
            %{type: :op, value: "*"},
            %{type: :num, value: "5"}, 
            %{type: :right, value: ")"},
        ]
        yeah = parse(tokens)
        Enum.map yeah, fn %{value: x} -> x end
    end

    def parse(tokens) do
        tokens = add_predence_key_to_operators(tokens)
        {_, output_queue, stack} = parse_impl(tokens, [], [])
        if has_parens(stack) do
            raise "Mismatched parens error"
        end
        output_queue ++ stack
    end

    def parse_impl(tokens, output_queue, stack) do
        if tokens == [] do
            {tokens, output_queue, stack}
        else
            [first | rest] = tokens
            {output_queue, stack} = add_token(first, output_queue, stack)
            parse_impl(rest, output_queue, stack)
        end
    end

    def add_token(token, output_queue, stack) do
        cond do
            token.type == :num ->
                {add_to_queue(token, output_queue, 1), stack}

            token.type == :left ->
                {output_queue, [token] ++ stack}

            token.type == :right ->
                add_right_paren(token, output_queue, stack)

            token.type == :op ->
                add_operator(token, output_queue, stack)

            true ->
                raise "Invalid token present"
        end
    end

    defp add_right_paren(token, output_queue, stack) do
        top_op = List.first stack
        if top_op == nil do
            raise "Matching parens not found"
        end

        [_ | rest] = stack
        if top_op.type == :left  do
            {output_queue, rest}
        else
            add_right_paren(token, add_to_queue(top_op, output_queue, 2), rest)
        end

    end

    defp add_operator(token, output_queue, stack) do
        {partial_queue, s1} = pop_higher_precendence_ops_to_queue(token, [], stack)
        latest_stack = [token] ++ s1
        {output_queue ++ partial_queue, latest_stack}
    end

    defp pop_higher_precendence_ops_to_queue(token, partial_queue, stack) do
        top_op = List.first stack
        if top_op == nil do
            {partial_queue, stack}
        else
            if top_op.value == "(" || top_op.value == ")" do
                {partial_queue, stack}
            else
                if token["precendence"] <= top_op["precendence"] do
                    [top_op | rest] = stack
                    pop_higher_precendence_ops_to_queue(token, partial_queue ++ [top_op], rest)
                else
                    {partial_queue, stack}
                end
            end
        end
    end
    
end