patrón de coincidencia de devolver una representación de cadena de la expresión matemática

Question

tengo que escribir un volcado de función que toma una expresión

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

y devuelve una representación de cadena de la misma. Por ejemplo:

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

debe devolver algo respectivamente

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

he escrito así:

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

y regresó expresiones son correctas, pero todavía no es óptima. (para Agregar (Int 1, Int 2)) es (1 + 2) y debe ser 1 + 2). ¿Cómo puedo arreglar esto? (juego sin patrón anidado que no es una buena idea)

Answer 1

En primer lugar, definir una lista de niveles de prioridad para sus operadores:

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

Un constructo útil es "envolver entre paréntesis si esta condición es verdadera":

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

último, definen un auxiliar función de impresión que se proporciona con un argumento de "prioridad" que significa "a propósito, está envuelto en una expresión que tiene prioridad X, así que proteja su salida en consecuencia":

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

Vamos a pensar cuando se necesita parens:

En primer lugar los parens siempre envolver alrededor de ciertas operaciones es el enfoque equivocado. Si un término necesita ser entre paréntesis o no, no solo depende de qué operador se usa en el término, sino también a qué operador es el operador.

E.g. cuando 1+2 y 3+4 son operandos a +, debe ser 1+2+3+4 - sin parens. Sin embargo, si el operador es *, debe ser (1+2) * (3+4).

Entonces, ¿para qué combinaciones de operadores necesitamos paréntesis?

Los operandos a + nunca deben estar entre paréntesis. Si los operandos son productos o cocientes, tienen mayor precedencia de todos modos, y si los operandos son diferencias, no necesita paréntesis porque x + (y - z) = x + y -z.

Con - es un poco diferente. * y / todavía no necesitan ser entre paréntesis porque tienen una precedencia más alta, pero + y - lo hacen si están en el segundo operando porque x + y - z = (x + y) - z, pero x - y + z != x - (y + z).

Con Mult, ambos operandos deben estar entre paréntesis si son Add o Sub, pero no si son Mult o Div.

Con Div, el primer operando debe estar entre paréntesis si es Agregar o Sub, y el segundo siempre tiene que estar entre paréntesis (a menos que sea Int o Float, por supuesto).

Answer 3

Me parece que desea construir un conjunto de reglas de reducción que se pueden aplicar para obtener la forma "embellecida" o más reducida de sus expresiones, según el orden de las operaciones y, por ejemplo, conmutatividad, asociatividad, etc. Por ejemplo, (a + a) => a + a, (a * b) + c => a * b + c y así sucesivamente.

Answer 4

Una respuesta bastante simple pero bastante genérica (funciona para otras sintaxis que las expresiones matemáticas): elija precedencias (y, si es quisquillosa, asociatividades) para sus constructores, y solo agregue paréntesis cuando un constructor subterráneo tenga menor precedencia que el constructor actual.

Más exactamente: cuando se quiere imprimir un constructor C(x1,x2,x3..), se mira el constructor de la cabeza de cada xi (si es x1D(y1,y2..), su constructor cabeza es D), comparar los niveles de precedencia de C y D. Si la precendencia de D es menor, agregue paréntesis alrededor de la representación de cadena de x2.