Выведите все возможные выражения, которые оценивают цель

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

Ввод: «123», цель: 6
Вывод: {«1 + 2 + 3», «1 * 2 * 3»}

Ввод: «125», цель: 7
Вывод: {«1 * 2 + 5», «12-5»}

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

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

См. Ниже пример для лучшего понимания -

Ввод 125, предположим, что мы дошли до 1 + 2,
Ввод = «125», текущее выражение = «1 + 2», 
позиция = 2, текущее значение = 3, последнее = 2

Теперь, когда мы переходим к умножению, нам нужна последняя 
значение для оценки следующим образом:

текущее значение = текущее значение - последнее + последнее * текущее значение

Сначала мы вычитаем последнее, а затем добавляем последний * текущий 
val для оценки, new last is last * current val.
текущий val = 3-2 + 2 * 5 = 11
последняя = 2 * 5 = 10 

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

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

Выход:

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

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

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.