csp-二十四点

题目链接

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

map<char,int> mp;
char str[11];

int fun(int t2,int t1,char op)
{
    if(op=='+')
        return t2+t1;
    else if(op=='-')
        return t2-t1;
    else if(op=='x')
        return t2*t1;
    else if(op=='/')
        return t2/t1;
}

int main()
{
    int n;
    cin >> n;  getchar();
    mp['+']=mp['-']=1;   mp['x']=mp['/']=2;

    while(n--)
    {
        stack<int> s1;  stack<char> s2;
        gets(str);
        for(int i=0;i<7;i++)
        {
            if(isdigit(str[i])) s1.push(str[i]-'0');
            else
            {
                if(s2.empty() || mp[s2.top()]<mp[str[i]])
                    s2.push(str[i]);
                else
                {
                    int t1=s1.top();  s1.pop();
                    int t2=s1.top();  s1.pop();
                    char op=s2.top();   s2.pop();
                    int res=fun(t2,t1,op);
                    s1.push(res);
                    s2.push(str[i]);
                }
            }
        }
        while(s1.size()!=1)
        {
            int t1=s1.top();  s1.pop();
            int t2=s1.top();  s1.pop();
            char op=s2.top();   s2.pop();
            int res=fun(t2,t1,op);
            s1.push(res);
        }
        if(s1.top()==24)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

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

stack<char> op;
stack<int> num;
int n,m;

void eval()
{
    int b=num.top();  num.pop();
    int a=num.top();  num.pop();

    char t=op.top();  op.pop();

    int res;
    if(t=='+') res=a+b;
    else if(t=='-') res=a-b;
    else if(t=='x') res=a*b;
    else if(t=='/') res=a/b;

    num.push(res);
}

int main()
{
    cin >> n; getchar();
    unordered_map<char,int> mp{{'+',0},{'-',0},{'x',1},{'/',1}};

    while(n--)
    {
        string str;
        getline(cin,str);

        for(int i=0;i<str.size();i++)
        {
            if(isdigit(str[i]))
                num.push(str[i]-'0');
            else
            {
                while(op.size() && mp[op.top()]>=mp[str[i]])
                    eval();

                op.push(str[i]);
            }
        }
        while(op.size()) eval();

        if(num.top()==24) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}
上一篇:模拟堆


下一篇:表达式求值(栈)