华为机试：添加符号使等式成立



题目描述：

输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号或者不填，使得等式成立。

1 2 3 4 5 6 7 8 9 = X

比如：
12-34+5-67+89 = 5

1+23+4-5+6-7-8-9 = 5

请编写程序，统计满足输入整数的所有等式个数。

输入：       正整数，等式右边的数字

输出：       使该等式成立的个数

样例输入：5

样例输出：21

代码：

#include<iostream>
#include<string>
#include<stack>
#include<cmath>
using namespace std;

string inFixToPostFix(string expr)//简化的（没有*/和括号）中缀表达式转后缀表达式，细节见我的表达式计算博文，略有修改
{
    stack<char> opt;
    string res = "";
    int len = expr.size();
    for (int i = 0; i < len; i++)
    {
        if (isdigit(expr[i]))
        {
            res += expr[i];
        }
        else if(expr[i] == ' ')
        {
            continue;
        }
        else
        {
            if (i && isdigit(expr[i-1]))
            {
                res += ";";
            }
            if (opt.empty())
            {
                opt.push(expr[i]);
            }
            else
            {
                while (!opt.empty())
                {
                    res += opt.top();
                    res += ";";
                    opt.pop();
                }
                opt.push(expr[i]);
            }
        }
    }
    while(!opt.empty())
    {
        res += ";";
        res += opt.top();
        opt.pop();
    }
    res += ";";//这一句，是hack的做法，为了避免整个表达式就是123这种情况（没有操作符）
    return res;
}


int evalPostFix(string expr)//简化的后缀表达式计算
{
    int res = 0;
    stack<int> opr;
    int len = expr.size();
    int i, j;
    for (i = 0; i < len; i++)
    {
        if (expr[i] == ';')
        {
            continue;
        }
        else if (isdigit(expr[i]))
        {
            int num = 0;
            for (j = i; expr[j] != ';'; j++)//配合上面的；分割和结束判断
            {
                num = num * 10 + expr[j] - '0';
            }
            opr.push(num);
            i = j;
        }
        else
        {
            int right = opr.top();
            opr.pop();
            int left = opr.top();
            opr.pop();
            int t;
            switch(expr[i])
            {
            case '+':
                t = left + right;
                opr.push(t);
                break;
            case '-':
                t = left - right;
                opr.push(t);
                break;
            }
        }
    }
    res = opr.top();
    return res;
}

int main()
{
    string s = "1 2 3 4 5 6 7 8 9";
    int num;//等式右边的数字
    while(cin >> num)
    {
        int count = 0;//使等式成立的表达式个数
        int maxVaule = (int)pow(3, 8);//9个数字之间的8个位置，每个位置可以放置3种字符
        char select[] = " +-";//可选的字符列表
        for(int i = 0; i < maxVaule; i++)//枚举，把每个整数转化为相应的3进制数，然后改变等式左边的表达式
        {
            int t = i;
            for(int j = 1; j <= 15 ; j += 2)
            {
                s[j] = select[t%3];
                t /= 3;
            }
            if(evalPostFix(inFixToPostFix(s)) == num)//计算表达式的值
            {
                count++;
                cout << s << endl;
            }
        }
        cout << count << endl;
    }
    return 0;
}

结果：

当然，此题完全可以用DFS做，或者使用8重for循环计算，由于要求的是所有满足条件的等式个数，所以只能枚举，不可能更高效。