Рубрики

Минимальные и максимальные значения выражения с * и +

Учитывая выражение, которое содержит числа и два оператора '+' и '*', нам нужно найти максимальное и минимальное значение, которое можно получить, оценивая это выражение с помощью различных круглых скобок.
Примеры:

Input  : expr = “1+2*3+4*5” 
Output : Minimum Value = 27, Maximum Value = 105 
Explanation:
Minimum evaluated value = 1 + (2*3) + (4*5) = 27
Maximum evaluated value = (1 + 2)*(3 + 4)*5 = 105

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

// C ++ программа для получения максимума и минимума
// значения выражения
#include <bits/stdc++.h>

using namespace std;

  
// Утилита для проверки наличия символа
// оператор или нет

bool isOperator(char op)

{

    return (op == '+' || op == '*');

}

  
// метод печатает минимальное и максимальное значение
// можно получить из выражения

void printMinAndMaxValueOfExp(string exp)

{

    vector<int> num;

    vector<char> opr;

    string tmp = "";

  

    // сохраняем оператор и числа в разных векторах

    for (int i = 0; i < exp.length(); i++)

    {

        if (isOperator(exp[i]))

        {

            opr.push_back(exp[i]);

            num.push_back(atoi(tmp.c_str()));

            tmp = "";

        }

        else

        {

            tmp += exp[i];

        }

    }

    // сохраняем последний номер в векторе

    num.push_back(atoi(tmp.c_str()));

  

    int len = num.size();

    int minVal[len][len];

    int maxVal[len][len];

  

    // инициализация 2D и массива minval

    for (int i = 0; i < len; i++)

    {

        for (int j = 0; j < len; j++)

        {

            minVal[i][j] = INT_MAX;

            maxVal[i][j] = 0;

  

            // инициализация главной диагонали по num значениям

            if (i == j)

                minVal[i][j] = maxVal[i][j] = num[i];

        }

    }

  

    // цикл похож на умножение цепочки матриц

    // и обновляем оба 2D массива

    for (int L = 2; L <= len; L++)

    {

        for (int i = 0; i < len - L + 1; i++)

        {

            int j = i + L - 1;

            for (int k = i; k < j; k++)

            {

                int minTmp = 0, maxTmp = 0;

  

                // если текущий оператор '+', обновляет tmp

                // переменная путем сложения

                if(opr[k] == '+')

                {

                    minTmp = minVal[i][k] + minVal[k + 1][j];

                    maxTmp = maxVal[i][k] + maxVal[k + 1][j];

                }

  

                // если текущий оператор '*', обновляет tmp

                // переменная умножением

                else if(opr[k] == '*')

                {

                    minTmp = minVal[i][k] * minVal[k + 1][j];

                    maxTmp = maxVal[i][k] * maxVal[k + 1][j];

                }

  

                // обновляем значения массива переменными tmp

                if (minTmp < minVal[i][j])

                    minVal[i][j] = minTmp;

                if (maxTmp > maxVal[i][j])

                    maxVal[i][j] = maxTmp;

            }

        }

    }

  

    // последний элемент первой строки будет хранить результат

    cout << "Minimum value : " << minVal[0][len - 1]

         << ", Maximum value : " << maxVal[0][len - 1];

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    string expression = "1+2*3+4*5";

    printMinAndMaxValueOfExp(expression);

    return 0;

}

Выход:

Minimum value : 27, Maximum value : 105

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальные и максимальные значения выражения с * и +

0.00 (0%) 0 votes