Как расставить скобки в выражении всеми возможными способами? какова сложность оптимального алгоритма?

Question

[andreys75]

Добрый день!

Есть арифметическое выражение состоящее из целых чисел, и операций +,-,*,\ к примеру 1+2-3*4. Надо найти множество всех уникальных результатов данного выражения при всевозможных расстановках скобок в выражении:
(1+2)-(3*4); (1+2-3)*4 и т.д.

я придумал 3 алгоритма, но все они имею в худшем случае O(n!). Есть ли более оптимальные алгоритмы?

Для простоты, давайте считать, что есть два массива nums и ops - чтобы не вдаваться в детали разбора выражения.

Мои решения:
Вариант 1
1. определяем рекурсивную функцию на вход которой подается два массива ops и nums и третий массив, куда будем складывать результаты
2. Если ops пустой, или ops содержит одну операцию, или ops содержит операции одного приоритета, вычисляем знаечение выражения, т.к. его результат не зависит от расстановки скобок, добавляем этот результат в массив с результатами и возвращаемся из функции.
3. Цикл по всем операциям из массива ops
4. для выбранной операции - считаем что она будет первой, выбираем соответствующие ей операнды из nums выполняем операцию
5. обновляем массив nums заменяя два операнда на результат выполнения операции и удаляя операцию из массива ops
6. рекурсивно вызываем функцию для новых массивов nums и ops меньшего размера
7. продолжаем цикл
8. в результирующем массиве удаляем стандартными функциями все дубли

Вариант 2.
1. определяем рекурсивную функцию с таким же входом как и в первом варианте
2. Если ops пустой, или ops содержит одну операцию, или ops содержит операции одного приоритета, вычисляем значение выражения, т.к. его результат не зависит от расстановки скобок, добавляем этот результат в массив с результатами и возвращаемся из функции.
3. цикл по всем операциям
4. выбранную операцию будем считать последней при вычислении
5. Формируем два подвыражения, все что стоит слева от выбранной операции и все что стоит справа
6. Рекурсивно вычисляем результат выполнения функции на 2-х подвыражениях, получаем два массива с уникальными результатами.
7. делаем декартово произведение этих массивов - выполняя для каждой пары выбранную операцию, заносим ее в результирующий массив
8. Удаляем из результирующего массива дубли

Третий вариант совсем плохой -
ставим в соответствие массиву операций массив [1...n] если n количество операций. И более менее стандартными алгоритмами получаем все возможные перестановки этого массива
потом считаем выражение с учетом последовательности выполнения операций в соответствии с очередной перестановкой.

Анализ все алгоритмы имеют сложность O(n!) но второй алгоритм, уменьшает сложность за счет того что:
1. (1+1-4+6) - такого рода подвыражения считает сразу не пытаясь расставить скобки разными вариантами
2. (1-2)-(3*4) - вычисляет один раз т.к. нам неважно что будет сосчитано в первую очередь (1-2) или (3*4). В первом алгоритме такое выражение получится и при выборе в качестве первой операции первый минут и при выборе в качестве первой операции умножения.

Буду благодарен если кто- пришлет более интересные решения или поможет доказать что второйвариант оптимальное решение.

Answer 1

[res2001]

Для вашего случая результаты выражения будут различаться от варианта без скобок, только если меняется приоритет операций. Т.е. (1+2)-(3*4) - не дает уникального результата, а (1+2-3)*4 - дает.
Итого - надо ставить закрывающую скобку перед знаком * или /, а открывающую скобку перед каждой предыдущей операцией.
Кроме того - когда расставите скобки, нужно брать выражение в скобках и рекурсивно прогонять его по алгоритму, таким образом расставите и вложенные скобки до тех пор пока внутри скобок не окажется простое выражение типа a+b, где уже ничего не поставить.

Answer 2

[Mercury13]

Тут чёткое динамическое программирование. У нас N+1 операнд, и N операций.
Создаём кэш: для всех L и R, 0<=L<=R<=N, мы храним:
• Операцию: null, +, ×, many.
• Ассоциативный массив:
•• Ключ — число (целое/рациональное/плавающее/фиксированное — с какими хотите работать).
̃•• Значение — тройка:
••• Номер операции с макс. приоритетом.
••• Значение слева (такое же число).
••• Значение справа (такое же число).
Для всех L=R кэш заполнен такой величиной:
• Операция — null.
• В массиве один элемент: ключ — операнд, значение — любая затычка.
Для кэша годится, например, матрица (N+1)×(N+1).

После этого проходимся по диагоналям нашего кэша, обрабатывая сначала L=0..N−1, R=L+1, затем L=0..N−2, R=L+2, и т.д., пока на дойдём до диагонали из одного элемента: L=0, R=N. Как именно обрабатываем?
1. Смотрим операцию, записанную в кэше (L+1, R), и L-ю операцию в выражении. Если вторая — «сложить» или «умножить», а первая — null или совпадает, записываем эту операцию в кэш на место (L, R). Иначе — пишем many.
2. Вычисляем R1: если в кэше на месте (L, R) есть какая-то операция, то L; если many — то R−1 (оптимизация по ассоциативности).
3. Проходимся по всем M=L…R1.
3.1. Двойным циклом проходимся по содержимому кэша в (L,M) и (M+1, R). Обозначим переменные u и v.
3.1.1. Записываем в кэш на место (L,R), если таковое отсутствует:
       • ключ u (+−×/) v
       • номер операции — M
       • значения слева и справа — u и v.
Рассмотрим, например 1 + 2 + 3 − 4.
(0, 0) — null; (1 → ? ? ?)
(1, 1) — null, (2 → ? ? ?)
(2, 2) — null, (3 → ? ? ?)
(3, 3) — null, (4 → ? ? ?)

UPD: Операнды у наc { 1 2 3 4 }, орерации { + + − }. Ну разумеется.

Теперь смотрим, что будет в (0, 1). В (1, 1) в кэше null, нулевая операция + — операция +. Одна итерация, R1=0.
Прокрутив эту итерацию, получаем…
(0, 1) — +; (3 → 0 1 2). Это означает: получили 3, сложив 0-м плюсом 1 и 2.
Аналогично…
(1, 2) — +; (5 → 1 2 3)
(2, 3) — many; (−1 → 2 3 4)

Вторая диагональ. (0, 2). В позиции (1, 2): в кэше +, 0-я операция +. Записываем + и прокручиваем одну итерацию, от 0 до 0. Т.е. складываем (0, 0) и (1, 2).
(0, 2) — +; (6 → 0 1 5).
Теперь (1, 3). Операция будет many; прокручиваем и получаем:
для M=1 — складываем (1, 1) и (2, 3), и получаем (1 → 1, 2, −1).
для M=2 — вычитаем (1, 2) и (3, 3), и получаем (1 → 2, 5, 4).
Если без дублей…
(1,3) — many; (1 → 1 2 -1)

Ну и, наконец, пошли (0, 3). Операция будет many…
для M=0 — складываем (0, 0) и (1, 3), и будет (2 → 0 1 1).
для M=1 — складываем (0, 1) и (2, 3), и будет (2 → 1 3 −1).
для M=2 — вычитаем (0, 2) и (3, 3), и будет (2 → 2 6 −4). Повторим, что это значит: получилось 2, из-за того, что вычли 2-м минусом 6 и −4.
Итого, без дублей, (0, 3) — many, (2 → 0 1 1).

Так «повезло», что у нас вышел один результат. Но в результате объединения может быть и множество.

А теперь вопрос: откуда мы получили 2-ку? Смотрим в (0, 3) и получаем: 2 = 1 +₀ 1. Левую единицу раскрываем через (0, 0), правую — через (1, 3): 2 = 1 +₀ 2 +₁ (−1).
Остаётся раскрыть −1, и получаем 2 = 1 + 2 + 3 − 4.
Это можно сделать рекурсивно.

Если точный путь вычислений не нужен, ассоциативный массив превращается в множество без повторов. Не (2 → 0 1 1), а просто 2.
Во многих вариантах динамического программирования, если прямой ход не нужен, двухмерный кэш можно превратить в одномерный. Тут я не вижу способа. Написал, да понял, что ошибся.

UPD. А сложность какая? — у меня выходит 2ⁿ·n². Почти уверен, что реально цифра меньше, просто думать над этим облом.