1

任务是在n -number A 中找到(n-1) 个运算符 (+,-,*) 的所有可能组合，因此表达式的结果等于数字 B。表达式从左到右计算。例如：

We have number A=123 and B=5 : 1*2+3=5

我猜这个任务可能与波兰符号和解析器的一些使用有关。所以它就像：我得到数字 123，将其设为字符串“3 2 1”，然后尝试所有可能的运算符组合，例如：“3 2 1 + +”“3 2 1 - -”“3 2 1 * *" "3 2 1 * -" 等并检查它是否等于 5。但问题是我真的不明白如何正确找到所有组合。我还编写了一个函数，该函数使数字字符串成为计算表达式的函数，例如“3 2 1 * +”。

exprCounting :: String -> Integer
exprCounting = head . foldl stackAnalyzing [] . words 
  where
    stackAnalyzing (x:y:ss) "+" = (x+y):ss
    stackAnalyzing (x:y:ss) "-" = (y-x):ss
    stackAnalyzing (x:y:ss) "*" = (x*y):ss
    stackAnalyzing   ss  number = read number : ss

toWordString :: Integer -> String               
toWordString = addSpace . show
  where
    addSpace [] = []
    addSpace (x:xs) = [x] ++ " " ++ addSpace xs

所以任何人都可以给我关于解决这个任务的方法或我应该使用什么工具的建议。

4

1 回答 1

2

所以你想要这样的东西

import Control.Monad
data Op = Plus
        | Sub
        | Mult
   deriving(Eq, Show)
denote :: Op -> (Integer -> Integer -> Integer)
denote Plus = (+)
denote Sub  = (-)
denote Mult = (*)

combos :: [Integer] -> Integer -> [[Op]]

所以combos [1, 2, 3] 5 == [[Mult, Plus]]

使用它的一个简单方法是 list monad。

eval :: [Integer] -> [Op] -> Integer
eval (n1:n2:ns) (o:os) = eval (denote o n1 n2 : ns) os
eval [n1]       []     = n1
eval  _         _      = error "eval: Length mismatch"
-- Or, with folds
eval' ns os = case foldl step ns os of
  [n] -> n
  _ -> error "eval: Length mismatch"
  where step (n1 : n2 : ns) o  = denote o n1 n2 : ns

combos ns target = filter ( (==target) . eval nums) os
  where os = replicateM (length ns -1) [Plus, Sub, Mult]

replicateMlength ns - 1将选择返回由组成的所有可能长度列表的列表Plus, Sub, Mult。然后我们只是测试它们，看看它们是否真的等于正确的值。这不是非常快，但很容易理解。

所以我们分别生成这个运算符列表。现在使用它很容易生成 RPN，因为这看起来像家庭作业，我会把这部分留给你 :)

于 2013-11-11T15:05:09.787 回答