题意：给出1个数字组成的字符串，然后在字符串内添加3种运算符号 * + - ，要求输出所有添加运算符并运算后结果等于2000的式子。
所有数字不能有前导0，且式子必须是合法的。
题解：字符串长度25左右，可以暴力，用dfs搜索所有可能的分割情况，并在每次分割的字符后添加3种运算符，然后递归到最后1个字符拿去判断，先用栈把所有分割字符串得到的数字压栈，同时优先运算’*’，然后再从左到右计算看结果是不是为2000，注意2000=是IMPOSSIBLE。。。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
const int N = 30;
char str[N], s1[N], flag[3] = {'*', '+', '-'};
int res, len, s[N], pos[N];
vector<char> v[100];
bool judge(int num) {
int cnt = 0, temp = 0, flag2 = 0;
stack<int> sta;
while (!sta.empty())
sta.pop();
for (int i = 0; i < len; i++) {
temp = temp * 10 + s[i];
if (i == pos[cnt]) {
if (flag2) {
int aa = sta.top();
sta.pop();
aa = aa * temp;
sta.push(aa);
if (s1[cnt] != '*')
flag2 = 0;
}
else if (s1[cnt] == '+' || s1[cnt] == '-')
sta.push(temp);
else if (s1[cnt] == '*') {
sta.push(temp);
flag2 = 1;
}
temp = 0;
cnt++;
}
}
if (flag2) {
int aa = sta.top();
sta.pop();
aa = aa * temp;
sta.push(aa);
}
else
sta.push(temp);
stack<int> sta2;
while (!sta.empty()) {
sta2.push(sta.top());
sta.pop();
}
for (int i = 0; i < num; i++) {
if (s1[i] != '*') {
int aa = sta2.top();
sta2.pop();
int bb = sta2.top();
sta2.pop();
if (s1[i] == '-') {
int cc = aa - bb;
sta2.push(cc);
}
else {
int cc = aa + bb;
sta2.push(cc);
}
}
}
if (sta2.size() == 1 && sta2.top() == 2000)
return true;
return false;
}
void dfs(int cur, int num, int pre) {
if (cur == len - 1) {
if (judge(num)) {
v[res].clear();
int cnt = 0;
for (int i = 0; i < len; i++) {
v[res].push_back(str[i]);
if (i == pos[cnt])
v[res].push_back(s1[cnt++]);
}
v[res].push_back('=');
res++;
}
return;
}
pos[num] = cur;
for (int i = 0; i < 3; i++) {
s1[num] = flag[i];
dfs(cur + 1, num + 1, cur);
}
pos[num] = -1;
if (str[cur] == '0' && cur - pre == 1)
return;
dfs(cur + 1, num, pre);
}
int main() {
int cas = 1;
while (scanf("%s", str) && str[0] != '=') {
memset(pos, -1, sizeof(pos));
res = 0;
len = strlen(str) - 1;
for (int i = 0; i < len; i++)
s[i] = str[i] - '0';
printf("Problem %d
", cas++);
if (strcmp(str, "2000=") == 0) {
printf(" IMPOSSIBLE
");
continue;
}
dfs(0, 0, -1);
if (res == 0)
printf(" IMPOSSIBLE
");
else {
for (int i = 0; i < res; i++) {
printf(" %c", v[i][0]);
for (int j = 1; j < v[i].size(); j++)
printf("%c", v[i][j]);
printf("
");
}
}
}
return 0;
}