Здравствуйте!
Который день не могу родить решение переборной задачи.
Суть ее такова: есть числа от 1 до 5 (пока что), есть арифметические знаки — "+", "-", "*" и скобочки "(", ")".
Нужно сгенерировать всевозможные комбинации расстановки скобочек и знаков, т.е. к примеру (1 + (2 — (3 * (4 + 5)))) или (1+((2*3)-(4+5))) — да, вариантов здесь множество.
Для пяти цифр, например, это количество K = 14 всех бинарных деревьев разбора выражения умноженные на количество размещений с повторениями трех знаков по четырем местам (между 1 и 5 четыре арифм. операции). Итого, получаем 14*3^4 = 1134.
Прошу помощи в генерации всевозможных пар скобок, которые будут являться бинарными деревьями со арифметическими операциями в узлах и цифрами в листьях.
13.11.11 13:04: Перенесено из 'Этюды для программистов'
Здравствуйте, pigman, Вы писали:
P>Прошу помощи в генерации всевозможных пар скобок, которые будут являться бинарными деревьями со арифметическими операциями в узлах и цифрами в листьях.
Задача решается с помощью рекурсии.
Рассмотрим список значений, например от [1,2,3,4,5]. Разобьем список на две части (левую и правую), например [1,2] и [3,4,5]. Для каждого подсписка сформируем все возможные выражения. Затем объединим все полученные выражения из одного списка со всеми выражениями другого списка, вставляя между ними какой-нибудь знак операции. Выполняя такую операцию для различных разбиений начального списка, получим все возможные выражения.
Надеюсь, что это не учебная задача (по-моему haskell в России не изучают в ВУЗах), поэтому выложу полный код. Если задача учебная, сюда заглядывать запрещено
| | Код |
| | import Data.List
-- Все возможные бинарные операции (для удобства, представим как Char)
type Operation = Char
operations :: [Operation]
operations = ['+', '-', '*']
-- Делим список на две части (левую и правую) всеми возможными способами, например
-- splits [1,2,3,4] = [
-- ([1], [2,3,4]),
-- ([1,2], [3,4]),
-- ([1,2,3],[4])
-- ]
splits :: Eq a => [a] -> [([a], [a])]
splits xs = [ (as,bs) | (as,bs) <- zip (inits xs) (tails xs), as /= [], bs /= [] ]
-- Наше дерево выражений, в котором будут храниться значения и операции между ними
data Node =
Value Int -- лист дерева с некоторым числовым значением
| Op Operation Node Node -- узел дерева: операция и два поддерева
deriving Show
-----
-- Генерация всех выражений из заданного списка значений.
-- На выходе получаем список всех деревьев
gen :: [Int] -> [Node]
-- Нет входных значений, значит нет и выражений
gen [] = []
-- Из одного значения, можем сформировать только одно выражение (лист дерева)
gen [x] = [Value x]
-- Если значений несколько, то можем сформировать несколько узлов. Для этого:
-- 1. Разобъем список значений на две части (левую и правую)
-- 2. Для левой и правой части сформируем рекурсивно выражения
-- 3. Склеим выражение левой и правой части, вставляя между ними операции
gen xs = [ Op op leftNode rightNode |
(leftList,rightList) <- splits xs,
leftNode <- gen leftList,
rightNode <- gen rightList,
op <- operations ]
-----
-- Вывод дерева в скобочной нотации
showNode :: Node -> String
-- Лист дерева: просто выводим значение
showNode (Value a) = show a
-- Узел дерева: выводим левое поддерево, знак между ними, правое поддерево
-- Все выражение заключаем в скобки
showNode (Op op left right) = "(" ++ showNode left ++ [op] ++ showNode right ++ ")"
|
| | |
| | Результат |
| | mapM_ (putStrLn.showNode) $ gen [1..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)
((1*2)*3)
— — — — — — — — — — — — — — — — — — — — —
length $ gen [1..5]
1134
— — — — — — — — — — — — — — — — — — — — -
|
| | |
Вообще, такая постановка задачи не совсем правильна. Например выражения (1+(2+3)) и ((1+2)+3) в задаче считаются различными, хотя по сути являются одинаковыми.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
