題意：給出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;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
