[Haskell-beginners] parse String -> Expression
Daniel Fischer
daniel.is.fischer at web.de
Sun Nov 8 14:00:10 EST 2009
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.?
More information about the Beginners
mailing list