expression_tree.ry

module expression_tree
  purpose: Evaluate and print arithmetic expressions stored as a tree.

import std.console

public type Expression is one of
  purpose: An arithmetic expression over decimals.
  Number(value: Decimal)
  Add(left: Expression, right: Expression)
  Multiply(left: Expression, right: Expression)
  Negate(inner: Expression)
end

public function evaluate(expression: Expression) returns Decimal
  purpose: The value of the expression.
  tags: arithmetic, tree, recursion
  example: evaluate(Number(value: 4)) is 4
  example: evaluate(Add(left: Number(value: 1), right: Number(value: 2))) is 3
  example: evaluate(Negate(inner: Multiply(left: Number(value: 2), right: Number(value: 3)))) is -6

  match expression
    when Number(value) then return value
    when Add(left, right) then return evaluate(left) + evaluate(right)
    when Multiply(left, right) then return evaluate(left) * evaluate(right)
    when Negate(inner) then return 0 - evaluate(inner)
  end
end

public function render(expression: Expression) returns Text
  purpose: The expression in infix notation with parentheses around every operation.
  example: render(Add(left: Number(value: 1), right: Number(value: 2))) is "(1 + 2)"
  example: render(Multiply(left: Number(value: 2), right: Number(value: 3))) is "(2 * 3)"
  example: render(Negate(inner: Number(value: 5))) is "-5"

  match expression
    when Number(value) then return value.to_text()
    when Add(left, right) then return "({render(left)} + {render(right)})"
    when Multiply(left, right) then return "({render(left)} * {render(right)})"
    when Negate(inner) then return "-{render(inner)}"
  end
end

public function main() needs console
  purpose: Build a small tree and print it next to its value.

  let tree be Multiply(
    left: Add(left: Number(value: 1), right: Number(value: 2)),
    right: Negate(inner: Number(value: 4))
  )
  console.print("{render(tree)} evaluates to {evaluate(tree)}")
end