Тут чёткое динамическое программирование. У нас 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 +0 1. Левую единицу раскрываем через (0, 0), правую — через (1, 3): 2 = 1 +0 2 +1 (−1).
Остаётся раскрыть −1, и получаем 2 = 1 + 2 + 3 − 4.
Это можно сделать рекурсивно.
Если точный путь вычислений не нужен, ассоциативный массив превращается в множество без повторов. Не (2 → 0 1 1), а просто 2.
Во многих вариантах динамического программирования, если прямой ход не нужен, двухмерный кэш можно превратить в одномерный. Тут я не вижу способа. Написал, да понял, что ошибся.
UPD. А сложность какая? — у меня выходит 2n·n². Почти уверен, что реально цифра меньше, просто думать над этим облом.