0

如果我有一个字符串如下

( (a || b) && c) || (d && e)

如何根据括号将它们拆分为不同的字符串并形成这样的树？

         ( (a || b) && c) || (d && e)  ---> Root

               /                \
              /                  \
           ( (a|| b) || c)      (d && e)
           /           \             /  \             
          /             \            /   \
         (a || b)        c           d    e
4

3 回答 3

1

你需要一个解析树生成器。对于繁重的工作，许多人使用ANTLR，但对于简单的语法，我在 JavaCC 和JJTree方面取得了很好的成功

于 2013-08-04T13:41:59.777 回答
0

您提出的问题可能属于计算机科学的解析器和形式语言分支。

可以使用 lex 和 yacc 等工具生成基于任意字符串的任意语法的解析器程序。

Lex 是一个词法分析程序生成工具，它将一个文本文件作为输入，该文本文件将语法的词法规则定义为正则表达式，并输出一个程序，该程序能够从您在规则中定义的任意输入字符串中识别标记。

Yacc 是一个语法解析器程序生成工具，它接受一个词法分析器作为输入，一个表示您的语言语法的文本文件（在您的情况下，这将是一个类似表达式的语法），并输出一个名为parser的程序，它将是能够将您的表达式字符串转换为您提到的树（即将字符串解析为解析树）。

Yacc 和 lex 可以很容易地一起使用来生成一个解析器程序，该程序基于所谓的语义动作创建一个解析树，您可以使用它指示解析器以您想要的方式构建树。

我建议您将以下内容作为介绍性阅读： http ://epaperpress.com/lexandyacc/

如果您对此事感兴趣，更具挑战性的阅读将是： http ://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811/ref=pd_sim_b_9

Yacc 和 Lex 仅用于 C 语言，Java 存在等效工具。我最喜欢的 java 解析器生成器工具是： http: //goldparser.org/

于 2013-08-04T13:53:14.137 回答
0

我将评论问题的另一部分，

...并形成一棵这样的树。

如果您真的打算将其打印为输出，您会发现它很棘手。

随着您了解有关解析的更多信息，您会发现您将操作一个堆栈，该堆栈包含以前读取但尚未处理的输入标记的值。如果您使用递归机制，堆栈将是隐式的，或者如果您使用迭代方法并自己管理堆栈，它可能是显式的。对于简单的运算符优先级解析器，后者将是一种常见的实现。

所以，我的建议是你创建一个StringBuilders 列表。这与堆栈平行。也就是说，stringBuilderList.get(3)将与yourStack.get(3)等相关联。

现在，当您执行一些操作（例如归约( a )到）时，您将在与当前堆栈级别对应a的项目中附加一个合适的字符串。stringBuilderList

现在，在您担心之前，对您的报价的另一种解释就是以标准方式智能地解析输入，括号中的项目首先被处理，等等。我建议您澄清一下您的要求。

于 2013-08-04T15:08:48.097 回答