0

我正在努力将带括号的字符串转换为f(d(a c(b))e)Java 中的 Tree 数据结构（我正在研究一种允许使用字符串表示来实例化 Tree 的方法）。在上面的字符串中，f是树的根节点，它分支成一个子树 atd和一个叶节点 at e。在我能够识别f为当前节点的标签后，我剩下d(a c(b))e.

我希望能够使用 Java 的正则表达式来识别孩子；在这种情况下，d(a c(b))并且e。因此，要求如下。

在字符串中，单个字符后面可能有也可能没有括号。如果后面是括号，则返回里面的所有子字符串，即使它包含嵌套的括号。因此，正则表达式将匹配d(a c(b))or e。

此外，我希望它不仅仅适用于有两个孩子的节点。一个可能的带括号的字符串可能f(a b c)是一棵f以 3 片叶子为根的树。

到目前为止，我有.\(?[^\(\)]\)?，但这不起作用。

4

1 回答 1

4

使用正则表达式是不可能的，请参阅Can regular expressions are used to match nested patterns？

改用 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 ')'
    }
  }
}

（如果节点名称都是单个字符并且分隔符始终只是单个空格，则可以在没有 StreamTokenizer 的情况下编写稍微简单的递归解析代码）

于 2013-11-03T23:22:48.460 回答