2

我在执行 readsPrec 以解析以下数据结构的输入时遇到问题：

data Term = Monom Int Int
          | Addition Term Term
          | Subtraction Term Term
          | Multiplication Term Term
          | Division Term Term

我已经实现了一个 show 实例，它使 monom 看起来像：

let k  = Monom 2 3
Main.show k

返回：

(2x^3)

和

let m = Addition k k
Main.show m

返回：

(2x^3)+(2x^3)

与此同时，我要坐 5 个小时来完成这项任务，我真的不知道如何处理它。我的第一种方法如下所示：

instance Read Term where
  readsPrec _ inp = let[(a,b)] = lex inp in
   case a of
   "x" -> readsPrec 0 b
   "^" -> [(Monom 1 (read b::Int), "")]
   c  -> let[(d, "")] = readsPrec 0 b in
     [(Monom (read c::Int) ((\(Monom x y) -> y) d), "")]

起初我感到非常高兴，直到我注意到这段代码除了 Monom 之外其他任何东西都不起作用。有人有更好的方法吗？

4

1 回答 1

2

是的。这可能看起来有点过于强大，但使用Parsec之类的解析器组合库可以让您整齐地编写代码。例如

import Text.ParserCombinators.Parsec
import Data.Maybe

monom, term :: Parser Term
operations :: [(Char,(Term -> Term -> Term))] -> Parser Term

int :: Parser Int
int = fmap read $ many1 digit

monom = do
         coef <- int
         string "x^"
         power <- int
         return $ Monom coef power


operations ops = do
                   a <- term
                   c <- choice . map (char . fst) $ ops
                   b <- term
                   return $ (fromJust $ lookup c ops) a b

term = do
        char '('
        x <- monom <|> (operations [('+', Addition), ('-', Subtraction), ('*', Multiplication), ('/', Division)])
        char ')'
        return x

term' = do 
         x <- term
         eof 
         return x

readTerm :: String -> Term
readTerm string = case parse term' "" string  of
                        Left err -> error . show $ err
                        Right term -> term

作为解释，monom解析类似2x^3（不带括号），operations获取元组列表并解析 aterm后跟一个操作字符，然后是另一个term，然后使用适当的数据构造函数生成正确的实例（fromJust $ lookup c ops行）。

term解析器解析一个或一个操作，用monom括号括起来。term'解析整个字符串（即确保解析器运行到字符串的末尾）。readTerm只是解析器的“更清洁”版本。

一些例子：

> readTerm "(2x^3)"
Monom 2 3
> readTerm "((2x^3)+(2x^3))"
Addition (Monom 2 3) (Monom 2 3)
> readTerm "(((2x^3)+(2x^3))*(2x^3))"
Multiplication (Addition (Monom 2 3) (Monom 2 3)) (Monom 2 3)

以上是一个非常基本的版本，可以很容易地扩展为（例如）使coef术语可选，以便x^2解析为Monom 1 2，或使power术语可选以便2x解析为Monom 2 1。（这个option函数对这个特定的修改非常有用，只增加了 1 或 2 行。）

（注意。这可能会更有效和优雅地写成应用风格，例如

import Control.Applicative

monom = Monom <$> int <* string "x^" <*> int

但这在进行修改时可能会有点笨拙。）

于 2012-10-22T10:08:42.617 回答