在 C++ 中添加括号的不同方法
c++server side programmingprogramming更新于 2024/11/9 0:03:00
假设我们有一串数字和运算符，我们必须通过计算所有可能的方式来对数字和运算符进行分组，从而找到所有可能的结果。这里有效的运算符是 +、- 和 *。因此，如果输入是"2*3-4*5"，则输出将是 [-34, -14, -10, -10, 10]。这是因为 −
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 memo 的地图。
定义一个名为 solved() 的方法。这将把输入字符串作为输入。
创建一个名为 ret 的数组
如果备忘录有输入，则返回 memo[input]
对于 i，范围从 0 到输入字符串的大小 −
如果 input[i] 是任何受支持的运算符，则
数组 part1 := resolve(输入的子字符串从 0 到 i - 1)
数组 part2 := resolve(输入的子字符串从 i 到字符串末尾)
对于 j，范围从 0 到 part1 的大小
对于 k，范围从 0 到 part2 的大小
如果 input[i] 是加法，则
执行 part[j] + part[k] 并添加到 ret
如果 input[i] 是乘法，则
执行 part[j] * part[k] 并添加到 ret
如果 input[i] 是减法，则
执行 part[j] - part[k] 并添加到 ret
如果 ret 为空，则将输入字符串作为整数返回
memo[input] := ret，并返回 ret
示例 (C++)
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
map <string, vector<int>> memo;
vector<int> diffWaysToCompute(string input) {
vector <int> ret;
if(memo.count(input)) return memo[input];
for(int i = 0; i < input.size(); i++){
if(input[i] == '+' || input[i] == '*' || input[i] == '-'){
vector <int> part1 = diffWaysToCompute(input.substr(0, i));
vector <int> part2 = diffWaysToCompute(input.substr(i + 1));
for(int j = 0; j < part1.size(); j++ ){
for(int k = 0; k < part2.size(); k++){
if(input[i] == '+'){
ret.push_back(part1[j] + part2[k]);
}
else if(input[i] == '*'){
ret.push_back(part1[j] * part2[k]);
} else {
ret.push_back(part1[j] - part2[k]);
}
}
}
}
}
if(ret.empty()){
ret.push_back(stoi(input));
}
return memo[input] = ret;
}
};
main(){
Solution ob;
print_vector(ob.diffWaysToCompute("2*3-4*5"));
}
输入
"2*3-4*5"
输出
[-34, -10, -14, -10, 10, ]
