DouKaku?

import Ratio

data Item a b c = Value a | Op (b->b->b) c String

cat a b = a*10+b

ops :: [Item Integer Rational Integer]
ops = [Op cat 2 "", Op (+) 0 "+", Op (-) 0 "-", Op (*) 1 "*", Op (/) 1 "/"]

opparse ops = reverse $ foldl push [Value 1] (zip ops $ map Value [2..])

push (op'@(Op o' p' _):vs) opv@(op@(Op o p _), v)
  | p <= p' = op:v:op':vs
  | otherwise = op':push vs opv
push vs (op, v) = op:v:vs

calc vs = head $ foldl g [] vs where
  g ns (Value a) = a%1:ns
  g (a:b:ns) (Op op _ _) = op b a:ns
  g _ _ = error "invalid stack state"

showFormula ops = concat $ ["1"] ++ zipWith (\(Op _ _ n) i -> n ++ show i) ops [2..]

genops n = sequence $ replicate n ops

komachi n = filter (test 100) $ genops n where
   test sum ops = sum == (calc $ opparse ops)