【题解】牛牛的24点

题意

给你一个包含个数字个操作符的表达式，计算其是否值为24。是输出Yes，否则输出No

题解一

由于输入的格式是固定的，而且只有一位数以及三个操作符。三个操作符在表达式字符串中的下标位置为，并且总的表达式类型个数也只有64种。所以我们可以先用程序把这64种表达式的语句打印出来，再粘到程序里面，即

char op1[4]= {'+','-','x','/'};
char op2[4]={'+','-','*','/'};
 for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            for(int k=0; k<4; k++)
            {
                printf("else if(str[1]=='%c'&&str[3]=='%c'&&str[5]=='%c'&&(a%cb%cc%cd)==24)printf(\"Yes\\n\");\n",op1[i],op1[j],op1[k],op2[i],op2[j],op2[k]);
            }

那么把第一个else去掉，最后再增加一个else输出No就可以了。

复杂度

时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
char str[10];
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",str);
        int a,b,c,d;
        a=str[0]-'0';
        b=str[2]-'0';
        c=str[4]-'0';
        d=str[6]-'0';
        if(str[1]=='+'&&str[3]=='+'&&str[5]=='+'&&(a+b+c+d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='+'&&str[5]=='-'&&(a+b+c-d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='+'&&str[5]=='x'&&(a+b+c*d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='+'&&str[5]=='/'&&(a+b+c/d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='-'&&str[5]=='+'&&(a+b-c+d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='-'&&str[5]=='-'&&(a+b-c-d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='-'&&str[5]=='x'&&(a+b-c*d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='-'&&str[5]=='/'&&(a+b-c/d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='x'&&str[5]=='+'&&(a+b*c+d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='x'&&str[5]=='-'&&(a+b*c-d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='x'&&str[5]=='x'&&(a+b*c*d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='x'&&str[5]=='/'&&(a+b*c/d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='/'&&str[5]=='+'&&(a+b/c+d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='/'&&str[5]=='-'&&(a+b/c-d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='/'&&str[5]=='x'&&(a+b/c*d)==24)printf("Yes\n");
        else if(str[1]=='+'&&str[3]=='/'&&str[5]=='/'&&(a+b/c/d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='+'&&str[5]=='+'&&(a-b+c+d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='+'&&str[5]=='-'&&(a-b+c-d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='+'&&str[5]=='x'&&(a-b+c*d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='+'&&str[5]=='/'&&(a-b+c/d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='-'&&str[5]=='+'&&(a-b-c+d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='-'&&str[5]=='-'&&(a-b-c-d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='-'&&str[5]=='x'&&(a-b-c*d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='-'&&str[5]=='/'&&(a-b-c/d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='x'&&str[5]=='+'&&(a-b*c+d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='x'&&str[5]=='-'&&(a-b*c-d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='x'&&str[5]=='x'&&(a-b*c*d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='x'&&str[5]=='/'&&(a-b*c/d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='/'&&str[5]=='+'&&(a-b/c+d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='/'&&str[5]=='-'&&(a-b/c-d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='/'&&str[5]=='x'&&(a-b/c*d)==24)printf("Yes\n");
        else if(str[1]=='-'&&str[3]=='/'&&str[5]=='/'&&(a-b/c/d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='+'&&str[5]=='+'&&(a*b+c+d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='+'&&str[5]=='-'&&(a*b+c-d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='+'&&str[5]=='x'&&(a*b+c*d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='+'&&str[5]=='/'&&(a*b+c/d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='-'&&str[5]=='+'&&(a*b-c+d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='-'&&str[5]=='-'&&(a*b-c-d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='-'&&str[5]=='x'&&(a*b-c*d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='-'&&str[5]=='/'&&(a*b-c/d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='x'&&str[5]=='+'&&(a*b*c+d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='x'&&str[5]=='-'&&(a*b*c-d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='x'&&str[5]=='x'&&(a*b*c*d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='x'&&str[5]=='/'&&(a*b*c/d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='/'&&str[5]=='+'&&(a*b/c+d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='/'&&str[5]=='-'&&(a*b/c-d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='/'&&str[5]=='x'&&(a*b/c*d)==24)printf("Yes\n");
        else if(str[1]=='x'&&str[3]=='/'&&str[5]=='/'&&(a*b/c/d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='+'&&str[5]=='+'&&(a/b+c+d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='+'&&str[5]=='-'&&(a/b+c-d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='+'&&str[5]=='x'&&(a/b+c*d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='+'&&str[5]=='/'&&(a/b+c/d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='-'&&str[5]=='+'&&(a/b-c+d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='-'&&str[5]=='-'&&(a/b-c-d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='-'&&str[5]=='x'&&(a/b-c*d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='-'&&str[5]=='/'&&(a/b-c/d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='x'&&str[5]=='+'&&(a/b*c+d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='x'&&str[5]=='-'&&(a/b*c-d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='x'&&str[5]=='x'&&(a/b*c*d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='x'&&str[5]=='/'&&(a/b*c/d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='/'&&str[5]=='+'&&(a/b/c+d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='/'&&str[5]=='-'&&(a/b/c-d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='/'&&str[5]=='x'&&(a/b/c*d)==24)printf("Yes\n");
        else if(str[1]=='/'&&str[3]=='/'&&str[5]=='/'&&(a/b/c/d)==24)printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

题解二

像这种表达式的题目一般可以用栈进行模拟计算。针对于这题，我们可以用一个数据栈来解决。对于给定的表达式，我们可以将里面的先处理成负数，也就是变成号，后面的数我们存下来负数形式，这样我们只用处理了。对于表达是的第一个数我们直接压入栈中，若遇到的是我们把数也直接压入栈中。若遇到，我们就得从栈中取出一个数进行计算后再压入栈中，最终的答案就是，数据栈中的值的和。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    int a[4];
    char op[3];
    scanf("%d",&t);
    while(t--) {
        string str;
        cin >> str;
        for(int i = 0; i < str.length(); i++) {
            if(i % 2 == 0) {
                a[i/2] = str[i] - '0';
                if(str[i-1] == '-') a[i/2] = -a[i/2];
            } else {
                op[(i-1)/2] = str[i];
            }
        }
        for(int i = 0; i < 3; i++) {
            if(op[i] == '-') op[i] = '+';
        }
        stack<int>s;
        for(int i = 0; i < 4; i++) {
            if(i == 0) s.push(a[i]);
            else {
                if(op[i-1] == '/') {
                    int temp = s.top();
                    s.pop();
                    temp = temp / a[i];
                    s.push(temp);
                } else if(op[i-1] == 'x') {
                    int temp = s.top();
                    s.pop();
                    temp = temp * a[i];
                    s.push(temp);
                } else {
                    s.push(a[i]);
                }
            }
        }
        int sum = 0;
        while(!s.empty()) {
            int temp = s.top();
            s.pop();
            sum += temp;
        }
        if(sum == 24) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}