CODEWITHSUNDEEP
ocaml
Anatoliy Sokolov
Anatoliy Sokolov

Reputation: 397

Changing an expression to string

I need to convert an arithmetic sequence that uses this type:

type expr =
      VarX
    | VarY
    | Sine of expr
    | Cosine of expr
    | Average of expr * expr
    | Times of expr * expr
    | Thresh of expr * expr * expr * expr

here are the definitions for all the things in it:

e ::= x | y | sin (pi*e) | cos (pi*e) | ((e + e)/2) | e * e | (e<e ? e : e)

need to convert something like this:

 exprToString (Thresh(VarX,VarY,VarX,(Times(Sine(VarX),Cosine(Average(VarX,VarY))))));;

to this:

string = "(x<y?x:sin(pi*x)*cos(pi*((x+y)/2)))"

I know I have to do this recursively by matching each expr with its appropriate string but Im not sure where the function begins matching or how to recurse through it. Any help or clues would be appreciated

Upvotes: 0

Views: 950

Answers (1)

camlspotter
camlspotter

Reputation: 9030

Here is a simplified version of what you probably want:

type expr = 
  | VarX
  | Sine of expr

let rec exprToString = function
  | VarX -> "x"
  | Sine e -> "sin(" ^ exprToString e ^ ")"

let () = print_endline (exprToString (Sine (Sine (Sine (Sine VarX)))))

It recurses over the AST nodes and create the string representation of the input by concatenating the string representations of the nodes.

This approach may not work nicely for bigger real world examples since:

  • String concatenation (^) creates a new string from two, this is slower than using some more appropriate data structure such as Buffer.t
  • Too many parentheses, ex, (2*(2*(2*2))), not 2*2*2*2. If you want minimize the number of parentheses, your algorithm must be aware of operator precedence and connectivity.

Upvotes: 1

Related Questions