数据结构与算法 / 编辑器和编译器如何判定括号是否合法

一、整体思路

使用栈这种数据结构。

遍历字符串，遇到左括号则入栈，遇到右括号则判断此时的栈顶的括号是否和右括号对应，如果是则 pop 栈顶；如果不是则直接可以判定该字符串中括号不匹配。

二、栗子

#include 
#include 
#include char leftOf(char c);bool isValid(std::string str)
{std::stack left;for (char c : str){if (c == '(' || c == '{' || c == '[')left.push(c);else // 字符 c 是右括号if (!left.empty() && leftOf(c) == left.top())left.pop();else// 和最近的左括号不匹配return false;}// 是否所有的左括号都被匹配了return left.empty();
}char leftOf(char c)
{if (c == '}')return '{';if (c == ')')return '(';return '[';
}void show(const std::string &str)
{if (isValid(str))std::cout << "合法" << std::endl;elsestd::cout << "不合法" << std::endl;return;
}int main()
{show("{()}");show("{()[]])");return 0;
}

合法
不合法

代码参考：https://zhuanlan.zhihu.com/p/107788052

（SAW：Game Over！）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！