Генерация деревьев на Haskell

 
0
 
Functional languages
ava
pigmanspb | 10.11.2011, 04:41
Здравствуйте!

Который день не могу родить решение переборной задачи.
Суть ее такова: есть числа от 1 до 5 (пока что), есть арифметические знаки - "+", "-", "*" и скобочки "(", ")".
Нужно сгенерировать всевозможные комбинации расстановки скобочек и знаков, т.е. к примеру (1 + (2 - (3 * (4 + 5)))) или (1+((2*3)-(4+5))) - да, вариантов здесь множество.

Для пяти цифр, например, это количество K = 14 всех бинарных деревьев разбора выражения  умноженные на количество размещений с повторениями трех знаков по четырем местам (между 1 и 5 четыре арифм. операции). Итого, получаем 14*3^4 = 1134.

Прошу помощи в генерации всевозможных выражений с парами скобок, которые будут являться бинарными деревьями со арифметическими операциями в узлах и цифрами в листьях.
Comments (1)
ava
Void | 10.11.2011, 10:27 #
Например так, на list comprehensions с явным протягиванием состояния:
data BinOp = Plus | Minus | Mult deriving (Eq, Enum, Bounded)

instance Show BinOp where
    show Plus = "+"
    show Minus = "-"
    show Mult = "*"

data Expr = Digit Int | Op BinOp Expr Expr deriving Eq

instance Show Expr where
    show (Digit n) = show n
    show (Op op lhs rhs) = "(" ++ show op ++ " " ++ show lhs ++ " " ++ show rhs ++ ")"

generate :: Int ->        -- ^ число узлов в дереве, которое нужно сгенерировать
            Int ->        -- ^ текущая цифра
            [(Expr, Int)] -- ^ список пар (дерево, новая текущая цифра)
generate 0 _ = []
generate 1 digit = [(Digit digit, digit + 1)]
generate n digit = [(Op op lhs rhs, nextDigit) |
    op <- [minBound..maxBound],
    (sizeLeft, sizeRight) <- [(i, n - i) | i <- [1..n - 1]],
    (lhs, nextDigitLeft) <- generate sizeLeft digit,
    (rhs, nextDigit) <- generate sizeRight nextDigitLeft]

[(x, y) | x <- a, y <- b] по сути даёт декартово произведение a и b. Остальное, надеюсь, очевидно.
Для трёх листьев:
Цитата
> mapM_ print $ map (\(x, _, _) -> x) $ generate 3 1

(+ (+ 1 2) 3)

(+ (- 1 2) 3)

(+ (* 1 2) 3)

(+ 1 (+ 2 3))

(+ 1 (- 2 3))

(+ 1 (* 2 3))

(- (+ 1 2) 3)

(- (- 1 2) 3)

(- (* 1 2) 3)

(- 1 (+ 2 3))

(- 1 (- 2 3))

(- 1 (* 2 3))

(* (+ 1 2) 3)

(* (- 1 2) 3)

(* (* 1 2) 3)

(* 1 (+ 2 3))

(* 1 (- 2 3))

(* 1 (* 2 3))

Проверка:
Цитата
> length $ generate 5 1

1134

Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Void   pigmanspb
advanced
Submit