题目描述：
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 $10^4$ 。
数据范围：
$1\le expression.len \le 20$
只存在 +-*，并且整数值在范围 $[0,99]$
题解：
对于一个计算式 1 + 2 * 3 - 4 * 5，如果只加一层括号，不嵌套。那么可以得到四种加括号的方式：
(1) + (2 * 3 - 4 * 5)
(1 + 2) * (3 - 4 * 5)
(1 + 2 * 3) - (4 * 5)
(1 + 2 * 3 - 4) * (5)
可以发现，对中间的运算符进行分割，左右两侧又是一个新的字符串，所以可以使用分治算法，更小的字符串交给递归程序处理，只需要处理最外层，分割一次的情况。
分完之后，最后对结果合并。合并时，取出左侧字符串结果和右侧字符串结果，然后二者做运算。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<int> diffWaysToCompute(string expression)
{
vector<int> ret;
int tmp = 0;
bool flag = false;
for (int i = 0; i < expression.size(); ++i)
{
if (!flag)
tmp = tmp * 10 + expression[i] - '0';
if (expression[i] < '0' || expression[i] > '9')
{
flag = true;
vector<int> left = diffWaysToCompute(expression.substr(0, i));
vector<int> right = diffWaysToCompute(expression.substr(i + 1));
for (auto &l : left)
{
for (auto &r : right)
{
switch (expression[i])
{
case '+':
ret.emplace_back(l + r);
break;
case '-':
ret.emplace_back(l - r);
break;
case '*':
ret.emplace_back(l * r);
break;
default:
break;
}
}
}
}
}
if (!flag)
ret.emplace_back(tmp);
return ret;
}
};
|