Рубрики

Распечатайте все возможные выражения, которые соответствуют цели

Данная строка содержит только цифры от 0 до 9 и целочисленное значение target . Узнайте, сколько выражения можно оценить которые целевой двоичный оператор +, — и * в данной строке цифр.

Input : "123",  Target : 6
Output : {“1+2+3”, “1*2*3”}

Input : “125”, Target : 7
Output : {“1*2+5”, “12-5”}

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

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

Смотрите пример ниже для лучшего понимания —

Input is 125, suppose we have reached till 1+2 now,
Input = “125”, current expression = “1+2”, 
position = 2, current val = 3, last = 2

Now when we go for multiplication, we need last 
value for evaluation as follows:

current val = current val - last + last * current val

First we subtract last and then add last * current 
val for evaluation, new last is last * current val.
current val = 3 – 2 + 2*5 = 11
last = 2*5 = 10 

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

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

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

using namespace std;

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

void getExprUtil(vector<string>& res, string curExp,

                 string input, int target, int pos,

                 int curVal, int last)

{

    // истина, если весь ввод обрабатывается с некоторыми

    // операторы

    if (pos == input.length())

    {

        // если текущее значение равно цели

        // тогда только добавить к окончательному решению

        // если вопрос: все возможные o / p, то просто

        // push_back без условия

        if (curVal == target)

            res.push_back(curExp);

        return;

    }

  

    // цикл для установки оператора на все позиции

    for (int i = pos; i < input.length(); i++)

    {

        // игнорируем регистр, который начинается с 0, поскольку они

        // бесполезны для оценки

        if (i != pos && input[pos] == '0')

            break;

  

        // принять участие от pos до i

        string part = input.substr(pos, i + 1 - pos);

  

        // принять числовое значение части

        int cur = atoi(part.c_str());

  

        // если pos равно 0, просто отправьте числовое значение

        // для следующего перевоспитания

        if (pos == 0)

            getExprUtil(res, curExp + part, input,

                     target, i + 1, cur, cur);

  

  

        // попробуем все заданные бинарные операторы для оценки

        else

        {

            getExprUtil(res, curExp + "+" + part, input,

                     target, i + 1, curVal + cur, cur);

            getExprUtil(res, curExp + "-" + part, input,

                     target, i + 1, curVal - cur, -cur);

            getExprUtil(res, curExp + "*" + part, input,

                     target, i + 1, curVal - last + last * cur,

                     last * cur);

        }

    }

}

  
// Метод ниже возвращает все возможные выражения
// оцениваем до цели

vector<string> getExprs(string input, int target)

{

    vector<string> res;

    getExprUtil(res, "", input, target, 0, 0, 0);

    return res;

}

  
// метод для печати результата

void printResult(vector<string> res)

{

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

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

    cout << endl;

}

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

int main()

{

    string input = "123";

    int target = 6;

    vector<string> res = getExprs(input, target);

    printResult(res);

  

    input = "125";

    target = 7;

    res = getExprs(input, target);

    printResult(res);

    return 0;

}

Выход:

1+2+3 1*2*3 
1*2+5 12-5

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

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

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

Распечатайте все возможные выражения, которые соответствуют цели

0.00 (0%) 0 votes