Рубрики

Все способы добавить скобки для оценки

Дана строка, представляющая выражение, составляющее числа, и только двоичные операторы +, — и *. Нам нужно заключить в скобки выражение всеми возможными способами и вернуть все вычисленные значения.

Input : expr = “3-2-1”
Output : {0, 2}
((3-2)-1) = 0 
(3-(2-1)) = 2

Input : expr = "5*4-3*2"
Output : {-10, 10, 14, 10, 34}
(5*(4-(3*2))) = -10
(5*((4-3)*2)) = 10
((5*4)-(3*2)) = 14
((5*(4-3))*2) = 10
(((5*4)-3)*2) = 34

Мы можем решить эту проблему, заключив в скобки все возможные допустимые подстроки выражения и затем оценив их, но, как мы видим, это потребует решения множества повторяющихся подзадач, чтобы спасти себя, мы можем следовать подходу динамического программирования.
Мы сохраняем результат для каждой подстроки в карте, и если строка в рекурсии уже решена, мы возвращаем результат из карты вместо того, чтобы решать это снова.
Ниже код запускает цикл в строке, и если в любой момент символ является оператором, мы делим входные данные оттуда, рекурсивно решаем каждую часть, а затем объединяем результат всеми возможными способами.
Смотрите использование функции c_str (), эта функция преобразует строку C ++ в массив C char, эта функция используется в приведенном ниже коде, потому что функция atoi () ожидает символьный массив в качестве аргумента, а не строки. Он преобразует массив символов в число.

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

using namespace std;

  
// проверяет метод, символ оператор или нет

bool isOperator(char op)

{

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

}

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

vector<int> possibleResultUtil(string input,

            map< string, vector<int> > memo)

{

    // Если уже рассчитано, то возвращаем из памятки

    if (memo.find(input) != memo.end())

        return memo[input];

  

    vector<int> res;

    for (int i = 0; i < input.size(); i++)

    {

        if (isOperator(input[i]))

        {

            // Если символ является оператором, то разделить и

            // вычислить рекурсивно

            vector<int> resPre =

              possibleResultUtil(input.substr(0, i), memo);

            vector<int> resSuf =

              possibleResultUtil(input.substr(i + 1), memo);

  

            // Объединяем все возможные комбинации

            for (int j = 0; j < resPre.size(); j++)

            {

                for (int k = 0; k < resSuf.size(); k++)

                {

                    if (input[i] == '+')

                        res.push_back(resPre[j] + resSuf[k]);

                    else if (input[i] == '-')

                        res.push_back(resPre[j] - resSuf[k]);

                    else if (input[i] == '*')

                        res.push_back(resPre[j] * resSuf[k]);

                }

            }

        }

    }

  

    // если вход содержит только номер, сохраните

    // в вектор рез

    if (res.size() == 0)

        res.push_back(atoi(input.c_str()));

  

    // Сохраняем в памятке, чтобы входная строка не

    // обрабатывается повторно

    memo[input] = res;

    return res;

}

  
// метод для возврата всех возможных выходных данных
// из входного выражения

vector<int> possibleResult(string input)

{

    map< string, vector<int> > memo;

    return possibleResultUtil(input, memo);

}

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

int main()

{

    string input = "5*4-3*2";

    vector<int> res = possibleResult(input);

  

    for (int i = 0; i < res.size(); i++)

        cout << res[i] << " ";

    return 0;

}

Выход:

-10 10 14 10 34 

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

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

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

Все способы добавить скобки для оценки

0.00 (0%) 0 votes