高效的自动括号补全算法
我正在为文本编辑器编写自动括号完成功能，我当前的方法是在每个换行符上调用括号匹配过程（假设它是正确且有效的），其中最后键入的符号是开括号，从新行开始（使用最后在堆栈顶部键入的开括号）直到堆栈为空或到达源末尾且找不到匹配的闭括号。
然而，对于大源文件（> 1 MB），这种方法似乎很慢，特别是当在源行的前半部分添加换行符时（第一行换行符 = 最坏情况 = 扫描整个文本）。一些 IDE 具有此功能并且可以快速处理它，因此它们必须使用不同的方法。所以，我想知道他们使用什么算法或任何其他比我更好的方法。
I'm writing automatic bracket completion feature for a text editor, my current approach is to call a bracket matching procedure (assume it's correct and efficient) on every newline where the last typed symbol is the open bracket, starting from the new line (with that last typed open bracket on the top of the stack) until either the stack is empty or it comes to the end of the source with no matching close bracket found.
However, this approach seems to be slow for big source files (>1 MB), especially when the newline is added at the first half of the source lines (newline at first line = worst case = whole text is scanned). Some IDEs have this capability and could handle it fast, so they must be using different approach. So, I would like to know what algorithm they use or any other approach better than mine.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果匹配括号是一个重要问题，您可以仅使用括号的辅助数据结构来处理它。
例如，您可以构建一棵树，其中存储节点内一对括号的 begin_pos/end_pos ，并将所有括号对作为子节点。特别注意不匹配的括号（即它们在父母边界处开始/结束）。
添加额外的开/闭括号对于这种结构来说非常方便，因为您可以跳过所有子树和兄弟树。
适当的实现应该使用 O(log(n)) 解决方案，n 是括号对的数量。
If matching brackets is an important concern you can handle it using a secondary data structure for brackets alone.
E.g. you can build a tree which stores begin_pos/end_pos for a pair of brackets within a node and as children all pairs of brackets within. Take special care of non-matching brackets (i.e. they start/end at their parents boundaries).
Adding an extra open/close bracket is quite comfortable with such a structure since you can skip all child and sibling trees.
An appropriate implementation should perform with O(log(n)) solution, n being the number of pairs of brackets.