On Sun, Nov 08, 2009 at 05:53:48PM +0000, John Moore wrote:

Hi, I'm trying to find a way to parseRPN (Reverse Polish Numbers) to expressions rather than to just numbers. e.g. I want the answer to be in the form

(Multiply (Val 2) (Val 3)) rather than just the answer.

You don't need to code all the parser by hand. You can use, for example, Parsec parsers. Spoilers ahead!!! If your data type is data Expr a = Multiply (Expr a) (Expr a) | Val a then you may write something like expression :: Parser a -> Parser (Expr a) expression valParser = spaces >> (mult <|> val) where expr = expression valParser mult = char "*" >> (Multiply <$> expr <*> expr) val = Val <$> valParser using Parsec for a concrete example. HTH, -- Felipe.

Am Sonntag 08 November 2009 18:53:48 schrieb John Moore:

Hi, I'm trying to find a way to parseRPN (Reverse Polish Numbers) to expressions rather than to just numbers. e.g. I want the answer to be in the form

(Multiply (Val 2) (Val 3)) rather than just the answer.

I'd suggest using something like type Stack = [Expression] parseRPN :: Parser Expression parseRPN = rpn [] parseVal :: Parser Expression parseVal = do num <- parseNumber return (Val num) rpn :: Stack -> Parser Expression rpn stack = (do char '+' case stack of (x:y:ts) -> rpn (Add x y:ts) _ -> parsecFail "BinOp requires two values on Stack") <|> (do char '*' case stack of (x:y:ts) -> rpn (Multiply x y:ts) _ -> parsecFail "BinOp requires two values on Stack") <|> ... <|> (do v <- parseVal rpn (v:stack)) <|> (do eof case stack of [x] -> return x _ -> parsecFail "No parse") -- You could also use the userstate of Parsec for the stack

Are these anyway near the steps parseRPN :: String->Expression

This is a lot more complicated then I thought.!!!

First do we have to read in a string is this (IsString)

fromString :: String -> a

Then this goes on a stack

pushStack :: a -> Stack -> Stack (Takes a value and puts in on a stack)

Later we pop it off

popStack :: Stack -> (a,Stack) -- takes the value of the stack and leaves the stack

Do we also have to define taking off the stack such as head(popstack) or fst(popstack) if we do we would probably have one for putting it onto a stack.

Do we then turn the value into an Expression.?