Пусть имеется файл, содержащий алгебраическое...

Задание:

Пусть имеется файл, содержащий алгебраическое выражение (до 250 символом без пробелов, 50 чисел в диапазоне от 0 до 10). Выражение состоит из неотрицательных вещественных чисел и знаков операций «+», «-» и «*». Задача: расставить в выражении скобки, чтобы его значение стало максимальным. Результат необходимо записать в файл, в котором в первой строке должно быть записано полученное выражение (со скобками), второй строкой – результат вычисления выражения.

Решение:

Пусть задано некоторое алгебраическое выражение, содержащее N чисел. Рассмотрим кусок этого выражения, расположенный между i-м и j-м его числами включительно (1 ≤ i ≤ j ≤ N). Пусть Max(i, j) обозначает максимально возможное после расстановки скобок значение этого куска, а Min(i, j) – минимально возможное. Эти числа следует вычислять парами в порядке увеличения длин кусков j-i+1. Для всех i от 1 до N значения Max(i, i) и Min(i, i) совпадают и равны i-му числу выражения. При i < j число Max(i, j) вычисляем следующим образом. Перебираем все значения k, такие что i ≤ k < j, и каждый раз предполагаем, что при вычислении значения рассматриваемого куска самой последней выполняется операция, записанная между числами с номерами k и k+1. Если это, к примеру, операция вычитания, то чтобы максимизировать значение части выражения от iго числа до j-го, мы должны взять максимальное значение куска от i-го числа до k-го (которое уже вычислено) и вычесть из него минимальное значение куска от (k+1)-го числа до j-го (которое также уже вычислено). Из значений, полученных при анализе различных k, выбираем максимальное. Другие операции и вычисление Min(i, j) рассматриваются аналогично.