Uva11890 - Calculus Simplified

題目大意

題目給予多元一次多項式，並給予未知數的可能數，並要我們求出此多項式的最大可能值為多少

重點觀念

• stack?

分析

• 把多項式平攤開來

程式題目碼

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

pair<int, int> process(string s) {
    vector<char> stack;
    pair<int, int> p;
    bool post = true;
    p.first = 0;
    p.second = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'x') {
            bool positive = post;
            if (i - 1 >= 0) {
                if (s[i - 1] == '-') {
                    positive = !positive;
                }
            }
            if (positive) {
                p.first += 1;
            } else {
                p.second += 1;
            }
        }
        if (s[i] == '(') {
            if (i == 0) {
                stack.push_back('+');
            } else {
                if (s[i - 1] == '-') {
                    post = !post;
                }
                stack.push_back(s[i - 1]);
            }
        }
        if (s[i] == ')') {
            if (stack.back() == '-') {
                post = !post;
            }
            stack.pop_back();
        }
    }

    return p;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, a + n);

        pair<int, int> p = process(s);

        int ans = 0;
        for (int i = 0; i < p.second; i++) {
            ans -= a[i];
        }

        for (int i = 0; i < p.first; i++) {
            ans += a[n - 1 - i];
        }

        cout << ans << endl;
    }

    return 0;
}