[Haskell-cafe] String to binary tree
naur at post11.tele.dk
Tue May 30 01:27:35 EDT 2006
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
The following code sketch uses this idea:
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')
On Monday 29 May 2006 20:53, Nuno Santos wrote:
> 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
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe