資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究用 C++ 列印所有可求值為目標值的表示式
在這個問題中，我們給定了一個 0 到 9 的整數字符串和一個目標值。我們必須打印出能夠使用 +、- 和 * 運算生成表示式的各種方式，其評估結果等於目標值。
我們舉一個例子來更好地理解該主題 −
Input: string = “123” , target= 6
Output: { “1+2+3”, “1*2*3” }為了解決這個問題，我們將透過將所有可能的二元運算子放在數字之間，然後用目標值檢查表示式的結果來建立表示式。
我們將所有值傳遞給將評估結果表示式的遞迴方法。如果數字從 0 開始，那麼我們將忽略它。
示例
#include <bits/stdc++.h>
using namespace std;
void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos,int curVal, int last){
if (pos == input.length()){
if (curVal == target)
res.push_back(curExp);
return;
}
for (int i = pos; i < input.length(); i++){
if (i != pos && input[pos] == '0')
break;
string part = input.substr(pos, i + 1 - pos);
int cur = atoi(part.c_str());
if (pos == 0)
generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
else{
generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
}
}
}
vector<string>generateExpression(string input, int target){
vector<string> res;
generateExpressionForTarget(res, "", input, target, 0, 0, 0);
return res;
}
int main(){
string input = "345";
int target = 12;
cout<<"The expressions are: \n";
vector<string> res = generateExpression(input, target);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
cout << endl;
return 0;
}輸出
這些表示式為 −
3+4+5
更新於： 2020 年 1 月 17 日
237 次檢視
廣告