VPF::Генерация деревьев на Haskell - Форум программистов

pigmanspb

Дата 10.11.2011, 03:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 20.4.2011

Репутация: нет
Всего: нет

Здравствуйте!

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

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

Прошу помощи в генерации всевозможных выражений с парами скобок, которые будут являться бинарными деревьями со арифметическими операциями в узлах и цифрами в листьях.

Это сообщение отредактировал(а) pigmanspb - 10.11.2011, 03:57

Void

Дата 10.11.2011, 10:27 (ссылка)

(голосов:1)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Например так, на 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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Функциональные языки: общие вопросы \| Следующая тема »