 |
|
|
 
|
|
Генерация выражений со скобками, Как сгенерировать все возможные... 
| disputant |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Если взять строку цифр и попытаться сгенерировать все возможные выражения с +-*/, не меняя последовательность цифр - например, из 12345 получать
1+23-4*5 - это делается буквально за полчаса, а то и быстрее  - просто берем всевозможные кортежи из пустого знакоместа и символов и распихиваем между цифрами. Но как поступить, если разрешены скобки? Что-то никаких идей, невзирая на наличие, например, у Кнута алгоритма генерации всех корректных расстановок n пар скобок. Само собой, выраждения должны быть правильные, неплохо еще и с допустимыми унарными - и +...Что подскажете? Это сообщение отредактировал(а) disputant - 22.1.2012, 15:14 |
|||
|
||||
Загрузка ...
| _Y_ |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
Расставляем скобки на все возможные места.
Проверяем какие варианты избыточны и их отбрасываем. Например, в выражениях (1+2)+3, 1+(2+3) и (1+2+3) скобки никакой информации не несут - они избыточны. Проверка простая. Считаем полученное выражение со скобками и без скобок. Если результаты совпадают (1+2)+3=1+2+3 значит скобки избыточны. -------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
| disputant |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
А вариант (1+((2+3)+4)+5) - это как генерировать? скобки-то не одни могут быть... |
|||
|
||||
| _Y_ |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 1651 Регистрация: 27.11.2006 Репутация: 8 Всего: 34 |
Думаю, если выражения не очень уж длинные, можно просто пробовать все варианты расстановки скобок. Чтобы не делать совсем уж обезьянью работу, надо задать условие, что новая пара скобок вставляется только так, чтобы внутри нее (или снаружи - не важно) оказалось равное число открывающих и закрывающих скобок. Ну и, естественно, открывающая скобка ставится только перед числом или другой открывающей скобкой, а закрывающая только после числа или другой закрывающей скобки. -------------------- Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:) |
|||
|
||||
| Silent |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 252 Регистрация: 3.10.2006 Репутация: 1 Всего: 9 |
зачем вам скобки генерировать? генерируйте выражения в польской нотации, и потом подходящие "оформите" со скобками, имхо, мороки меньше
+12*3+*45*6 -> ((1+2)*3+4*5)*6 |
|||
|
||||
| disputant |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Спасибо за идею! Хотя надо еще разобраться с оператором конкатенации (назовем его так), чтоб получать двузначные и длиннее числа... Это сообщение отредактировал(а) disputant - 23.1.2012, 16:06 |
|||
|
||||
| disputant |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 210 Регистрация: 28.11.2011 Репутация: 2 Всего: 3 |
Дело уже прошлое, но наиболее эффективным окказался способ генерации бинарных деревьев (см. Кнута
), с последующей трактовкой их как синтаксических. |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0472 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |