[Haskell-cafe] String to binary tree

[Sebastian Sylvan]

On 5/30/06, Thorkil Naur <naur at post11.tele.dk> wrote:
> 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>
>

A bit OT perhaps, but I'd just like to point out this wonderful little
code snippet from the Haskell wiki-page that I've always liked, in
case nobody's seen it:

calc :: String -> Float
calc = foldl f [] . words
  where
    f (x:y:zs) "+" = y+x:zs
    f (x:y:zs) "-" = y-x:zs
    f (x:y:zs) "*" = y*x:zs
    f (x:y:zs) "/" = y/x:zs
    f xs y = read y : xs

That's it. An RPN evaluator in a couple of lines.


-- 
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862