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

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

Answer 2

Давайте думать о том, когда вам нужна скобка:

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

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

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

Операнды до + не нуждаются в скобках. Если операнды являются продуктами или частными, они имеют более высокий приоритет в любом случае, и если операнды являются различиями, вам не нужны парсеры, потому что .

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

С несколькими операндами должны быть заключены в скобки, если они являются Add или Sub, но не являются Mult или Div.

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

Answer 3

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

Answer 4

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

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