题解

题目难度：中等难度

难点分析：

1.对于四个数字具有24种排列方式。比如：1 2 3 4 可以重新排列为1 3 4 2、4 3 2 1等情况。

2.两个数字之间可以插入任意符号“+” 、“-”、“*”、“/”，四个数字一共有3个符号

3.运算符具有优先级，需要先进行“*”、“/”运算，再进行“+”、“-”运算。

知识点：栈、全排列、字典序、四则运算

思路：

首先思考一个运算式子的计算过程：(使用栈)

如 1 + 3 * 5 - 6

其中数字放入数组a种，运算符放入数组b种（1表示“+”，2表示“-”，3表示“*”，4表示“/”）

数组a:

数组b:

第一步：

将a[0]压入栈s中
##第二步：
依次判断每个运算符：

如果是“+”和“-”，直接压入栈s中（不能直接运算，需要继续判断之后是否存在“*”“/”优先级更高的运算符）。

如果是“*”、“/”，弹出栈顶元素进行乘或者除操作。

第三步：

在第二步中，所用的乘除运算已经运算完成，现在进行加减运算。由于栈先弹出后压入的数字，同时加减运算满足结合

律，因此对数组b运算符逆序依次判断：

当b[x]=1时：

弹出栈顶两个元素，将相加之和压入栈中

当b[x]=2时：

弹出栈顶两个元素相减，注意：后后弹出元素减先弹出元素

当b[x]=3或者b[x]=4时：

由于第二步已经运算过，直接跳过（代码中，在第二步乘除运算后将b[x]赋值为0，因此当b[x]=0时直接跳过运算即可）。

第四步：

通过第三步运算，栈中比保存一个元素，即为运算结果。

考虑数组a中数组的顺序问题，使用STL对其进行全排列。

STL中有两个关于全排列的函数，分别为next_permutation（下一个排列）和prev_permutation（上一个排列），这两

个算法都是以“字典序”为准则进行全排列的。所谓某一序列的全排列，指的是：“序列上每一位都取完该序列所包含的所

有元素”，如“123”的全排列为：“123”、“132”、“213”、“231”、“312”、“321”，共6种情况。

【注】得到通过next_permutation（下一个排列）函数得到全排列需要先对数字进行排序

关于运算符数组b:

通过三层for循环得到，每层循环代表一个位置的符号，包括四种情况（1表示“+”，2表示“-”，3表示“*”，4表示“/”）

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int main(){
    int n=4,m;
    stack<int> s;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>m;
    sort(a,a+4); 
    do{
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            for(int k=1;k<=4;k++){
                s.push(a[0]);
                int b[3];
                b[0]=i;b[1]=j;b[2]=k;        
                for(int x=0;x<3;x++){
                    if(b[x]==1||b[x]==2) s.push(a[x+1]);
                    else{
                        int tmp=s.top();
                        s.pop();
                        if(b[x]==3) s.push(tmp*a[x+1]);
                        else s.push(tmp/a[x+1]); 
                        b[x]=0;
                    }
                }
                for(int x=2;x>=0;x--){
                    if(b[x]==0) continue;
                    else if(b[x]==1) {
                        int tmp;
                        tmp=s.top();
                        s.pop();
                        tmp+=s.top();
                        s.pop();
                        s.push(tmp);
                    }else{
                        int tmp;
                        tmp=s.top();
                        s.pop();
                        tmp=s.top()-tmp;
                        s.pop();
                        s.push(tmp);
                    }
                }
      //  cout<<s.size()<<":"<<s.top()<<endl;
        if(s.top()==m){
            cout<<1;
            return 0;
        }
        s.pop();
        }
    }
}
}while(next_permutation(a,a+4)); 

    cout<<0;
    return 0;
}