4

これが私が思いついたものです：

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

calcFunction :: String -> String -> String -> String
calcFunction "+" x y = show $ read x + read y
calcFunction "-" x y = show $ read x - read y
calcFunction "*" x y = show $ read x * read y
calcFunction "/" x y = show $ read x / read y
calcFunction op x y = error $ "Unknown operator: " ++ op ++ "."

isOperator :: String -> Bool
isOperator "+" = True
isOperator "-" = True
isOperator "*" = True
isOperator "/" = True
isOperator _ = False

solveRPN :: (Read a, Integral a) => [String] -> [String] -> a
solveRPN [] (x:[]) = read x
solveRPN [] (x:y:xs) = solveRPN (x:y:[]) xs
solveRPN stack (x:xs)
         | isOperator x =
           let z = calcFunction x (last (init stack)) (last stack)
           in solveRPN (init (init stack)) (z:xs)
         | otherwise = solveRPN (stack ++ [x]) xs
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show stack

それが機能している間...

*Main>  solveRPNWrapper "10 4 3 + 2 *  -"
-4

...これは慣用的なものではなく（確かに演算子ビットの重複が多く、読み取り/表示は冗長に見える）、制約も台無しになっている可能性があります。

4

5 に答える 5

9

  1. スタックのタイプを に変更しますIntegral a => [a]。readこれにより、あらゆる場所でandが不要になるだけでなくshow、元のコードに隠れていた型エラーが明らかになります。/整数除算 ( ) の代わりに分数除算 ( ) を使用していdivました。

  2. スタックを反転します。リストは前面から操作する方が簡単なので、それをスタックのトップとして使用してください。lastこれにより、スタックでパターン マッチングを使用して、とをいじる代わりに、スタックの一番上から要素を簡単に選択することもできますinit。これもより効率的です。

  3. 演算子にはルックアップ テーブルを使用します。これにより、重複がさらに削減され、対応する Haskell 関数 ( 、 など) をテーブルに直接格納することができ+ますdiv。

これは、これらの変更を行った後の結果です。

solveRPNWrapper :: (Read a, Integral a) => String -> a
solveRPNWrapper str = solveRPN [] $ words str

solveRPN :: (Read a, Integral a) => [a] -> [String] -> a
solveRPN [result] [] = result
solveRPN (y : x : stack) (token : tokens)
  | Just f <- lookup token operators = solveRPN (f x y : stack) tokens
solveRPN stack (token : tokens) = solveRPN (read token : stack) tokens
solveRPN stack [] = error $ "Badly formatted expression: Stack contains " ++ show (reverse stack)

operators :: Integral a => [(String, a -> a -> a)]
operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

再帰の代わりに折り畳みを使用することもできますが、その場合はラッパーにエラー処理を追加する必要があります。Integerの代わりにjust を使用することも検討しますがIntegral a => a、それは型シグネチャを変更するだけの問題です。

堅牢性のために、 を使用する代わりにEitherorのような純粋な形式のエラー処理を使用し、不正な形式の入力を処理する代わりにを使用することもおそらく良い考えです。Maybeerrorreadsread

于 2012-04-17T09:29:52.600 に答える
6

あなたのコードを改善するために、他の人はすでにほとんどすべてをあなたに伝えました。本書Learn You a Haskell , Functioanlly Solving Problemsに非常にうまく書かれた章があることを付け加えたいと思いますfoldl.

于 2012-04-17T10:12:08.613 に答える
5

あなたが定義する場合

data Token a = Literal a
             | Operator (a -> a -> a)

適当に書いて

parseToken :: String -> Token a

solveRPNこの署名を使用するように書き直します

solveRPN :: [a] -> [Token a] -> a

その後isOperator、やや些細なことになり、面倒な作業をcalcFunctionすべて回避できます。readshow

ただし、除算の問題をごまかすのはやめなければなりません:/はFractional(not Integral) 型専用です。毎回文字列との間で変換を行っているため、これまではうまくいっていなかったので、除算を行ったときに数値が分数型に変換されました。divorquotを代わりに使用するか、小数型を使用するかを決定する必要があります。

(また、parseTokenandの結果はsolveRPN内部Maybe(または型) でラップする必要があるため、例外をスローする代わりにEither失敗を示すことができます。)Nothing

于 2012-04-17T09:28:52.273 に答える
3

リストを効率的に使う（簡単）

より慣用的なものにする簡単な方法は、逆にstackすることです (これにより、真のスタックに少し似たものになります)。これにより、パターン マッチングを使用でき、リストの先頭でのアタッチ/読み取りがO(1)操作であるため、コードがより効率的になります。最後にそうしている間、O(n)すなわち：

solveRPN :: (Read a, Integral a) => [String] -> [String] -> a
solveRPN [] (x:[]) = read x
solveRPN [] (x:y:xs) = solveRPN (y:x:[]) xs -- push them on backwards
solveRPN stack@(s1:s2:rest) (x:xs) -- pattern match on stack with length >= 2
         | isOperator x =
           let z = calcFunction x s2 s1
           in solveRPN rest (z:xs)
         | otherwise = solveRPN (x:stack) xs
solveRPN stack (x:xs) -- last case: list with a single element
         | isOperator x = error "Stack too small"
         | otherwise = solveRPN (x:stack) xs

型システムを使用する (重要!)

文字列を使用して、入力スタックで可能な 2 つの型をカプセル化しています: 操作と数値。これにより、無効な入力が可能になります。慣用的な Haskell は型システムを活用して、関数が常に定義された結果を持つようにします (つまり、すべての関数が合計になるように)。 .

ADT (代数データ型) を使用して可能な操作をカプセル化Eitherし、タイプセーフな方法で操作とリテラルを区別することをお勧めします。

data Operation = Plus | Minus | Times | Divide

-- conversion function
readStackVar :: (Read a) => String -> Either Operation a
readStackVar "+" = Left Plus
readStackVar "-" = Left Minux
readStackVar "*" = Left Times
readStackVar "/" = Left Divide
readStackVar other = Right . read $ other

これにより、isOperatorうまく書くことができます (実際には不要ですが):

isOperator :: Either Operation a -> Bool
isOperator (Left _) = False
isOperator _ = True

calcFunctionはタイプセーフになり (型には がないことに注意してくださいEither)、認識されない操作の可能性はありません:

calcFunction :: (Integral a) => Operation -> a -> a -> a
calcFunction Plus = (+)
calcFunction Minus = (-)
calcFunction Times = (*)
calcFunction Divide = div -- integral division

これらを使用して書き直すことができます( where 句を使用してsolveRPN空のリストを渡す必要がなくなったことに注意してください)。solveRPN

solveRPN :: (Read a, Integral a) => [Either Operation a] -> a
solveRPN xs = go [] xs
   where
     go :: (Read a, Integral a) => [a] -> [Either Operation a] -> a
     go [] [] = error "Empty"
     go (x:xs) [] = x -- finished all the input
     go [] (x:y:xs) = go (y:x:[]) xs -- start the stack in reverse order

     go (s1:s2:rest) ((Left op):xs) = go ((calcFunction op s1 s2) : rest) xs -- operation   
     go stack ((Right x):xs) = go (x:stack) xs -- literal

LeftとRightでパターン マッチングを使用して、Either操作とリテラルを区別できることに注目してください。(さらにできる (そしてすべき) ことは、 return を作成して、 solveRPNreturnMaybe aでエラーを示し、 returnNothingで成功を示すことができるようにすることJust xです。)

これは次のように使用されます。

solveRPN . map readStackVar . words $ "1 2 + 3 *"

(警告: 私はこれを実際にテストしていないので、タイプミスや小さな論理エラーがあるかもしれません)

于 2012-04-17T09:38:29.480 に答える
0

キーと値のペアまたはキーと値のペアを使用してMap、操作を保存できます。

ops = [("+",(+)),("-",(-)),("/",(/)),("*",(*))]

calcFunction :: String -> String -> String -> String
calcFunction op x y = go $ lookup op ops where
  go (Just f) = show $ read x `f` read y
  go Nothing = error $ "Unknown operator: " ++ op ++ "."

isOperator :: String -> Bool
isOperator op = elem op $ fst $ unzip ops
于 2012-04-17T14:07:03.243 に答える