Finding all combinations of operators in number A so that the result expression equals some number B

Question

The task is to find all possible combinations of (n-1) operators (+,-,*) in n-number A so the reslut of expression equals number B. Expression is calculated from left to right. For example:

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

I guess that this task may be connected with some usage of polish notation and Parsers. So it is smth like: I get number 123, make it string "3 2 1" and then try all possible combinations of operators with it like: "3 2 1 + +" "3 2 1 - -" "3 2 1 * *" "3 2 1 * -" etc and check if it equals 5. But problem is that I don't really understand how to find all combinations properly. Also I wrote function that makes string from number an function that calculates expression e.g. "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

So can anyone give me advices about the way to resolve this task or what instrument i should use.

Answer 1

So you want something like this

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]]

So combos [1, 2, 3] 5 == [[Mult, Plus]]

A simple way to go about using this is the 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]

replicateM will choose return a list of all possible lists of length length ns - 1 made up of Plus, Sub, Mult. Then we just test them to see if they actually equal the correct value. This isn't terribly fast, but it's quite simple to understand.

So we generate this list of operators separately. And now using this it's easy to generate the RPN, since this looks like homework, I'll leave that part to you :)