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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On 5/30/06, 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>
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
Hello, Both my Hugs and my GHCi report a type error when presented with this. A possible repaired version looks like this: calc :: String -> Float calc = g . 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 g [r] = r Not as small, but still quite nice. Regards Thorkil On Tuesday 30 May 2006 15:10, Sebastian Sylvan wrote:
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.
On 5/30/06, Thorkil Naur
Hello,
Both my Hugs and my GHCi report a type error when presented with this. A possible repaired version looks like this:
calc :: String -> Float calc = g . 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 g [r] = r
Not as small, but still quite nice.
..or you could just have it return [Float], maybe that's the intention (you could do several computations). Or throw in a "head" in there instead of defining a new function. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
Hello Nuno, Monday, May 29, 2006, 10:53:30 PM, you wrote:
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
to be exact, tree represents an expression itself while you can get _linear_ text from it in polish postfix/prefix or ordinary infix notation by applying various visiting strategies -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (4)
-
Bulat Ziganshin -
Nuno Santos -
Sebastian Sylvan -
Thorkil Naur