题目描述

问题描述
　　计算器和计算机的大量普及也有其弊端。即便是受过专业技术训练的学生们也很可能缺乏计算能力。由于电脑的大量使用，很多人无法心算出7*8这样的算式，甚至是用纸和笔也算不出13*17。不过谁在意呢？
　　Bartjens教授十分在意——因为他比较传统。他决定给学生布置一些计算作业，并且不能使用电子设备。为了批改方便，他决定使得几乎所有题答案都是2000，不过不全是，否则会被学生发现然后就不仔细计算了。
　　不幸的是，Bartjens教授的打印机实在是太旧了，不能和新的打印机兼容。打印出了题目后，教授发现所有的符号都丢失了！例如2100-100=，被打印成了2100100=。不过，数字和等号被正确的打印了。
　　更糟糕的是，教授的试题原稿不见了。因此，他需要恢复出这些题原来的样子。如果答案是2000，那么2100100=可能是：
　　2100-100=
　　2*100*10+0=
　　2*100*10-0=
　　2*10*0100=
　　2*-100*-10+0=
　　Bartjen教授记得几点：
　　1.他写的数字没有前导零。例如2*10*0100=就是不可行的。
　　2.他写0的时候不会写多个0。例如2*1000+000=就是不可行的。
　　3.他只用二元运算符，不用取负。所以2*-100*-10+0=也不合法。
　　4.他只用+、-、*，不用/和括号。
　　5.这些算式按照正常的优先级顺序计算。
　　你需要帮助barjen教授恢复这些题目。你需要在算式中插入至少一个运算符，使得答案是2000。有多少种可能的算式呢？
输入格式
输入包含一组数据。这组数据有n个数字（1<=n<=9），后面跟着一个=号。
输出格式
输出包含若干行，每一行是一个可行的解，具体格式见样例。按字典序从小到大输出这些字符串。如果无解，输出一行IMPOSSIBLE。

样例

2100100=
【样例输出】
2*100*10+0=
2*100*10-0=
2100-100=

算法

(dfs + 判断字符串是否合法 +计算器)

好多好多细节要注意。

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <numeric>
#include <map>
using namespace std;
const int N = 15;
int n;
typedef vector<string>::iterator iter;
vector<string> V;
char str[N];
char op[3];
int calculate(string s) { // 输入合法字符串，计算器
    vector<int> stk;
    char preSign = '+';
    int num = 0;
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        if (isdigit(s[i])) {
            num = num * 10 + int(s[i] - '0');
        }
        if ((!isdigit(s[i]) && s[i] != ' ') || i == n - 1) {
            switch (preSign) {
                case '+':
                    stk.push_back(num);
                    break;
                case '-':
                    stk.push_back(-num);
                    break;
                case '*':
                    stk.back() *= num;
                    break;
            }
            preSign = s[i];
            num = 0;
        }
    }
    return accumulate(stk.begin(), stk.end(), 0); // 累加的初值
}

bool isValid(string s){ // 字符串子否合法
    int len = s.length();
    bool flag = true;
    for(int i = 0; i < len ;i ++ ) if(!isdigit(s[i])) {flag = false; break;}
    if(flag) return false;
    int i = 0;
    // bool flag = true;
    while(i < len){
        if(isdigit(s[i])){
            if(s[i] == '0') if(i + 1 < len && isdigit(s[i + 1])) return false;
            while(i < len && isdigit(s[i])) i ++ ;
        } 
        // else if(!isdigit(s[i])) flag = false;
        i ++ ;
    }
    // if(flag) return false;
    return true;
}

void dfs(int pos, string s){ // 当前符号塞的位置，当前字符串
    if(pos == n) {
        // cout << s << " "; 
        // cout << isValid(s) << endl;
        if(isValid(s)){
            if(calculate(s) == 2000) V.push_back(s + '=');
        }
        return;
    }

    dfs(pos + 1, s + str[pos]);
    for(int i = 0; i < 3; i ++ ){
        if(pos == 0 && i != 1) break;
        dfs(pos + 1, s + op[i] + str[pos]);
    }

}

int main(){

    cin >> str;
    n = strlen(str) - 1;
    // cout << n << endl;
    // cout << calculate("1-2*3") << endl;
    // cout << isValid("1000") << endl;
    op[0] = '+';
    op[1] = '-';
    op[2] = '*';

    dfs(0, ""); // pos, op
    if(V.empty()) {
        puts("IMPOSSIBLE");
        return 0;
    }
    sort(V.begin(), V.end());
    for(iter it = V.begin(); it != V.end(); it ++ ) cout << (*it) << endl;
    return 0;
}