java - 是否可以使用正则表达式在完全括号表示中查找树的根？

Question

我想找到一棵树的根，当它以完全括号的形式表示时，如下所示:

(s (A (B b)(C c))(D (E e)))

我已经尝试过这个:

(\(\s*(\S+)\s+(\([.^\)]*\))*\))

但它不匹配任何内容。我想提取 S 及其叶子，在本例中它们是 (A (B b)(C c))和(D (E e)) .

我猜完全括号形式不是正则表达式。我对吗？

Answer 1

问题

使用正则表达式无法解决此问题，因为您要使用它的字符串集不形成正则语言。这种语言在某种程度上相当于平衡括号语言，它是一种上下文无关语言。

解决方案

解决此问题的一种方法是使用上下文无关语法，但由于这不是标准 Java 功能(据我所知)，因此不建议在您的上下文中使用此策略。

更好的方法是使用堆栈(它为上下文无关语言提供了能力)。这个想法很简单:

parse the string from left to right
   create an empty stack
   if next char is '('
       throw it on the stack
   else if next char is ')'
       pop from stack
   if stack is empty
       current position is the root
       return substring from 0 to here as left leaves
       return substring from here to end as right leaves

这当然是伪代码。