0

Javaのツリーデータ構造などに括弧で囲まれた文字列を変換する作業を行っていf(d(a c(b))e)ます(文字列表現を使用してツリーをインスタンス化できるようにする方法に取り組んでいます)。上記の文字列では、 はツリーのルート ノードであり、サブツリー atとリーフ ノード atfに分岐します。現在のノードのラベルとして識別できた後、 .defd(a c(b))e

Java の正規表現を使用して子を識別できるようにしたいと考えています。この場合、d(a c(b))およびe. したがって、要件は次のとおりです。

文字列では、単一の文字の後に括弧が続く場合とそうでない場合があります。括弧が続く場合は、ネストされた括弧が含まれていても、内部のすべての部分文字列を返します。したがって、正規表現はd(a c(b))orに一致しeます。

さらに、これが 2 つの子を持つノードだけでなく、複数のノードでも機能するようにしたいと考えています。括弧で囲まれた可能性のある文字列は、3 つのリーフをf(a b c)ルートとするツリーである可能性があります。f

これまでのところ、私は持っています.\(?[^\(\)]\)?が、これは機能しません。

4

1 に答える 1

4

正規表現では不可能です。正規表現を使用してネストされたパターンに一致させることができますか? を参照してください。

代わりに StreamTokenizer と再帰を使用すると、次のようになります (未テスト)。

public class Node {
  private String name;
  private ArrayList<Node> children = new ArrayList<Node>();

  public static Node parseTree(String s) throws IOException {
    StreamTokenizer tokenizer = new StreamTokenizer(new StringReader(s));
    tokenizer.nextToken();                 // Move to first token
    Node result = new Node(tokenizer);     // Parse root node (and children)
    if (tokenizer.ttype != StreamTokenizer.TT_EOF) {
      throw new RuntimeException("Leftover token: "+ tokenizer.ttype);
    }
    return result;
  }

  Node(StreamTokenizer tokenizer) throws IOException {
    if (tokenizer.ttype != StreamTokenizer.TT_WORD) {
      throw new RuntimeException("identifier expected; got: " + tokenizer.ttype);
    }
    name = tokenizer.sval;                  // read then name 
    if (tokenizer.nextToken() == '(') {     // Consume the name and check for Children
      tokenizer.nextToken();                // Yes, consume '('
      do {
        children.add(new Node(tokenizer));  // Add and parse a child
      } while (tokenizer.ttype != ')');     // Until we reach ')'
      tokenizer.nextToken();                // Consume ')'
    }
  }
}

(ノード名がすべて 1 文字で、区切り文字が常に 1 つのスペースである場合、StreamTokenizer を使用せずに、少し単純な再帰的解析コードを作成することができます)

于 2013-11-03T23:22:48.460 に答える