Dada una string que contiene solo dígitos del 0 al 9 y un valor entero, target . Averigüe cuántas expresiones son posibles que se evalúan como objetivo utilizando el operador binario +, – y * en una string de dígitos determinada.
Input : "123", Target : 6 Output : {“1+2+3”, “1*2*3”} Input : “125”, Target : 7 Output : {“1*2+5”, “12-5”}
Este problema se puede resolver colocando todos los operadores binarios posibles en el medio entre dos dígitos y evaluándolos y luego verificando que se evalúen como objetivo o no.
- Mientras escribimos el código recursivo, debemos mantener estas variables como argumento del método recursivo: vector de resultado, string de entrada, string de expresión actual, valor objetivo, posición hasta la que se procesa la entrada, valor evaluado actual y último valor en evaluación.
- El último valor se mantiene en recursión debido a la operación de multiplicación, mientras hacemos la multiplicación necesitamos el último valor para una evaluación correcta.
Vea el siguiente ejemplo para una mejor comprensión:
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
Otra cosa a tener en cuenta en el código a continuación es que hemos ignorado todos los números que comienzan desde 0 al imponer una condición como primera condición dentro del ciclo para que no procesemos números como 03, 05, etc.
Vea el uso de la función c_str(), esta función convierte la string C++ en una array de caracteres C, esta función se usa en el código siguiente porque la función atoi() espera una array de caracteres como argumento, no la string. Convierte una array de caracteres en un número.
C++
// C++ program to find all possible expression which // evaluate to target #include <bits/stdc++.h> using namespace std; // Utility recursive method to generate all possible // expressions void getExprUtil(vector<string>& res, string curExp, string input, int target, int pos, int curVal, int last) { // true if whole input is processed with some // operators if (pos == input.length()) { // if current value is equal to target //then only add to final solution // if question is : all possible o/p then just //push_back without condition if (curVal == target) res.push_back(curExp); return; } // loop to put operator at all positions for (int i = pos; i < input.length(); i++) { // ignoring case which start with 0 as they // are useless for evaluation if (i != pos && input[pos] == '0') break; // take part of input from pos to i string part = input.substr(pos, i + 1 - pos); // take numeric value of part int cur = atoi(part.c_str()); // if pos is 0 then just send numeric value // for next recursion if (pos == 0) getExprUtil(res, curExp + part, input, target, i + 1, cur, cur); // try all given binary operator for evaluation 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); } } } // Below method returns all possible expression // evaluating to target vector<string> getExprs(string input, int target) { vector<string> res; getExprUtil(res, "", input, target, 0, 0, 0); return res; } // method to print result void printResult(vector<string> res) { for (int i = 0; i < res.size(); i++) cout << res[i] << " "; cout << endl; } // Driver code to test above methods 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; }
Java
// Java program to find all possible expression which // evaluate to target import java.util.ArrayList; class GFG { // Utility recursive method to generate all possible // expressions static void getExprUtil(ArrayList<String> res, String curExp, String input, int target, int pos, int curVal, int last) { // true if whole input is processed with some // operators if (pos == input.length()) { // if current value is equal to target // then only add to final solution // if question is : all possible o/p then just // push_back without condition if (curVal == target) res.add(curExp); return; } // loop to put operator at all positions for (int i = pos; i < input.length(); i++) { // ignoring case which start with 0 as they // are useless for evaluation if (i != pos && input.charAt(pos) == '0') break; // take part of input from pos to i String part = input.substring(pos, i + 1); // take numeric value of part int cur = Integer.parseInt(part); // if pos is 0 then just send numeric value // for next recursion if (pos == 0) getExprUtil(res, curExp + part, input, target, i + 1, cur, cur); // try all given binary operator for evaluation 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); } } } // Below method returns all possible expression // evaluating to target static ArrayList<String> getExprs(String input, int target) { ArrayList<String> res = new ArrayList<String>(); getExprUtil(res, "", input, target, 0, 0, 0); return res; } // method to print result static void printResult(ArrayList<String> res) { for (int i = 0; i < res.size(); i++) System.out.print(res.get(i) + " "); System.out.println(); } // Driver code to test above methods public static void main(String[] args) { String input = "123"; int target = 6; ArrayList<String> res = getExprs(input, target); printResult(res); input = "125"; target = 7; res = getExprs(input, target); printResult(res); } } // This code is contributed by jainlovely450.o
Python3
# Python3 program to find all possible expression which # evaluate to target # Utility recursive method to generate all possible # expressions def getExprUtil(res, curExp, _input, target, pos, curVal, last): # true if whole input is processed with some # operators if (pos == len(_input)): # if current value is equal to target #then only add to final solution # if question is : all possible o/p then just #push_back without condition if (curVal == target): res.append(curExp) return # loop to put operator at all positions for i in range(pos,len(_input)): # ignoring case which start with 0 as they # are useless for evaluation if (i != pos and _input[pos] == '0'): break # take part of input from pos to i part = _input[pos: i + 1].strip() # take numeric value of part cur = int(part) # if pos is 0 then just send numeric value # for next recursion if (pos == 0): getExprUtil(res, curExp + part, _input, target, i + 1, cur, cur) # try all given binary operator for evaluation 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) # Below method returns all possible expression # evaluating to target def getExprs(_input, target): res=[] getExprUtil(res, "", _input, target, 0, 0, 0) return res # method to print result def printResult(res): for i in range(len(res)): print(res[i],end=" ") print() # Driver code to test above methods if __name__ == '__main__': _input = "123" target = 6 res = getExprs(_input, target) printResult(res) _input = "125" target = 7 res = getExprs(_input, target) printResult(res)
C#
// C# program to find all possible expression which // evaluate to target using System; using System.Collections.Generic; class GFG { // Utility recursive method to generate all possible expressions static void getExprUtil(List<string> res, string curExp, string input, int target, int pos, int curVal, int last) { // true if whole input is processed with some // operators if (pos == input.Length) { // if current value is equal to target //then only add to final solution // if question is : all possible o/p then just //push_back without condition if (curVal == target) res.Add(curExp); return; } // loop to put operator at all positions for (int i = pos; i < input.Length; i++) { // ignoring case which start with 0 as they // are useless for evaluation if (i != pos && input[pos] == '0') break; // take part of input from pos to i string part = input.Substring(pos, i + 1 - pos); // take numeric value of part int cur = Int32.Parse(part); // if pos is 0 then just send numeric value // for next recursion if (pos == 0) getExprUtil(res, curExp + part, input, target, i + 1, cur, cur); // try all given binary operator for evaluation 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); } } } // Below method returns all possible expression // evaluating to target static List<string> getExprs(string input, int target) { List<string> res = new List<string>(); getExprUtil(res, "", input, target, 0, 0, 0); return res; } // method to print result static void printResult(List<string> res) { for (int i = 0; i < res.Count; i++) Console.Write(res[i] + " "); Console.WriteLine(); } static void Main() { string input = "123"; int target = 6; List<string> res = getExprs(input, target); printResult(res); input = "125"; target = 7; res = getExprs(input, target); printResult(res); } } // This code is contributed by divyesh072019.
Javascript
<script> // Javascript program to find all possible expression which // evaluate to target // Utility recursive method to generate all possible // expressions function getExprUtil(res, curExp, input, target, pos, curVal, last) { // true if whole input is processed with some // operators if (pos == input.length) { // if current value is equal to target //then only add to final solution // if question is : all possible o/p then just //push_back without condition if (curVal == target) res.push(curExp); return; } // loop to put operator at all positions for (let i = pos; i < input.length; i++) { // ignoring case which start with 0 as they // are useless for evaluation if (i != pos && input[pos] == '0') break; // take part of input from pos to i let part = input.substr(pos, i + 1 - pos); // take numeric value of part let cur = parseInt(part, 10); // if pos is 0 then just send numeric value // for next recursion if (pos == 0) getExprUtil(res, curExp + part, input, target, i + 1, cur, cur); // try all given binary operator for evaluation 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); } } } // Below method returns all possible expression // evaluating to target function getExprs(input, target) { let res = []; getExprUtil(res, "", input, target, 0, 0, 0); return res; } // method to print result function printResult(res) { for (let i = 0; i < res.length; i++) document.write(res[i] + " "); document.write("</br>"); } let input = "123"; let target = 6; let res = getExprs(input, target); printResult(res); input = "125"; target = 7; res = getExprs(input, target); printResult(res); // This code is contributed by decode2207. </script>
Producción:
1+2+3 1*2*3 1*2+5 12-5
Complejidad de tiempo: O( )
Espacio auxiliar: O(N)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA