题目大意：给一个不含括号、只有+和*运算的表达式，数字的范围在1到20之间，算出计算结果的可能最大值和最小值。
贪心，如果加法优先级比乘法高，那么得出的结果为最大值。(a+b)*c = a*c + b*c >= a+b*c。同理，如果乘法优先级比加法高，得出的结果为最小值。
#include <cstdio>
#include <cctype> int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
double lmin, lmax, lstack[];
int top;
int N;
scanf("%d", &N);
getchar();
char s[];
while (N--)
{
gets(s);
char ch = '+';
top = ;
for (int i = ; s[i] != '\0'; )
{
int n = ;
while (isdigit(s[i]))
{
n = n* + s[i]-'';
i++;
}
if (ch == '+') lstack[top++] = n;
else lstack[top-] *= n;
if (s[i] != '\0') ch = s[i++];
}
lmin = ;
for (int i = ; i < top; i++)
lmin += lstack[i];
top = ;
ch = '*';
for (int i = ; s[i] != '\0'; )
{
int n = ;
while (isdigit(s[i]))
{
n = n* + s[i]-'';
i++;
}
if (ch == '*') lstack[top++] = n;
else lstack[top-] += n;
if (s[i] != '\0') ch = s[i++];
}
lmax = ;
for (int i = ; i < top; i++)
lmax *= lstack[i];
printf("The maximum and minimum are %.0lf and %.0lf.\n", lmax, lmin);
}
return ;
}
也可以用动态规划，不过觉得可以用贪心就不想麻烦了。