UVA 10700 題解：通過加括號改變加乘表達式求值的最大最小值

題目大意

輸入只含 + 和 * 的表達式（數字 ≤ 20），可加括號改變運算順序。求最大值與最小值。多測試用例。

數學洞察

對於正整數 a, b, c：

• a * b + c ≤ a * (b + c) → 先加後乘結果更大。
• a + b * c ≥ (a + b) * c（不總是，但總體趨勢） → 先乘後加結果更小。

結論：最小值對應「先算所有乘法，再算加法」；最大值對應「先算所有加法，再算乘法」。

棧模擬算法

掃描表達式提取數字與運算符。兩種策略分別模擬：

1. 求最小值：遇到 * 立即與棧頂相乘；遇到 + 將數字入棧。最後求棧內所有數之和。
2. 求最大值：遇到 + 立即與棧頂相加；遇到 * 將數字入棧。最後求棧內所有數之積。

首個數字前假設一個虛擬運算符（最小值用 +，最大值用 *），統一處理邏輯。

AC 代碼 (C++)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char str[100]; scanf("%s", str);
        double minv=0, maxv=1, stk[30];
        // 最小值：先乘後加
        int top=0, i=0; char op='+';
        while (str[i]) {
            int val=0;
            while (str[i]>='0' && str[i]<='9') val=val*10+str[i++]-'0';
            if (op=='+') stk[++top]=val;
            else stk[top]*=val;
            if (str[i]) op=str[i++];
        }
        for (i=1;i<=top;i++) minv+=stk[i];
        // 最大值：先加後乘
        top=0; i=0; op='*';
        while (str[i]) {
            int val=0;
            while (str[i]>='0' && str[i]<='9') val=val*10+str[i++]-'0';
            if (op=='*') stk[++top]=val;
            else stk[top]+=val;
            if (str[i]) op=str[i++];
        }
        for (i=1;i<=top;i++) maxv*=stk[i];
        printf("The maximum and minimum are %.0lf and %.0lf.\n", maxv, minv);
    }
    return 0;
}

注意

結果可能超過 64 位整數，需用 double（或高精度）存儲，輸出格式 %.0lf。