pattern-matching restituendo una stringa che rappresenta un'espressione matematica

Question

devo scrivere una discarica funzione che prende un'espressione

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

e restituisce una rappresentazione di stringa di esso. Per esempio:

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

dovrebbe restituire qualcosa rispettivamente

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

ho scritto in questo modo:

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

e restituito le espressioni sono corretti, ma ancora non ottimale. (per Aggiungi (Int 1, Int 2)) è (1 + 2) e dovrebbe essere 1 + 2). Come posso risolvere questo? (corrispondenza senza nidificato di modello che non è una buona idea)

Answer 1

In primo luogo, definire un elenco di livelli di priorità per gli operatori:

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

Un costrutto utile è "wrap tra parentesi, se questa condizione è vera":

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

Infine, definire un ausiliario funzione di stampa che viene fornita con un argomento "prioritario" che significa "a proposito, sei avvolto in un'espressione che ha priorità X, quindi proteggi l'output di conseguenza":

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

Pensiamo a quando avete bisogno di parentesi:

Prima di tutto parentesi sempre avvolgono certe operazioni è l'approccio sbagliato. Se un termine deve essere tra parentesi o meno non dipende solo da quale operatore è usato nel termine, ma anche da quale operatore il termine è un operando.

E.g. quando 1+2 e 3+4 sono operandi su +, dovrebbe essere 1+2+3+4 - nessun paren. Tuttavia, se l'operatore è *, è necessario che sia (1+2) * (3+4).

Quindi per quali combinazioni di operatori abbiamo bisogno di parents?

Gli operandi su + non devono mai essere tra parentesi. Se gli operandi sono prodotti o quozienti, hanno comunque precedenza superiore, e se gli operandi sono differenze, non è necessario alcun parto perché x + (y - z) = x + y -z.

Con - è un po 'diverso. * e / ancora non devono essere parentesi perché hanno precedenza più alta, ma + e - fanno se sono nel secondo operando perché x + y - z = (x + y) - z, ma x - y + z != x - (y + z).

Con Mult entrambi gli operandi devono essere tra parentesi se sono Aggiungi o Sottotitoli, ma non se sono Mult o Div.

Con Div il primo operando deve essere tra parentesi se è Aggiungi o Sotto e il secondo deve sempre essere tra parentesi (a meno che non sia Int o Float, ovviamente).

Answer 3

Mi sembra che vogliate creare un insieme di regole di riduzione che possono essere applicate per ottenere la forma "prettificata" o più ridotta delle vostre espressioni, in base all'ordine delle operazioni e ad es. commutatività, associatività, ecc. Ad esempio (a + a) => a + a, (a * b) + c => a * b + c e così via.

Answer 4

Una risposta piuttosto semplice ma piuttosto generico (lavora per altre sintassi di espressioni matematiche): pick precedenze (e, se siete schizzinosi, associativities) per i vostri costruttori, e solo aggiungere parentesi quando un costruttore sottotermine ha la precedenza più bassa rispetto al costruttore corrente.

Più precisamente: quando si desidera stampare un costruttore C(x1,x2,x3..), si guarda il costruttore capo di ogni xi (se x1 è D(y1,y2..), il suo costruttore testa è D), confrontare i livelli di precedenza di C e D. Se la precarietà di D è inferiore, si aggiunge la parentesi attorno alla rappresentazione di stringa di x2.