Wataru

Самое надежное - распарсить выражение, построить Абстрактное Синтаксическое Дерево (это бинарное дерево, где вершина - операция, а два ребенка - операнды, которые могут быть или числом, или выражением).

Потом его надо вывести, вставляя только необходимые скобки. Надо порисовать на бумаге кучу случаев и аккуратно их разобрать.

Так, если вершина "+", то скобки ставить вообще не надо. Если вершина "*", то надо ставить скобки вокруг ребенка, если там операция "+" или "-". Если вершина "-", то надо ставить скобки справа, если там "+" или "-". Если вершина "/", то надо ставить скобки вокруг левого сына, если там "+" или "-". Вокруг правого сына скобки надо ставить если не число. Подумайте аккуратно, может я какие-то правила упустил.

Это удобно реализовывать рекурсивной функцией. Она проверяет, надо ли ставить скобки вокруг левого сына и выводит его рекурсивно, потом операцию, потом также правого ребенка.

Парсинг - очень заезженная тема. Гуглите. Самый простой алгоритм - квадртатичный - проходитесь по строке и ищите самую левую операцию с самым большим приоритетом вне скобок (ведя счетчик открытых скобок). Если такой нет, то можно опустить скобки по краям. Если их нет, то это число (или перменная). Если нашли операцию, то рекурсивно разбирайте две подстроки слева и справа.

Вам же минимальный по объему паралеллипипед нужен? Это довольно сложная задача. Даже на плоскости искать прямоугольник не очень приятно.

Кажется, есть эффективное решение через численную оптимизацию и троичный поиск.

Введем функцию f(a,b) - минимальный объем параллелипипеда, повернутого на угол a вдоль оси oz и потом угол b вдоль ox. Ну или это эйлеровы углы, если хотите.

Вам надо найти минимум этой функции. Утверждение: если зафиксировать a, то двигая b функция будет переодическая с двумя экстремумами. Ну, потому что поворот на 90 градусов взвращает все как было, только оси местами меняются. Значит, на ней можно что-то вроде тернарного поиска запускать (об этом дальше).

Если же ввести функцию g(a) =Min_b(f(a,b)), то она, похоже будет такая же. По ней тоже можно такой же поиск запустить.

Итого, 2 вложенных тернарных поиска, в внутри легче все точки повернуть на -b и -a градусов и потом взять обрамляющий параллелипипед, параллельный осям координат (min/max по трем координатам за 1 проход).

В тернарном поиске делим отрезок всех углов на 3 части, считаем значение функции в двух промежуточных и крайних точках. Дальше придется повозиться со случаями, их много (12), Функция может сначала иметь максимум, потом минимум, или наоборот. И 6 вариантов, как 2 промежуточные точки лягут на 3 отрезка (возрастание,убываниние, возрастание или убывание, возрастание, убывание). Тут надо их все аккуратно нарисовать, подумать, какие соотношения четырех точек позволяют выкинуть один из трех отрезков между точками.

Возможно, придется вообще считать производные (изменять чуть-чуть угол, считать функцию и смотреть, как она поменялась). Тогда будет сильно проще решить, какой из отрезков выкинуть. Ну или тогда можно метод Ньютона применять (считая вторую производную функции численно).

Это будет что-то вроде O(n log^2 n).

Или можно просто случайным образом или с малым шагом перебирать разные углы поворота. Поворачивать все точки и искать параллельный осям координат параллелипипед (просто беря min/max по трем координатам). Для 800 точек можно 10000 углов перебрать и это займет лишь 100мс на современном железе.

Это сильно проще в реализации и, хоть и не найдет самый оптимальный параллелипипед, на глаз будет сложно это заметить.

Edit: вообще, кажется, там 3 угла, а не 2. Ну появляется еще третья функция t(a,b,c). и лишний Log n в сложности. Перебирать углы становится еще хуже, но все еще возмоно.

Вообще, вот алгоритм для произвольных слов: https://e-maxx.ru/algo/longest_increasing_subseq_log

Его, наверно, можно ускорить для работы с повторяющимеся строками через возведение матриц в степень, но будет муторно.

Какие у вас там ограничения: длины строк и количество повторений?

Вот эти побитовые сдвиги работли бы, если бы вы хранили число в двоичной системе счисления. Допустим, по 16 бит в каждом int. В таком виде вычисления побыстрее будут немного, но при выводе надо переводить число в 10-ую систему счисления. Судя по примеру ответа, вы храните по 3 десятичных знака в каждой ячейке. Т.е. у вас основание системы счисления 1000. И тут нужны сдвиги не битовые, а тысячные (которых не существует).

Вообще, основной цикл умножения должен быть примерно такой:

for (i = 0; i < len1; ++i)
  for (j = 0; j < len2; ++j) 
    c[i+j] += a[i]*b[j];

И потом надо сделать все переносы. Вот тут и происходят сдвиг на i позиций (в системе счисления 1000) - это то самое +i в индексе у массива результата. И вместо выполнения прибавления, когда бит равен 1, тут происходит умножение на a[i]. В битовом случае оно как раз вырождается в умножение на 1 или 0 - прибавление или пропуск прибавления.

Это работает даже если вы в массивах a,b храните по несколько бит в каждой ячейке, или даже десятичных знаков. Это просто умножение в столбик в произвольной системе счисления.

Правда, тут проблема, что вот такое вот умножение, если вы храните по 32 бита, оно переполнится, и ответ надо в 64-битном типе получать. И даже если вы храните по 16 бит, то сумма может переполниться из-за большого количества слагаемых. Ну это решается выполнением переноса сразу же:

const int BASE = 1000; // База системы счисления. Оно же максимальное число в ячейке +1.
for (i = 0; i < len1; ++i) {
  int carry = 0;
  for (j = 0; j < len2; ++j) {
    carry += c[i+j] + a[i]*b[j];
    c[i+j] = carry % BASE; 
    carry /= BASE;
  }
  int i = len1+len2-1;
  while (carry > 0) {
    carry += c[i];
    c[i] = carry % BASE;
    carry /= BASE;
    ++i;
  }
}

Линейная. O(N+M). Ибо там цикл по i от 0 до startMedianIndex и вся остальная мишура на i вообще никак не влияет. Больше циклов в программе нет. Не понимаю, что тут может быть непонятного.