[Haskell-cafe] String to binary tree
Sebastian Sylvan
sylvan at student.chalmers.se
Tue May 30 09:10:27 EDT 2006
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
More information about the Haskell-Cafe
mailing list