C++怎么实现括号匹配检查_C++栈数据结构示例【详解】

1次阅读

用std::stack检查括号匹配需确保:遇左括号压,遇右括号先判栈非空再比对弹出;用unordered_map映射右括号到左括号;过滤非法字符和空白;结尾栈必须为空。

C++怎么实现括号匹配检查_C++栈数据结构示例【详解】

std::stack 检查括号是否匹配最直接

不用自己手写栈,std::stack 就够用。它底层默认用 std::deque,增删都是 O(1),且不暴露内部结构,避免误操作。

关键不是“能不能用栈”,而是「遇到左括号就压入,遇到右括号就弹出比对」这个逻辑是否严谨。常见错误是只检查栈非空就弹出,结果栈空时调用 top()pop()——这会触发未定义行为,Debug 模式下可能崩溃,Release 下静默出错。

  • 每读一个字符,如果是 '(''{''[',就 push 进栈
  • 如果是 ')''}'']',先检查栈是否为空;空则直接返回 false
  • 非空时,用 top() 取栈顶,和当前右括号配对;不匹配就 return false,匹配则 pop()
  • 字符串扫完后,栈必须为空才算完全匹配(防止 “(((” 这种漏判)

字符配对别硬编码 if-else,用 std::unordered_map 更清晰

手写三组 if (c == ')' && last != '(') 容易漏条件、难维护。映射右括号到对应左括号,逻辑一目了然,也方便后续扩展(比如加尖括号 )。

注意:std::unordered_map 查找是平均 O(1),比线性查找安全;但别用 map,它多一层 log N 开销,这里没必要。

立即学习C++免费学习笔记(深入)”;

std::unordered_map<char, char> pairs = {     {')', '('},     {'}', '{'},     {']', '['} };
  • 遍历到右括号 c 时,先查 pairs.count(c) 确认它是合法右括号
  • 再用 pairs[c] 拿期望的左括号,和 stack.top() 比较
  • 别在 map 里塞左括号做 key——那样查的是“哪个右括号配我”,方向反了

输入含非法字符时要提前拒绝

很多实现默认只处理四类括号,但实际输入可能是带字母、数字、空格甚至中文的表达式。如果忽略非法字符,可能把 "a(b[c]d)e" 当作合法——它确实括号匹配,但业务上未必接受非括号字符。

取决于需求:若只要求“括号结构正确”,可跳过非括号字符;若要求“仅含括号”,就得在循环里加校验。

  • if (c != '(' && c != ')' && c != '{' && ...) 判断太啰嗦
  • 建议建一个 std::unordered_set<char> 存所有合法括号字符,用 valid_chars.find(c) == valid_chars.end() 判非法
  • 一旦发现非法字符,立刻 return false(或按需抛异常)

别忘了空字符串和全空格输入的边界情况

空字符串 "" 是合法匹配(栈初始为空,最后也为空);但带空格的 " " 如果没过滤,会进主循环体并触发非法字符判断——这时候行为取决于你是否允许空白。

常见坑:用 std::getline 读输入后,忘记 std::String::find_first_not_of(" tnr") == std::string::npos 去判断是否真为空内容。

  • 建议在主逻辑前统一 trim 字符串,或在循环中跳过空白(std::isspace(c)
  • 如果输入来自文件或网络,还可能有 bom、控制字符,isspace 不覆盖全部,需按需增强
  • 测试用例至少覆盖:""" ""()"")(""([)]""((("

括号匹配看着简单,真正鲁棒的实现得同时盯住栈空状态、字符合法性、配对映射、以及输入清洗这几个点。少一个,线上跑着跑着就崩在奇怪的地方。

text=ZqhQzanResources