| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Генерация выражений со скобками |
| Автор: disputant 22.1.2012, 15:13 |
| Если взять строку цифр и попытаться сгенерировать все возможные выражения с +-*/, не меняя последовательность цифр - например, из 12345 получать 1+23-4*5 - это делается буквально за полчаса, а то и быстрее  - просто берем всевозможные кортежи из пустого знакоместа и символов и распихиваем между цифрами. Но как поступить, если разрешены скобки? Что-то никаких идей, невзирая на наличие, например, у Кнута алгоритма генерации всех корректных расстановок n пар скобок. Само собой, выраждения должны быть правильные, неплохо еще и с допустимыми унарными - и +...Что подскажете? |
| Автор: _Y_ 22.1.2012, 21:53 |
| Расставляем скобки на все возможные места. Проверяем какие варианты избыточны и их отбрасываем. Например, в выражениях (1+2)+3, 1+(2+3) и (1+2+3) скобки никакой информации не несут - они избыточны. Проверка простая. Считаем полученное выражение со скобками и без скобок. Если результаты совпадают (1+2)+3=1+2+3 значит скобки избыточны. |
| Автор: disputant 22.1.2012, 21:55 | ||
А вариант (1+((2+3)+4)+5) - это как генерировать? скобки-то не одни могут быть... |
| Автор: _Y_ 23.1.2012, 10:23 | ||
Думаю, если выражения не очень уж длинные, можно просто пробовать все варианты расстановки скобок. Чтобы не делать совсем уж обезьянью работу, надо задать условие, что новая пара скобок вставляется только так, чтобы внутри нее (или снаружи - не важно) оказалось равное число открывающих и закрывающих скобок. Ну и, естественно, открывающая скобка ставится только перед числом или другой открывающей скобкой, а закрывающая только после числа или другой закрывающей скобки. |
| Автор: Silent 23.1.2012, 14:08 |
| зачем вам скобки генерировать? генерируйте выражения в польской нотации, и потом подходящие "оформите" со скобками, имхо, мороки меньше +12*3+*45*6 -> ((1+2)*3+4*5)*6 |
| Автор: disputant 23.1.2012, 16:04 | ||
Спасибо за идею! Хотя надо еще разобраться с оператором конкатенации (назовем его так), чтоб получать двузначные и длиннее числа... |
| Автор: disputant 30.1.2012, 09:19 |
| Дело уже прошлое, но наиболее эффективным окказался способ генерации бинарных деревьев (см. Кнута ), с последующей трактовкой их как синтаксических. |