c - BASH/CSH/ZSH 样式大括号扩展算法

Question

如果我有一个像

这样的字符串

a/{b,c,d}/e

然后我希望能够产生这个输出:

a/b/e
a/c/e
a/d/e

你明白了。我需要在 C 中实现它。我编写了一种强力代码，我能够解析一对大括号(例如:/a/{b,c,d}/e/ 但是如果有多对大括号，比如 /a/{b,c}/{d,e}/f 在这种情况下我的方法就会失效。我想采用更好的方法.

我不是直接要求代码，只是对高效算法的提示就足够了。我认为解析大括号的任务是重复的，我们可以遵循递归算法吗？

Answer 1

如果您使用的是任何类型的 Unix、Linux 或 OS X 系统，都有一个内置的库函数可以执行此操作。 man 3 glob 会告诉你如何从 C 调用它。或者你可以访问 http://linux.die.net/man/3/glob查找在线文档。

如果您想自己动手，一个简单的方法是首先扫描字符串并构建一个中间数据结构，然后递归遍历该数据结构，打印字符串。该数据结构可以由具有以下字段的结构构建:

• 文本:指向一段字符串的指针
• next_node:指向打印时此文本之后的内容的指针
• sibling_node:指向下一个可以做出的选择而不是这个的指针