UVA 10700 Camel Trading 詳解

題目：給定不含括號的表達式，僅含正整數（1~20）、+、*，數字個數 ≤12。通過加括號改變運算順序，求表達式的最大值與最小值。

核心觀察：極值對應極端運算順序

• 最大值：優先做加法，再做乘法。即將表達式視為「乘法分隔的加法項」相乘。
  例：1+2*3+4 → (1+2)*(3+4)=21。
• 最小值：優先做乘法，再做加法。即按標準優先級（乘法優先）計算。
  例：1+2*3+4 → 1+(2*3)+4=11。

證明直覺：a+b vs a*b（a,b≥1），乘法增長更快。要最大化，盡量讓大數相乘（先加變大再乘）；要最小化，盡量讓小數相乘（先乘變小再加）。

棧模擬算法

兩次掃描，分別模擬兩種優先級：

1. 最小值（標準優先級：乘前加後）：
   維護棧 st。讀數字入棧。讀運算符：
     若 *：彈出棧頂 x，讀下一數 y，壓入 x*y。
     若 +：直接讀下一數入棧。
   最後棧內所有數求和 → 最小值。
2. 最大值（加前乘後）：
   維護棧 st。讀數字入棧。讀運算符：
     若 +：彈出棧頂 x，讀下一數 y，壓入 x+y。
     若 *：直接讀下一數入棧。
   最後棧內所有數求積 → 最大值。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

long long evalMin(const string& s) {
    vector st;
    long long cur = 0;
    char op = '+';
    for (size_t i = 0; i <= s.size(); ++i) {
        if (i < s.size() && isdigit(s[i])) {
            cur = cur * 10 + (s[i] - '0');
        } else {
            if (op == '+') st.push_back(cur);
            else if (op == '*') { st.back() *= cur; }
            if (i < s.size()) op = s[i];
            cur = 0;
        }
    }
    return accumulate(st.begin(), st.end(), 0LL);
}

long long evalMax(const string& s) {
    vector st;
    long long cur = 0;
    char op = '*';
    for (size_t i = 0; i <= s.size(); ++i) {
        if (i < s.size() && isdigit(s[i])) {
            cur = cur * 10 + (s[i] - '0');
        } else {
            if (op == '*') st.push_back(cur);
            else if (op == '+') { st.back() += cur; }
            if (i < s.size()) op = s[i];
            cur = 0;
        }
    }
    long long prod = 1;
    for (long long v : st) prod *= v;
    return prod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    string s;
    while (T--) {
        cin >> s;
        cout << "The maximum and minimum are " << evalMax(s) << " and " << evalMin(s) << ".\n";
    }
    return 0;
}

關鍵測試用例

複雜度分析

總結

UVA 10700 是「表達式加括號極值」的經典題。核心洞察：最大值=加優先，最小值=乘優先。這將指數級的括號放置問題轉化為線性掃描棧模擬。掌握此結論，可秒殺同類問題（如 LeetCode 227 基礎計算器 II 的變體）。注意數據範圍：12 個數字最大 20，結果可能超 32 位，必須用 long long（64 位）。