Call of Acceepted【中綴り式】2018 ICPC瀋陽ネットワーク試合

Call of Acceepted
You an d your friends.the table,playing an old and interesting game-the Call of Cthulhu.The is a mechaism in the game:rolling the dice.You use a notation to communicate the type of dice the the opediedbe. d y x  d  y"means that an y-sided dice shound be rolled x times and the sum of the res ults is taken.Formally,for any two integers x,y x,y satisfying x≧0 and y≧1 y≧1 y≧1 d y x  d  y"means the sum of x random integers in the range of[1,y].It’s ovious that eigther x<0 x<0 or y<1 y<1 makes the expression x> d y x  d  emilegal.For example:“2 d 6 2 d 6”means that rolling a 6-sided dice 2 times.At this time,the reult can be at least[1,1]=2,and at most[6,6]=12.The restults of rolling can theeeexxxabebeinininininininininininininininininininininininininapartattttttttttthethethethethethethethethethethethethethethethethethethethetheapartattttttttttttttttleleleleleleleleleleleator「d」does not satisfy the assicative law,it’s necessary to make sure that“d”is right-assicriative.Now the game has reached its most excititing stage.You are facing the Great One-Cthulu.Becagreenyour sanity value needs to be deducted according to the result of rolling.If the sanity value loses too much,You will fall into madness.As player,you want to write a program for knowing the minum and mashoutvance of
The oldest and strongest emotion of manked is fear,and the oldest and strontagst kind of fear is fear of the unknown.—H.P.Lovecraft
Input
The re are multiple sets of input、at most 30 cases.
Each set of input contains a string of only'+'-'、'、'*'d'('、')and integers without spaces,indicating the expression of this loss.The length of the expression will most 100.
It is garanted that all expressitions are legal,all operators except for'('and')ar binary,and all intermediate relt while calculating are e e e integers in the range of[−21473648]
The most merciful thing in the world,I think,is the inability of the huoman mind to corelate all its contens.We live on a placd island of ignorance in the midst of black seas of infinity,and it was not meanthwelt.
Output
For each set of data、output a line of two integers separated by spaces、indicating the minimum and maximb possible values of the sanity loss.
サンプル入力
3 d 6*5 2 d 3 d 4
サンプル出力
15 90 2 24
件名:
演算dを定義します.a d bは[1,b][1,b]の範囲内でランダムa回、a∈[0,+∞]a∈[0,+∞)、b∈[1,∞]b∈[1,118]b∈[1,+∞]の乱数の和を表します.演算優先度は乗算より高いです.
In particular,the precedence of"d"is above"*"を入力します.文字列を表式として入力して、その最大値と最小値を求めます.

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
struct ob {//                 。。
    ll nu;
    char fu;
    ob() {};
    ob(ll x) { nu = x; fu = 0; }
    ob(char c) { nu = 0; fu = c; }
};
queuesuf;//     
stack<char>st;//   
stackmi, ma;//         
string s;
int pri[129];//     
int main()
{
    pri['('] = 0;
    pri['+'] = pri['-'] = 1;
    pri['*'] = 2;
    pri['d'] = 3;
    pri[')'] = 4;//       
    while (cin >> s)
    {
        while (suf.size()){suf.pop();}while (st.size()){st.pop();}while (mi.size()){mi.pop();}while (ma.size()){ma.pop();}
        ll t = 0;
        int i = 0;
        while (i < s.size())
        {
            if (s[i] >= '0'&&s[i] <= '9')//      
            {
                t = 0;
                while (s[i] >= '0'&&s[i] <= '9')
                {
                    t = t * 10 + s[i] - '0';
                    i++;
                }
                suf.push(ob(t));
            }
            else
            {
                if (st.empty())
                {
                    st.push(s[i]);
                }
                else
                {
                    if (s[i] == '(')
                    //       
                    {
                        st.push(s[i]);
                    }
                    else if (s[i] == ')')
                    //     ，       
                    {
                        while (st.top() != '(')
                        {
                            suf.push(ob(st.top()));
                            st.pop();
                        }
                        st.pop();
                    }
                    else if (pri[s[i]] > pri[st.top()])
                    //           ，  
                        st.push(s[i]);
                    else if (pri[s[i]] < pri[st.top()])
                    //           ，               ，  
                    {
                        while (st.size()&&pri[st.top()]>=pri[s[i]])
                        {
                            suf.push(ob(st.top()));
                            st.pop();
                        }
                        st.push(s[i]);
                    }
                    else if (pri[s[i]] == pri[st.top()])
                    //     ，    ，    
                    {
                        suf.push(ob(st.top()));
                        st.pop();
                        st.push(s[i]);
                    }
                }//             
                i++;
            }
        }
        while (st.size())
        {
            suf.push(ob(st.top()));
            st.pop();
        }
        while (suf.size())
        {
            ob oo = suf.front();
            suf.pop();
            if (oo.fu)
            //    ，       ，                       
            //                     
            {
                ll a, b, A, B;
                a = b = A = B = 0;
                if (mi.size()) { a = mi.top(); mi.pop(); }
                if (mi.size()) { b = mi.top(); mi.pop(); }
                if (ma.size()) { A = ma.top(); ma.pop(); }
                if (ma.size()) { B = ma.top(); ma.pop(); }
                //b  ，a  
                ll res = 0;
                if (oo.fu == 'd')
                {
                    if (a < 1)a = 1;
                    if (A < 1)A = 1;
                    if (b < 0)b = 0;
                    if (B < 0)B = 0;
                    ma.push(max(a*b, max(a*B, max(A*b, A*B))));
                    mi.push(min(b, B));
                }
                else if (oo.fu == '+')
                {
                    mi.push(min(a + b, min(a + B, min(A + b, A + B))));
                    ma.push(max(a + b, max(a + B, max(A + b, A + B))));
                }
                else if (oo.fu == '*')
                {
                    mi.push(min(a * b, min(A * B, min(a*B, A*b))));
                    ma.push(max(A * B, max(a * b, max(a*B, A*b))));
                }
                else if (oo.fu == '-')
                {
                    mi.push(min(B - A, min(b - a, min(B - a, b - A))));
                    ma.push(max(b - a, max(B - A, max(B - a, b - A))));
                }
            }
            else//       
            {
                mi.push(oo.nu);
                ma.push(oo.nu);
            }
        }
        cout << mi.top() << ' ' << ma.top() << endl;//             
    }
}