竞赛讨论区 > 卡到74%,想要一个WA的数据
头像
大圣爱面码
发布于 2018-08-23 17:14
+ 关注

卡到74%,想要一个WA的数据

# include <iostream>
# include <algorithm>
# include <cstring>
# include <stack>
# define ll long long 
# define P pair<ll,ll>


using namespace std;

int Rank[256]={0};

ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

void init()
{
    Rank['#']=0;
    Rank['(']=0;
    Rank[')']=0;
    Rank['+']=1;
    Rank['-']=1;
    Rank['*']=2;
    Rank['/']=2;
    return ;
}


string getRPN(string s)
{
    stack <char> s1;
    stack <char> s2;
    s1.push('#');
    for(int i=0;i<s.size();i++)
    {
        switch(s[i])
        {
            case 'x':
                s2.push('x');
                break;
            case '(':
                s1.push('(');
                break;
            case '+':
            case '-':
            case '*':
            case '/':
                while(Rank[s[i]]<=Rank[s1.top()])
                {
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.push(s[i]);
                break;
            case ')':
                while(s1.top()!='(')
                {
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.pop();
                break;
        }
    }
    while(s1.top()!='#')
    {
        s2.push(s1.top());
        s1.pop();
    }
    string t="";
    while(s2.size())
    {
        t+=s2.top();
        s2.pop();
    }
    reverse(t.begin(),t.end());
    return t;
}

P calcRPN(string t)
{
    stack <P > s;
    P a,b;
    for(int i=0;i<t.size();i++)
    {
        switch(t[i])
        {
            case 'x':
                s.push(P(1,1));
                break;
            case '+':
                a=s.top();
                s.pop();
                b=s.top();
                s.pop();
                if(a.first==b.first)
                    a.second=a.second+b.second;
                else if(a.first<b.first)
                    a=b;
                s.push(a);
                break;
            case '*':
                a=s.top();
                s.pop();
                b=s.top();
                s.pop();
                a.second*=b.second;
                a.first+=b.first;
                s.push(a);
                break;                    
        }
    }
    return s.top();
}

int main()
{
    init();
    string s,t;
    cin>>s>>t;
    s=getRPN(s);
    t=getRPN(t);
    P a=calcRPN(s);
    P b=calcRPN(t);
    if(a.first==b.first)
    {
        ll k=gcd(a.second,b.second);
        cout<<a.second/k<<"/"<<b.second/k<<endl;
    }
    else if(a.first>b.first)
        cout<<"1/0"<<endl;
    else
        cout<<"0/1"<<endl;
    /*cout<<a.second<<"*x^"<<a.first<<endl;
    cout<<b.second<<"*x^"<<b.first<<endl;*/
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐