uva-10700-贪心

题意：对于一个只有加法和乘法的序列,没有加法和乘法的优先级,问,结果最大值和最小值是多少,数字范围 1<=N <= 20

解题思路:

(A+B)*C - (A+(B*C)) = AC + BC - A - BC = AC - A = A(C-1) >=0 

所以,先算加法肯定是最大值,先算乘法肯定是最小值,使用一个栈模拟运算,注意使用long long

#include <string>
#include<iostream>
#include<map>
#include<memory.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>


namespace cc
{
    using std::cout;
    using std::endl;
    using std::cin;
    using std::map;
    using std::vector;
    using std::string;
    using std::sort;
    using std::priority_queue;
    using std::greater;
    using std::vector;
    using std::swap;
    using std::stack;

    constexpr int N = 1001;
    //constexpr int N = 30;

    //priority_queue<int,vector<int>, greater<int> >q;

    //int a[N];
    //int b[N*N];

    long long MIN(string str) 
    {
        stack<long long> st;
        long long c = 0;
        int needMul = 0;
        for (auto i=0;i<str.length();i++) 
        {
            if (str[i] == '*')
            {
                if (needMul)
                {
                    c = c * st.top();
                    st.pop();
                    needMul = 0;
                }
                st.push(c);
                c = 0;
                needMul = 1;
            }
            else if(str[i]=='+')
            {
                if (needMul)
                {
                    c = c * st.top();
                    st.pop();
                    needMul = 0;
                }
                st.push(c);
                c = 0;
            }
            else
            {
                c = c * 10 + (str[i] - '0');
                
            }
        }
        if (needMul)
        {
            c = c * st.top();
            st.pop();
        }
        while (st.empty() == false)
        {
            c = c + st.top();
            st.pop();
        }
        return c;
    }

    long long MAX(string str)
    {
        stack<long long> st;
        long long c = 0;
        int needAdd = 0;
        for (auto i = 0;i < str.length();i++)
        {
            if (str[i] == '*')
            {
                if (needAdd)
                {
                    c = c + st.top();
                    st.pop();
                    needAdd = 0;
                }
                st.push(c);
                c = 0;
            }
            else if (str[i] == '+')
            {
                if (needAdd)
                {
                    c = c + st.top();
                    st.pop();
                    needAdd = 0;
                }
                st.push(c);
                c = 0;
                needAdd = 1;
            }
            else
            {
                c = c * 10 + (str[i] - '0');

            }
        }
        if (needAdd)
        {
            c = c + st.top();
            st.pop();
        }
        while (st.empty() == false)
        {
            c = c * st.top();
            st.pop();
        }
        return c;
    
    }

    void solve()
    {
        int n;
        cin >> n;
        while (n--) 
        {
            string str;
            cin >> str;
            long long min = MIN(str);
            long long max = MAX(str);
            cout << "The maximum and minimum are " << max << " and " << min << "." << endl;
            
        }
    }

};


int main()
{

#ifndef ONLINE_JUDGE
    freopen("d://1.text", "r", stdin);
#endif // !ONLINE_JUDGE
    cc::solve();

    return 0;
}