高效的自动括号补全算法
提问于 2011-05-21 17:05:19
我正在为一个文本编辑器编写自动括号完成功能，我目前的方法是在最后键入的符号是左括号的每个新行上调用括号匹配过程(假设它是正确和有效的)，从新行(最后键入的左括号在堆栈的顶部)开始，直到堆栈为空或到达源代码的末尾，但没有找到匹配的闭括号。
但是，对于较大的源文件(>1MB)，这种方法似乎很慢，特别是在源行的前半部分添加换行符时(第一行换行符=最坏情况=整个文本被扫描)。一些IDE具有此功能，并且可以快速处理它，因此它们必须使用不同的方法。所以，我想知道他们使用的是什么算法，或者是否有比我更好的其他方法。
回答 1
Stack Overflow用户
发布于 2011-05-21 17:18:34
如果匹配括号是一个重要问题，您可以单独使用括号的辅助数据结构来处理它。
例如，您可以构建一个树，其中存储节点内一对括号的begin_pos/end_pos，以及作为子节点中的所有对括号。特别注意不匹配的括号(即它们在父代边界处开始/结束)。
添加一个额外的左/右括号对于这样的结构来说是非常舒服的，因为你可以跳过所有的子树和兄弟树。
一个适当的实现应该使用O(log(n))解来执行，n是括号对的数量。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/6083209
复制相关文章
腾讯云开发者
