3

如果我有一个字符串

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在这种情况下我的方法会中断。我想采取更好的方法。

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

4

4 回答 4

2

如果你在任何类型的 Unix、Linux 或 OS X 系统上，都有一个内置的库函数可以做到这一点。 man 3 glob将告诉您如何从 C 中调用它。或者您可以访问http://linux.die.net/man/3/glob以查找在线文档。

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

  • text：指向一段字符串的指针
  • next_node：指向打印时此文本之后的内容的指针
  • 兄弟节点：指向可以做出的下一个选择而不是这个选择的指针
于 2011-06-03T17:52:28.010 回答
2

你在这里展示的并不是真正的递归。如果您可以嵌套括号，那么这将是递归的。

基本上你所拥有的是一个简单的语法：

thing ::= element { "/" element }*
element ::= symbol || list
list ::= "{" symbol { "," symbol }* "}"
symbol ::= [a-z]+

那是一种即兴的语法语言。* 表示“零个或多个”，+ 表示“1 个或多个”。很常见。

因此，您需要一个简单的标记器，它可以将符号分组并主要分离标点符号。

然后是一个简单的解析器

parseThing() {
    Element e = parseElement();
    while (nextToken != null) {
        Slash s = parseSlash();
        e = parseElement():
    }
}

Slash parseSlash() {
    Token t = peekNextToken();
    if (t.getText().equals("/")) {
        return new Slash();
    }
    throw "expected a '/' but got a " + t;
}

Element parseElement() {
    Token t = peekNextToken();
    if (t.isSymbol()) {
        return parseSymbol();
    }
    if (t.isOpenCurly()) {
        return parseList());
    }
    thrown "Syntax error, wanted a symbol or { and got " + t;
}

List parseList() {
    List l = new List();
    Token t = peekNextToken();
    if (t.isOpenCurly()) {
        consumeNextToken();
        Symbol s = parseSymbol();
        l.add(s);
        t = peekNextToken();
        while (t.isComma()) {
            consumeNextToken();
            s = parseSymbol();
            l.add(s);
            t = peekNextToken();
        }
        if (!t.closeCurly()) {
            throw "expected close of list, but got " + t;
        }
        consumeNextToken();
     } else {
         throw "expected start of list but got " + t;
     }
     return l;
}

Symbol parseSymbol() {
    Token t = peekNextToken();

    if(!t.isSymbol()) {
        throw "expected symbol, got " + t;
    }
    consumeNextToken();
    return new Symbol(t);
}

这是不完整的，高层次的，但让你知道如何去做。

于 2011-06-03T18:44:03.740 回答
1

我最近一直在做这样的事情，我花了很多时间来解决这个问题，所以这就是我的做法。不过，可能有一个更简单的算法。

您可以编写递归下降解析器将文本转换为树。使包含该字符串的字符串叶节点和匹配的大括号对成为内部节点。每个叶节点可以包含多个字符串。

例如，这个：

/a/{b,c}/{d,e{f,g,h}}/i

可以变成：

(
   ["/a/"]
   {
      ( ["b"] )
      ( ["c"] )
   }
   ["/"]
   {
      ( ["d"] )
      (
         ["e"]
         {
            ( ["f"] )
            ( ["g"] )
            ( ["h"] )
         }
      )
   }
   ["i"]
)

尝试将其视为一棵树，其中["stringA", "stringB"]表示叶节点，匹配的大括号对表示内部节点。有两种类型的内部节点，一种可以在其中一种选择之间进行选择（我{}在这个例子中使用），另一种可以结合所有组合（我()在这里使用）。

所以，上面的树会是这样的：

(
   ["/a/"]
   {
      ["b"]
      ["c"]
   }
   ["/"]
   {
      ["d"]
      (
         ["e"]
         {
            ["f"]
            ["g"]
            ["h"]
         }
      )
   }
   ["i"]
)

然后

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   {
      ["d"]
      (
         ["e"]
         ["f", "g", "h"]
      )
   }
   ["i"]
)

然后

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   {
      ["d"]
      ["ef", "eg", "eh"]
   }
   ["i"]
)

然后

(
   ["/a/"]
   ["b", "c"]
   ["/"]
   ["d", "ef", "eg", "eh"]
   ["i"]
)

最后，你最终得到一个叶子节点，这是所有的组合：

["/a/b/di", "/a/b/efi", "/a/b/egi", "/a/b/ehi",
 "/a/c/di", "/a/c/efi", "/a/c/egi", "/a/c/ehi"]

然后你可以漂亮地打印它。

于 2011-06-03T18:43:53.413 回答
0

不知道效率如何，但一种直观的方法是使用某种形式的递归。该函数应该能够找到第一个大括号。假设第一个大括号包含 N 个选项。因此该函数产生 N 次扩展，并在每次扩展时递归调用自身。每个“叉子”都会继续叉子，直到用尽每个支架。

这有帮助吗？

于 2011-06-03T17:48:53.590 回答