打印所有可能计算为目标的表达式-yiteyi-C++库

给定一个只包含0到9的数字和一个整数值的字符串，目标 .找出可以计算的表达式的数量目标在给定的数字串中使用二进制运算符+、–和*。

null

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个问题可以通过将所有可能的二进制运算符放在数字中间并计算它们，然后检查它们是否计算到目标值来解决。

在编写递归代码时，我们需要将这些变量作为递归方法的参数——结果向量、输入字符串、当前表达式字符串、目标值、处理输入的位置、当前评估值和评估中的最后一个值。
由于乘法运算，最后一个值保留在递归中，在进行乘法运算时，我们需要最后一个值来正确计算。

请参见下面的示例，以便更好地理解——

Input is 125, suppose we have reached till 1+2 now,Input = “125”, current expression = “1+2”, position = 2, current val = 3, last = 2Now when we go for multiplication, we need last value for evaluation as follows:current val = current val - last + last * current valFirst we subtract last and then add last * current val for evaluation, new last is last * current val.current val = 3 – 2 + 2*5 = 11last = 2*5 = 10

在下面的代码中需要注意的另一件事是，我们忽略了所有从0开始的数字，将一个条件作为循环中的第一个条件，这样我们就不会处理03、05等数字。请参阅使用CXString（）函数，该函数将C++字符串转换为C char数组，该函数用于下面的代码中，因为ATOI（）函数希望字符数组作为参数而不是字符串。它将字符数组转换为数字。

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;                       
                         }                       

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>                       

输出：

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

时间复杂性： O( $4 ^ N$ ) 辅助空间： O（N）本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章