I often operate at a very abstracted level in the computer, translating human thought to a high level programming language (Elixir) and creating applications that are then run by on top of the computer's operating system. My applications often interact with other applications, also running on top of the operating system. A good example here is Postgres, a database engine my applications use for persistence.

I think it is important to always look inward to try to fill the gaps we all have in different aspects in our lives. I enjoy my job but realize there is more to computers than the things I get to do on a daily basis.

A great book that outlines these ideas/gaps is "The Elements of Computing Systems" "The Elements of Computing Systems" , where the authors discuss a first principles of computing. Here is a great TED Talk about the book (and education as well).

`The Elements of Computing Systems` mentions the concept of "Stack Arithmetic" in chapter 7 (on Virtual Machines). It mentions a very interesting observation: "any arithmetic and Boolen expression - no matter how complex - can be systematically converted into, and evaluated by, a sequence of simple operations on a stack".

With that in mind, I thought it would be interesting to create a calculator that does just that: takes in a valid math expression (text) and uses stacks to do the calculation (without calling `eval` and friends).

I'm sure there are better ways of approaching this problem, but this is my current MVP. It handles precedence, parentheses and returns the correct values for the test cases I have below. The more test cases I have, the more confident I'll be of the solution. If you have any suggestions, please contact me.

A few years back, some folks in the community were experimenting with the idea of what we now call "tagged tuples". At the time, it was cool (like many things in life). However, I (and most of the community too) now see this pattern as a smell. It's a smell because it misses the chance to create an api that follows the ok/error tuple convention. The else clauses become massive, lines become long. The alternative is to extract functions that return ok/error tuples or modules if needed. A future exercise (for when life allows me) would be to refactor the code below to not use tagged tuples. With that said, it was a good v1 but it has unfortunately not aged well in my opinion.

Elixir Implementation of a stack based calculator:

ExUnit.start()

defmodule VM  do
  defmodule Calculator do
    @moduledoc """
    A stack based calculator.

    Notes:
    - I'm ommitting @spec, @doc for simplicity
    - Instead of growing downwards like the usual examples, the stack "grows to
      the left".
    - Error handling can be more robust. At this time, we are just handling happy
      paths and hoping people don't input things like "4+a/1"

    Resources:
    - "The Elements of Computer Systems"
    - http://www2.lawrence.edu/fast/GREGGJ/CMSC150/071Calculator/Calculator.html
    """

    @supported_operands ["(", ")", "*", "/", "+", "-"]

    def call(expression) when is_binary(expression) do
      calculate([], [], String.split(expression, " ", trim: true))
    end

    defp calculate([final_value], [], []) do
      final_value
    end

    defp calculate(
           values,
           [_ | _] = operands,
           ["(" = h_expression | t_expression]
         ) do
      operands = increment_stack(operands, h_expression, :operand)
      calculate(values, operands, t_expression)
    end

    defp calculate(
           values,
           [_ | _] = operands,
           [")" | t_expression]
         ) do
      calculate(values, operands, t_expression)
    end

    defp calculate(values, operands, [last_token]) do
      values = increment_stack(values, last_token, :value)
      operands = increment_stack(operands, last_token, :operand)
      [a, b | t_values] = values
      [operand | t_operands] = operands
      result = evaluate([a, b], operand)
      calculate([result | t_values], t_operands, [])
    end

    defp calculate(
           values,
           operands,
           [h_expression | t_expression] = expression
         ) do
      with {:has_two_values, [_a, _b | _]} <- {:has_two_values, values},
           {:current_operand, [current_operand | _]} <- {:current_operand, operands},
           {:next_token, [next_token | _]} <- {:next_token, expression},
           {:next_token_is_operand, true} <- {:next_token_is_operand, is_operand(next_token)},
           {:current_operand_is_parens, false} <-
             {:current_operand_is_parens, current_operand == "(" or current_operand == ")"},
           {:precedence, false} <-
             {:precedence, precedence_value(next_token) > precedence_value(current_operand)} do
        [a, b | t_values] = values
        [operand | t_operands] = operands
        result = evaluate([a, b], operand)
        calculate([result | t_values], t_operands, expression)
      else
        _reason ->
          values = increment_stack(values, h_expression, :value)
          operands = increment_stack(operands, h_expression, :operand)
          calculate(values, operands, t_expression)
      end
    end

    defp calculate(
           [_, _ | _] = values,
           ["(" | t_operands],
           [] = expression
         ) do
      calculate(values, t_operands, expression)
    end

    defp calculate(
           [a, b | t_values],
           [h_operands | t_operands],
           [] = expression
         ) do
      result = evaluate([a, b], h_operands)
      calculate([result | t_values], t_operands, expression)
    end

    # The order in the args here matters. Since this is a stack, the list
    # "head" is actually the stack's last element.
    defp evaluate([a, b], "+") do
      b + a
    end

    defp evaluate([a, b], "-") do
      b - a
    end

    defp evaluate([a, b], "*") do
      b * a
    end

    defp evaluate([a, b], "/") do
      b / a
    end

    defp increment_stack(stack, token, :value) do
      if is_value(token) do
        {int, _} = Integer.parse(token)
        [int | stack]
      else
        stack
      end
    end

    defp increment_stack(stack, token, :operand) do
      if is_operand(token), do: [token | stack], else: stack
    end

    defp is_operand(token) when token in @supported_operands, do: true
    defp is_operand(_), do: false

    defp is_value(token), do: !is_operand(token)

    defp precedence_value(operand) do
      case operand do
        "*" -> 2
        "/" -> 2
        "+" -> 1
        "-" -> 1
        e -> raise "not implemented yet #{inspect(e)}"
      end
    end
  end

  #
  # Tests
  #

  use ExUnit.Case

  describe "StackArithmetic" do
    @tag :solved
    test "calculates expressions, solved" do
      assert 10 ==  Calculator.call("4 + 6")
      assert 24 == Calculator.call("4 * 6")
      assert 8 == Calculator.call("2 + 3 * 4 - 6")
      assert 34 == Calculator.call("4 + 5 * 6")
      assert 2 == Calculator.call("3 / 3 + 1")
      assert 2 == Calculator.call("3 / 3 + 4 / 4")
      assert 8 == Calculator.call("4 * ( 4 - 2 )")
      assert 8 == Calculator.call("4 * ( 6 - 2 * ( 4 - 2 ) )")
      assert 27 == Calculator.call("4 / 2 + 8 * 4 - ( 5 + 2 )")
    end

    @tag :in_progress
    test "calculates expressions, in progress" do
      # Add more expressions you'd like to try here, see the test fail and work
      # on it until it passes! Then, move them above and keep going.
      assert true
    end
  end
end

If you'd like to run the above on your machine, I suggest the following:

• - Install Elixir on your machine
• - Copy and paste the code above to a file called `calculator_test.exs`
• - Run `elixir calculator_test.exs`

• - Nand To Tetris Book
• - TED Talk about Nand To Tetris
• - Joe Gregg's (Lawrence University) CMSC150's lecture notes about this problem