top1编程
← 返回题目
题解

【提高】删除多余括号

1 条题解

  • 0
    @ 2026-7-29 0:17:48
    #include <iostream>
    #include <stack>
    #include <string>
    #include <vector>
    #include <unordered_map>
    
    using namespace std;
    
    string removeExtraParentheses(string s) {
        unordered_map<char, int> prio;
        prio['+'] = 1;
        prio['-'] = 1;
        prio['*'] = 2;
        prio['/'] = 2;
    
        stack<pair<int, bool> > st;
        vector<bool> toDel(s.size(), false);
    
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                bool needFlip = (i > 0 && s[i-1] == '-');
                st.push(make_pair(i, needFlip));
            } else if (s[i] == ')') {
                if (st.empty()) continue;
                
                int l = st.top().first;
                bool needFlip = st.top().second;
                st.pop();
    
                char innerOp = 0;
                for (int j = l+1; j < i; ++j) {
                    if (prio.find(s[j]) != prio.end()) {
                        innerOp = s[j];
                        break;
                    }
                }
                if (innerOp == 0) {
                    toDel[l] = true;
                    toDel[i] = true;
                    continue;
                }
    
                char leftOp = 0, rightOp = 0;
                int j = l-1;
                while (j >= 0 && (isalpha(s[j]) || s[j] == ')')) --j;
                if (j >= 0) leftOp = s[j];
    
                j = i+1;
                while (j < s.size() && (isalpha(s[j]) || s[j] == '(')) ++j;
                if (j < s.size()) rightOp = s[j];
    
                // 核心规则:
                // 1. *// 包裹 +- → 保留括号(如 (a+b)*f、a/(b+c))
                // 2. - 包裹 +- → 保留括号(如 a-(b+c),不再展开)
                // 3. 其他情况 → 删除括号
                bool needKeep = false;
                // 保护 *// 包裹 +-
                if ((leftOp == '*' || leftOp == '/') && (innerOp == '+' || innerOp == '-')) needKeep = true;
                if ((rightOp == '*' || rightOp == '/') && (innerOp == '+' || innerOp == '-')) needKeep = true;
                // 保护 - 包裹 +-(新增!)
                if (leftOp == '-' && (innerOp == '+' || innerOp == '-')) needKeep = true;
    
                if (!needKeep) {
                    toDel[l] = true;
                    toDel[i] = true;
                    // 仅在非保护括号时才翻转符号(现在只有纯变量/同级运算符会触发)
                    if (needFlip && !needKeep) {
                        for (int k = l+1; k < i; ++k) {
                            if (s[k] == '+') s[k] = '-';
                            else if (s[k] == '-') s[k] = '+';
                        }
                    }
                }
            }
        }
    
        string res;
        for (int i = 0; i < s.size(); ++i) {
            if (toDel[i]) continue;
            res += s[i];
        }
    
        // 仅删除最外层完全包裹的括号
        while (res.size() >= 2 && res[0] == '(' && res.back() == ')') {
            int cnt = 0;
            bool canDel = true;
            for (int i = 0; i < res.size(); ++i) {
                if (res[i] == '(') cnt++;
                else if (res[i] == ')') cnt--;
                if (cnt == 0 && i != res.size()-1) {
                    canDel = false;
                    break;
                }
            }
            if (canDel) res = res.substr(1, res.size()-2);
            else break;
        }
    
        return res;
    }
    
    int main() {
        string expr;
        cin >> expr;
        cout << removeExtraParentheses(expr) << endl;
        return 0;
    }
    
    • 1