题意：对于一个只有加法和乘法的序列,没有加法和乘法的优先级,问,结果最大值和最小值是多少,数字范围 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 = ;
//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 = ;
int needMul = ;
for (auto i=;i<str.length();i++)
{
if (str[i] == '*')
{
if (needMul)
{
c = c * st.top();
st.pop();
needMul = ;
}
st.push(c);
c = ;
needMul = ;
}
else if(str[i]=='+')
{
if (needMul)
{
c = c * st.top();
st.pop();
needMul = ;
}
st.push(c);
c = ;
}
else
{
c = c * + (str[i] - ''); }
}
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 = ;
int needAdd = ;
for (auto i = ;i < str.length();i++)
{
if (str[i] == '*')
{
if (needAdd)
{
c = c + st.top();
st.pop();
needAdd = ;
}
st.push(c);
c = ;
}
else if (str[i] == '+')
{
if (needAdd)
{
c = c + st.top();
st.pop();
needAdd = ;
}
st.push(c);
c = ;
needAdd = ;
}
else
{
c = c * + (str[i] - ''); }
}
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 ;
}