您当前位置：首页 > php开源 > php教程 > uva 817(dfs)

uva 817(dfs)

来源：程序员人生发布时间：2015-07-30 14:18:28 阅读次数：2230次

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

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 leetcode || 138、Copy List with Random Pointer

下一篇 同余与模运算

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点