[Haskell-cafe] String to binary tree

Nuno Santos developer at imaginando.net
Mon May 29 14:53:30 EDT 2006


I have this type which represents polish expressions (floorplan  

data PeAux a = Folha Char | Nodo Char (PeAux a) (PeAux a)  deriving Show

The reverse polish expression are the result of doing a post order  
visit to the tree

One example of this reverse polish expression is "12H3V"

and a example of tree is

pe5 = Node 'V' (Node 'H' (Folha '1') (Folha '2')) (Folha '3')

the tree above is the same as the expression "12H3V"

What i need and i cant do is turn the expression a tree again...

I have done the following:

converteAux [] (x,y) = (x,y)
converteAux (a:t) (x,y)
         | ((length (a:t))<3) = converteAux [] (x,y ++ (a:t))
converteAux (a:b:t) (x,y)
         | ((length (a:b:t))<3) = converteAux [] (x,y ++ (a:b:t))
converteAux (a:b:c:t) (x,y)
         | (isNumber a) && (isNumber b) && (isLetter c) = converteAux  
t (x ++ [(Nodo c (Folha a) (Folha b))],y)
         | otherwise = converteAux (b:c:t) (x,y++[a])

The strategy followed is to recognize operand, operand, operator and  
then put it as a basic element in a list, for instance, 12H -> Node  
'H' (Folha '1') (Folha '2')

And at the end put it togheter in one tree. ( not done yet)

But i'm getting to the conclusion that it doesnt cover every case...

Can anybody give me a light here?

Many thx,

Best regards,

Nuno Santos

More information about the Haskell-Cafe mailing list