模式匹配返回数学表达式的字符串表示

Question

我必须编写一个带有表达式的函数转储

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

并返回它的字符串表示形式.例如:

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

应该分别回来

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

我写过这样的话:

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)
;;

并且返回的表达式是正确的,但仍然不是最佳的.(对于Add(Int 1,Int 2)),它是(1 + 2)并且应该是1 + 2).我怎样才能解决这个问题？(没有嵌套模式匹配,这不是一个好主意)

Answer 1

首先，为您的操作员定义优先级列表：

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

一个有用的构造是“如果此条件为真，则用括号括起来”：

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

最后，定义一个辅助打印函数，它提供了一个“优先级”参数，意思是“顺便说一句，你被包装在一个具有优先级 X 的表达式中，因此相应地保护你的输出”：

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
;;