3

私が次のような文字列を持っている場合

a/{b,c,d}/e

次に、この出力を生成できるようにします。

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

あなたはその考えを理解します。これをCで実装する必要があります。1組のブレースを解析できるブルートフォースのようなコードを作成しました（たとえば/a/{b,c,d}/e/、複数のブレースのペアが/a/{b,c}/{d,e}/fある場合、その場合のように、メソッドが機能しなくなります。Iより良いアプローチを取りたいと思います。

私はコードを直接求めているのではなく、効率的なアルゴリズムへのヒントで十分です。中括弧を解析するタスクは反復的であり、再帰的なアルゴリズムに従うことができると思いますか？

4

4 に答える 4

2

あらゆる種類のUnix、Linux、またはOS Xシステムを使用している場合は、これを行うための組み込みのライブラリ関数があります。 man 3 globCから呼び出す方法について説明します。または、http：//linux.die.net/man/3/globにアクセスしてオンラインドキュメントを見つけることもできます。

自分でロールしたい場合は、最初に文字列をスキャンして中間データ構造を構築し、次にそのデータ構造を再帰的に調べて文字列を印刷するのが簡単な方法です。そのデータ構造は、次のフィールドを持つ構造体から構築できます。

  • テキスト：文字列へのポインタ
  • next_node：印刷時にこのテキストの後に続くものへのポインタ
  • sibling_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"]はリーフノードを表し、一致する中括弧のペアは内部ノードを表します。内部ノードには2つのタイプがあり、1つは選択肢の1つ（{}この例で使用）から選択でき、もう1つはすべての組み合わせを組み合わせたもの（()ここで使用）です。

したがって、上記のツリーは次のようになります。

(
   ["/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 に答える