题解
【提高】删除多余括号
1 条题解
-
0
#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