CODEWITHSUNDEEP
haskelltreeexpression-treeshaskell-platform
fwegmk
fwegmk

Reputation: 1

With a parse tree of an arithmetic expression how to generate the infix expression as the result in Haskell

Here is the tree definition: data Tree = Leaf Char | Node (Char, Tree, Tree)

I want to write a function treeToInfix in the form: 

treeToInfix :: Tree -> String

Here are some examples:

treeToInfix (Node ('*', (Node ('+', (Leaf 'a'), (Leaf 'b'))), (Leaf 'c'))) 
-- =>  "(a+b)*c"

treeToInfix (Node ('-', (Node ('+', (Leaf 'a') ,(Leaf 'b'))), (Leaf 'c')))
-- =>  "a+b-c"

treeToInfix (Node ('-', (Leaf 'c'), (Node ('+', (Leaf 'a') ,(Leaf 'b')))))
-- =>  "c-(a+b)"

treeToInfix (Node ('*', (Node ('/', (Leaf 'a'), (Leaf 'b'))), (Node ('/', (Leaf 'c'), (Leaf 'd'))))) 
-- =>  "a/b*c/d"

treeToInfix (Node ('+', (Node ('-', (Leaf 'a'), (Node ('*', (Leaf 'b'), (Leaf 'c'))))), (Node ('/', (Leaf 'd'), (Leaf 'e'))))) 
-- =>  "a-b*c+d/e"

I need help about the algorithm of this program.

Upvotes: 0

Views: 1276

Answers (2)

nominolo
nominolo

Reputation: 5155

Given this looks like homework you, I just give a general idea. Every operator has a precedence (and possibly associativity). This can be expressed simply as a number. The idea, then, is to print the associativity of the context as an additional parameter. So your function may look like this:

treeToInfix :: Tree -> String
treeToInfix tr = treeAux 0 tr


treeAux :: Int -> Tree -> String
treeAux prec (Node ("+",left,right)) = 
  -- TODO:
  --   * let's say precedence of '+' is 5
  --   * generate strings for children (with prec = 5)
  --   * put "+" in between
  --   * if prec > 5, put parantheses around the result
-- Similar for other cases

You can even implement associativity by varying the precedence passed to recursive calls.

Upvotes: 1

chrisdb
chrisdb

Reputation: 1115

Well, if you think about it, each stage of the operation needs to be:

  1. generate string for left operand
  2. generate string for operator
  3. generate string for right operand
  4. glue them all together in the correct order

Notice that generating the string for the left and right operands is just another application of your tree to string function, so you can code this recursively. Your base case, that you don't define recursively, is going to be how to display a Leaf.

It gets slightly more complicated if you want to ensure that brackets are only inserted when operator precedence requires it, but I'm assuming that you don't mind having some extra, strictly speaking unnecessary, brackets in the function result.

Is this enough help? I've tried to avoid just giving you the code in case it's a homework problem. I've also assumed that you understand recursion, since it's a key skill in Haskell. If you don't understand recursion, then let me know and I'll write more.

Upvotes: 0

Related Questions