Pattern-matching returning a string representation of math expression

Question

I have to write a function dump which takes an expression

type expression = 
| Int of int
| Float of float
| Add of expression * expression
| Sub of expression * expression
| Mult of expression * expression
| Div of expression * expression
;;

and returns a string representation of it. For example:

dump (Add (Int 1, Int 2));;
dump (Mult (Int 5, Add(Int 2, Int 3)), Int 1)

should return respectively

- : string = "1+2"
- : string = "5*(2+3)-1"

I've written something like this:

let rec dump e = match e with
    | Int a -> string_of_int a
    | Float a -> string_of_float a
    | Add (e1,e2) -> "(" ^ (dump e1) ^ "+" ^ (dump e2) ^ ")"
    | Sub (e1,e2) -> "(" ^ (dump e1) ^ "-" ^ (dump e2) ^ ")"
    | Mult (e1,e2) -> (dump e1) ^ "*" ^ (dump e2)
    | Div (e1,e2) -> (dump e1) ^ "/" ^ (dump e2)
;;

and returned expressions are correct, but still not optimal. (for Add (Int 1, Int 2)) it is (1+2) and should be 1+2 ). How can I fix this? (without nested pattern matching which isn't a good idea)

Answer 1

Let's think about when you need parens:

First of all always wrapping parens around certain operations is the wrong approach. Whether a term needs to be parenthesized or not does not only depend on which operator is used in the term, but also which operator the term is an operand to.

E.g. when 1+2 and 3+4 are operands to +, it should be 1+2+3+4 - no parens. However if the operator is *, it needs to be (1+2) * (3+4).

So for which combinations of operators do we need parens?

The operands to + never need to be parenthesized. If the operands are products or quotients, they have higher precedence anyway, and if the operands are differences, you need no parens because x + (y - z) = x + y -z.

With - it's a bit different. * and / still don't need to be parenthesized because they have higher precedence, but + and - do iff they're in the second operand because x + y - z = (x + y) - z, but x - y + z != x - (y + z).

With Mult both operands need to be parenthesized if they're Add or Sub, but not if they're Mult or Div.

With Div the first operand needs to be parenthesized if it's Add or Sub and the second always needs to be parenthesized (unless it's an Int or Float, of course).

Answer 2

First, define a list of priority levels for your operators:

module Prio = struct
  let div = 4
  let mul = 3
  let sub = 2
  let add = 1
end

An useful construct is "wrap in brackets if this condition is true" :

let wrap_if c str = if c then "("^str^")" else str

Finally, define an auxiliary printing function which is provided with a "priority" argument meaning "by the way, you're wrapped in an expression which has priority X, so protect your output accordingly":

let dump e = 
  let rec aux prio = function
    | Int a -> string_of_int a
    | Float a -> string_of_float a
    | Add (e1,e2) -> 
        wrap_if (prio > Prio.add) (aux Prio.add e1 ^ "+" ^ aux Prio.add e2)
    | Sub (e1,e2) -> 
        wrap_if (prio > Prio.add) (aux Prio.add e1 ^ "-" ^ aux Prio.sub e2)
    | Mult (e1,e2) -> 
        wrap_if (prio > Prio.mul) (aux Prio.mul e1 ^ "*" ^ aux Prio.mul e2)
    | Div (e1,e2) -> 
        wrap_if (prio > Prio.mul) (aux Prio.mul e1 ^ "/" ^ aux Prio.div e2)
  in aux Prio.add e
;;