用栈模拟匹配删除最内层括号对需记录左右括号索引,仅删合法配对部分;遍历中标记待删位置,最后构建新字符串避免erase性能损耗,推荐默认保留孤立括号。

用 stack 模拟匹配删除最内层括号对
直接删括号不等于简单 replace,因为括号是成对嵌套的,比如 "a(b(c)d)e" 里必须先删 "(c)",再删 "(b(c)d)",最后剩 "ae"。靠正则或多次 erase 会漏掉嵌套结构,得用栈记录左括号位置。
核心逻辑:遍历字符串,遇到 '(' 记下索引;遇到 ')' 且栈非空,则弹出一个 '(' 位置,标记这两个位置待删;最后一次性移除所有标记位置。
- 不要边遍历边
erase—— 索引会偏移,导致漏删或越界 - 标记用
vector<bool></bool>或set<size_t></size_t>都行,前者更快,后者易读 - 如果只删「合法配对」的括号(即忽略孤立括号),这个栈方法天然支持;若要删所有括号字符(不管是否配对),就退化为简单过滤
处理非法括号(不成对、反向顺序)时的行为选择
真实数据常含 "abc)def(" 这类乱序括号。此时栈为空却遇到 ')',或遍历完栈还有剩余 '(',就得决定怎么处理:
- 默认策略(推荐):只删能配对的部分,保留孤立括号 —— 符合多数业务场景,比如解析表达式前的预处理
- 强制全删:额外加两轮扫描,分别删所有剩余
'('和')',但会破坏原始语义,慎用 - 报错退出:在栈非空或遇右括号时抛
std::runtime_error,适合校验阶段
例如输入 "x(y)z(",按默认策略输出 "xyz(";若强制全删则输出 "xyz"。
立即学习“C++免费学习笔记(深入)”;
性能关键点:避免多次内存拷贝
std::string 的 erase 在中间删字符会触发后续内容平移,频繁调用很慢。最优做法是构建新字符串:
- 先收集所有需保留字符的索引(即未被标记的位置)
- 用
reserve()预分配目标容量 - 用
push_back()逐个追加,比反复erase快 3–5 倍(尤其长字符串)
示例片段:
std::string result; result.reserve(s.size()); for (size_t i = 0; i < s.size(); ++i) { if (!to_remove[i]) result.push_back(s[i]); }
要不要用正则?std::regex 在这里不适用
有人想用 std::regex_replace(s, std::regex(R"(\([^()]*\))"), "") 循环替换,但这只能删最内层且无嵌套的括号,像 "((a))" 第一轮变 "(())",第二轮才变 "",效率低且不可控。
-
std::regex不支持递归匹配,C++20 也没补上 - 每次替换都重建字符串,时间复杂度接近 O(n²)
- 编译正则本身有开销,短字符串反而更慢
真要正则方案,得用 PCRE 或 Boost.Regex 写递归模式,但引入依赖+学习成本远超手写栈。
栈处理嵌套结构这事,边界条件比看起来多——比如空字符串、全括号、连续嵌套深度超过千层,实际跑时记得测下stack 容量和迭代器稳定性。


















