uva 817(dfs)

发布时间：2020-12-13 20:45:47 所属栏目：PHP教程来源：网络整理

导读：题意：给出1个数字组成的字符串，然后在字符串内添加3种运算符号 * + - ，要求输出所有添加运算符并运算后结果等于2000的式子。所有数字不能有前导0，且式子必须是合法的。题解：字符串长度25左右，可以暴力，用dfs搜索所有可能的分割情况，并在每次分割的

题意：给出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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!