[Haskell-beginners] parse String -> Expression

[Daniel Fischer]

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.?