8.8. Задача «Расставить скобки»

Для выражения существуют два способа расставить скобки: и .

✒️ Упражнение:
Для максимального значения нужно поставить в скобки выражение .

• Входные данные: Ввод содержит только строку длиной для некого с символами . Каждый символ на чётной позиции — это цифра (то есть целое число от 0 до 9), а на нечетной позиции — одна из трёх операций из .
• Выходные данные: Максимальное значение данного арифметического выражения из всех возможных порядков арифметических операций.
• Ограничения: — таким образом, строка содержит максимум символов.

Пример 1

Ввод	Вывод
5-8+7*4-8+9	200

Рассмотрим решение задачи. Каждая из пяти операций в выражении

может быть последней — внешней. Рассмотрим случай, в котором последняя операция — «», то есть умножение. В этой ситуации нам необходимо поместить два подвыражения в скобки

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

На основании этих значений мы заключаем, что общее значение произведения составляет .

Предположим, что вводный набор данных имеет форму

где каждая — это цифра, а каждая — базовая арифметическая операция. Сказанное выше предполагает, что мы вычисляем минимальное и максимальное значение каждого подвыражения в форме

где . Пусть и — минимальное и максимальное значение соответственно. Тогда

Базовый случай — это :

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

Тогда наше рекуррентное соотношение говорит о том, что дерево состоит из корня и двух поддеревьев. Для нахождения оптимальной формы дерева мы анализируем все возможные корни (за это отвечает параметр ), а затем составляем дерево из двух оптимальных поддеревьев.

Как обычно, сделать из рекуррентного соотношения рекурсивный алгоритм довольно просто. Рекурсивная процедура берёт индексы и в качестве параметров и использует их для вычисления минимального и максимального значения подвыражения . Перед тем, как начать вычисления, проверяется, не сохранены ли уже эти значения в , где — это ассоциативный массив, хранящий уже вычисленные результаты. Если запись отсутствует, рекурсивная процедура вычисляет два значения, используя рекуррентное соотношение, сохраняет их в таблицу и выдаёт их. Конечный ответ соответствует и . Время выполнения составляет : есть возможных пар , для каждой из которых рекурсивная процедура проверяет возможные значения для .

Для переведения рекурсивного алгоритма в итерационный используются двумерные таблицы и , в которых хранятся минимальные и максимальные значения всех подвыражений. Заполняя данные таблицы, нам нужно убедиться, что к окончанию вычислений оптимальных значений для оптимальные значения и для всех уже вычислены. Один из способов сделать это — перечислить все пары в порядке возрастания значения . Чтобы это сделать, в псевдокоде ниже используется параметр .

MaxValue(d[0],op[0],d[1],op[1],…d[n]):
    mins, maxs = 2d-arrays of size (n+1)×(n+1)
    fill mins with +infinity, fill maxs with -infinity
    for i from 0 to n:
        mins[i][i]=d[i], maxs[i][i]←d[i]​
    for s from 1 to n:
        for l from 1 to n-s:
            r = l+s
            for m from l to r-1:
                a = mins[l][m] op[m] mins[m+1][r]
                b = mins[l][m] op[m] maxs[m+1][r]
                c = maxs[l][m] op[m] mins[m+1][r]
                d = maxs[l][m] op[m] maxs[m+1][r]
                mins[l][r] = min(mins[l][r],a,b,c,d)
                maxs[l][r] = max(maxs[l][r],a,b,c,d)
    return maxs[0][n]