[Haskell-cafe] String to binary tree

[Thorkil Naur]

Hello,

It seems that what you need is the technique of evaluating an expression in 
reverse polish notation by using a stack. This technique is well known in 
subjects related to compiler construction.

Basically, the expression (list of operands and operators) is processed 
sequentially from left to right. If an operand (in your case: A character c 
for which isNumber c is true) is encountered, it is pushed onto the stack. If 
an operator (in your case: A character c for which isLetter is true) is 
enountered, it pops its operands (one or more) from the top of the stack and 
pushes the result of applying the operator to the operands back onto the 
stack.

The following code sketch uses this idea:

  ...
  import Char
  ...
  isNumber = isDigit
  isLetter = isAlpha

  cvBase stack c | isNumber c = Folha c:stack
  cvBase (tr:tl:stack) c | isLetter c = Node c tl tr : stack

  cv s = let [t] = foldl cvBase [] s in t

Example using Hugs:

  Main> cv "12H3V"
  Node 'V' (Node 'H' (Folha '1') (Folha '2')) (Folha '3')
  Main>

Regards
Thorkil Naur
On Monday 29 May 2006 20:53, Nuno Santos wrote:
> Hi,
> 
> I have this type which represents polish expressions (floorplan  
> representation):
> 
> 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
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>