足し算・かけ算からなる数式を表す型

まずは型の定義。

# type arith = Const of int | Add of arith * arith | Mul of arith * arith;;
type arith = Const of int | Add of arith * arith | Mul of arith * arith

式を評価する関数・文字列に変換する関数・展開する関数

# let rec eval = function
    Const n -> n
  | Add (a, b) -> eval a + eval b
  | Mul (a, b) -> eval a * eval b;;
val eval : arith -> int = <fun>
# let rec string_of_arith = function
    Const n -> string_of_int n
  | Add (a, b) -> "(" ^ string_of_arith a ^ "+" ^ string_of_arith b ^ ")"
  | Mul (a, b) -> string_of_arith a ^ "*" ^ string_of_arith b;;
val string_of_arith : arith -> string = <fun>
# let rec expand = function
    Mul (a, Add (b, c)) ->
      let (a', b', c') = (expand a, expand b, expand c) in
      Add (expand (Mul (a', b')), expand (Mul (a', c')))
  | Mul (Add (a, b), c) ->
      let (a', b', c') = (expand a, expand b, expand c) in
      Add (expand (Mul (a', c')), expand (Mul (b', c')))
  | Add (a, b) -> Add (expand a, expand b)
  | a -> a;;
- : arith -> arith = <fun>

いろんな式について試してみた。

# let exp1 = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5));;
val exp1 : arith = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5))
# string_of_arith exp1;;
- : string = "(3+4)*(2+5)"
# eval exp1;;
- : int = 49
# string_of_arith (expand exp1);;
- : string = "((3*2+4*2)+(3*5+4*5))"

# let exp2 = Add (Mul (Const 3, Add (Const 4, Const 5)), Mul (Const 5, Add (Const 3, Const 4)));;
val exp2 : arith =
  Add (Mul (Const 3, Add (Const 4, Const 5)),
   Mul (Const 5, Add (Const 3, Const 4)))
# string_of_arith exp2;;
- : string = "(3*(4+5)+5*(3+4))"
# eval exp2;;
- : int = 62
# string_of_arith (expand exp2);;
- : string = "((3*4+3*5)+(5*3+5*4))"

# let exp3 = Mul (Add (Mul (Const 3, Const 2), Mul (Const 4, Const 3)),
                 Add (Mul (Const 2, Const 3),
                      Add (Mul (Const 1, Const 2), Mul (Const 2, Const 3))));;
val exp3 : arith =
  Mul (Add (Mul (Const 3, Const 2), Mul (Const 4, Const 3)),
   Add (Mul (Const 2, Const 3),
    Add (Mul (Const 1, Const 2), Mul (Const 2, Const 3))))
# string_of_arith exp3;;
- : string = "(3*2+4*3)*(2*3+(1*2+2*3))"
# eval exp3;;
- : int = 252
# string_of_arith (expand exp3);;
- : string = "((3*2*2*3+4*3*2*3)+((3*2*1*2+4*3*1*2)+(3*2*2*3+4*3*2*3)))"

無駄な括弧が多いので、string_of_arithを書き換えてみた。

# let rec string_of_arith = function
    Const n -> string_of_int n
  | Add (a, b) -> string_of_arith a ^ "+" ^ string_of_arith b
  | Mul (a, b) -> 
      let string_of = function
        Add _ as c -> "(" ^ string_of_arith c ^ ")"
      | c -> string_of_arith c
      in
      string_of a ^ "*" ^ string_of b;;
val string_of_arith : arith -> string = <fun>

かけ算の中身が足し算の時のみ、括弧が付きます。これでOKなはず。

val string_of_arith : arith -> string = <fun>
# string_of_arith exp1;;
- : string = "(3+4)*(2+5)"
# string_of_arith (expand exp1);;
- : string = "3*2+4*2+3*5+4*5"
# string_of_arith exp2;;
- : string = "3*(4+5)+5*(3+4)"
# string_of_arith (expand exp2);;
- : string = "3*4+3*5+5*3+5*4"
# string_of_arith exp3;;
- : string = "(3*2+4*3)*(2*3+1*2+2*3)"
# string_of_arith (expand exp3);;
- : string = "3*2*2*3+4*3*2*3+3*2*1*2+4*3*1*2+3*2*2*3+4*3*2*3"
# let exp4 = Add (Const 1, Add (Const 2, Add (Const 3, Add (Const 4, Const 5))));;
val exp4 : arith =
  Add (Const 1, Add (Const 2, Add (Const 3, Add (Const 4, Const 5))))
# string_of_arith exp4;;
- : string = "1+2+3+4+5"
# let exp5 = Mul (exp4, Mul (exp4, exp4));;
val exp5 : arith =
  Mul (Add (Const 1, Add (Const 2, Add (Const 3, Add (Const 4, Const 5)))),
   Mul (Add (Const 1, Add (Const 2, Add (Const 3, Add (Const 4, Const 5)))),
    Add (Const 1, Add (Const 2, Add (Const 3, Add (Const 4, Const 5))))))
# string_of_arith exp5;;
- : string = "(1+2+3+4+5)*(1+2+3+4+5)*(1+2+3+4+5)"
# string_of_arith (expand exp5);;
- : string =
"1*1*1+1*2*1+1*3*1+1*4*1+1*5*1+1*1*2+1*2*2+1*3*2+1*4*2+1*5*2+1*1*3+1*2*3+1*3*3+1*4*3+1*5*3+1*1*4+1*2*4+1*3*4+1*4*4+1*5*4+1*1*5+1*2*5+1*3*5+1*4*5+1*5*5+2*1*1+3*1*1+4*1*1+5*1*1+2*2*1+3*2*1+4*2*1+5*2*1+2*3*1+3*3*1+4*3*1+5*3*1+2*4*1+3*4*1+4*4*1+5*4*1+2*5*1+3*5*1+4*5*1+5*5*1+2*1*2+3*1*2+4*1*2+5*1*2+2*2*2+3*2*2+4*2*2+5*2*2+2*3*2+3*3*2+4*3*2+5*3*2+2*4*2+3*4*2+4*4*2+5*4*2+2*5*2+3*5*2+4*5*2+5*5*2+2*1*3+3*1*3+4*1*3+5*1*3+2*2*3+3*2*3+4*2*3+5*2*3+2*3*3+3*3*3+4*3*3+5*3*3+2*4*3+3*4*3+4*4*3+5*4*3+2*5*3+3*5*3+4*5*3+5*5*3+2*1*4+3*1*4+4*1*4+5*1*4+2*2*4+3*2*4+4*2*4+5*2*4+2*3*4+3*3*4+4*3*4+5*3*4+2*4*4+3*4*4+4*4*4+5*4*4+2*5*4+3*5*4+4*5*4+5*5*4+2*1*5+3*1*5+4*1*5+5*1*5+2*2*5+3*2*5+4*2*5+5*2*5+2*3*5+3*3*5+4*3*5+5*3*5+2*4*5+3*4*5+4*4*5+5*4*5+2*5*5+3*5*5+4*5*5+5*5*5"
# eval exp5;;
- : int = 3375
# eval (expand exp5);;
- : int = 3375

最低限な個数の括弧だけになりました。展開後は括弧が消えています。