Сопоставление с образцом, возвращающее строковое представление математического выражения

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

Давайте подумаем о том, когда вам нужны парены:

Прежде всего, всегда заключать в скобки парето вокруг определенных операций - неправильный подход.То, нужно ли заключать скобки в скобки или нет, зависит не только от того, какой оператор используется в термине, но также от того, какой оператор является операндом.

Например, когда 1+2 и 3+4 являются операндамидо +, должно быть 1+2+3+4 - без паренов.Однако, если оператор *, он должен быть (1+2) * (3+4).

Так для каких комбинаций операторов нам нужны парены?

Операнды + никогда не должны бытькруглые скобки.Если операнды являются продуктами или частными, они в любом случае имеют более высокий приоритет, и если операнды являются разностями, вам не нужны парены, потому что x + (y - z) = x + y -z.

С - это немного отличается.* и / все еще не нужно заключать в скобки, потому что они имеют более высокий приоритет, но + и - делают, если они во втором операнде, потому что x + y - z = (x + y) - z, но x - y + z != x - (y + z).

При использовании Mult оба операнда должны быть заключены в скобки, если они являются «Добавить» или «Sub», но не если они являются «Mult» или «Div».

При использовании «Div» первый операнд должен быть заключен в скобки, если это «Add» или «Sub»и второе всегда должно быть заключено в скобки (если, конечно, это не Int или Float).

Answer 2

Во-первых, определите список уровней приоритета для ваших операторов:

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

Наконец,определите вспомогательную функцию печати, которая имеет аргумент «priority», означающий «кстати, вы заключены в выражение, которое имеет приоритет 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
;;

Answer 3

Довольно простой и в то же время довольно общий ответ (работает для других синтаксисов, нежели математических выражений): выберите приоритеты (и, если вы требовательны, ассоциации) для ваших конструкторов и добавьте круглые скобки только тогда, когда конструктор подтериев имеет более низкий приоритет, чем текущий конструктор.

Точнее: когда вы хотите напечатать конструктор C(x1,x2,x3..), вы смотрите на конструктор головы каждого xi (если x1 равен D(y1,y2..), его конструктор головы равен D), сравните приоритет уровни C и D. Если приоритет D ниже, вы добавляете круглые скобки вокруг строкового представления x2.

Answer 4

Мне кажется, что вы хотите построить некоторый набор правил сокращения, которые могут применяться для получения «предварительно подтвержденной» или наиболее сокращенной формы ваших выражений, основанной на порядке операций и, например, коммутативность, ассоциативность и т. д. Например, (a + a) => a + a, (a * b) + c => a * b + c и т. д.