parsing一个算术expression式,并用Java构build一个树

给定一个算术expression式,我需要一些帮助来创build自定义。 比方说,你input这个算术expression式:

(5+2)*7 

结果树应该如下所示:

  * / \ + 7 / \ 5 2 

我有一些自定义类来表示不同types的节点,即PlusOp,LeafInt等。我不需要评估expression式,只需创build树,以便稍后可以执行其他function。 此外,否定运算符“ – ”只能有一个孩子,要表示“5-2”,则必须input5 +(-2)。

需要对expression式进行一些validation,以确保每种types的操作符都具有正确的编号。 的参数/孩子,每个开放括号附有一个右括号。

此外,我应该提到我的朋友已经写了代码,将inputstring转换成一个令牌堆栈,如果这将是有益的。

我将不胜感激任何帮助。 谢谢 :)

(我读过,你可以写一个语法,并使用antlr / JavaCC等来创build分析树,但我不熟悉这些工具或编写语法,所以如果这是你的解决scheme,我会很感激,如果你可以为他们提供一些有用的教程/链接。)

5 Solutions collect form web for “parsing一个算术expression式,并用Java构build一个树”

“五分钟ANTLR简介”包括一个算术文法的例子。 值得一提的是,特别是因为antlr是开源的(BSD许可证)。

假设这是一些功课,你想自己做。

我做了一次,你需要一个堆栈

那么你为这个例子做的是:

    parsing做什么? 堆栈看起来像
       (推到堆栈上(
       5推5(,5
       +推+(,5,+
       2推2(,5,+,2
       )评估,直到(7            
       *推* 7,*
       7推7 + 7,*,7
       eof评估,直到前49

像“5”或“+”这样的符号可以存储为string或简单对象,也可以将+存储为+()对象,而无需设置值并在评估时进行设置。

我想这也需要一个优先顺序,所以我会描述这是如何工作的。

在5 + 2 * 7的情况下

你必须推5 push +推2下op是更高的优先,所以你推它,然后推三。 当遇到a)或者文件结尾或者优先级较低或者相等的操作符时,你开始计算堆栈到前一个(或者文件的开始)。

因为你的堆栈现在包含5 + 2 * 7,所以当你评估它时,首先popup2 * 7,然后将得到的*(2,7)节点推入堆栈,然后再一次评估堆栈中的前三个事物5 + *节点),所以树出来正确。

如果是以另一种方式命令:5 * 2 + 7,你会推到你有一个“5 * 2”的堆栈,那么你会击中较低的优先级+这意味着评估你现在有什么。 你将评估5 * 2到一个*节点并推动它,然后你将继续推+和3,所以你有*节点+7,在这一点上,你会评估。

这意味着你有一个“最高当前优先”variables,当你按+/-时存储1,当你按下*时为2,或者为^时为3。 这样你可以testingvariables来查看你的下一个运算符的优先级是否是你的当前优先级。

如果“)”被认为是优先级4,你可以把它看作是其他的操作符,除了删除匹配的“(”,低优先级不会。

我想回应比尔K.的答案,但我缺乏在那里添加评论的声望(这真的是这个答案所属的地方)。 你可以把这看作比尔·K的答案的补充,因为他有点不完整。 缺less的考虑是操作员的联想性 ; 即如何parsingexpression式,如:

 49 / 7 / 7 

根据分割是左或右关联,答案是:

 49 / (7 / 7) => 49 / 1 => 49 

要么

 (49 / 7) / 7 => 7 / 7 => 1 

典型地,分割和减法被认为是左联合的(即情况2,以上),而指数是正确的联想。 因此,当你遇到一系列具有相同优先级的运算符时,如果它们是左关联的,或者如果是右关联的,则要按顺序parsing它们。 这只是决定你是在推送还是popup到堆栈,所以它不会使给定的algorithm过度复杂,它只是为连续运算符具有相同优先级时添加了一些情况(即,如果是左关联,则评估堆栈,如果是右关联则推入堆栈) 。

几个选项给你:

  1. 重新使用现有的expression式parsing器。 如果你在语法和语义方面灵活的话,那将是有效的。 我推荐的一个好的是Java中内置的统一expression式语言(最初用于JSP和JSF文件)。

  2. 从头开始编写你自己的parsing器。 有一个明确的方式来编写一个parsing器,考虑到运算符的优先顺序等。描述完成如何做是超出了这个答案的范围。 如果你走这条路,找一本关于编译器devise的好书。 语言分析理论将在前几章中介绍。 通常情况下,expression式parsing就是其中一个例子。

  3. 使用JavaCC或ANTLR生成词法分析器和分析器。 我更喜欢JavaCC,但每个人都是自己的。 只是谷歌“javacc样本”或“antlr样本”。 你会发现很多。

在2到3之间,即使你必须学习新技术,我也强烈推荐3。 parsing器生成器已经创build是有原因的。

另外请注意,创build一个可以处理格式错误的input的parsing器(不仅仅是parsingexception失败)比编写只接受有效input的parsing器复杂得多。 你基本上必须编写一个语法来阐明各种常见的语法错误。

更新:下面是使用JavaCC编写的expression式语言parsing器的示例。 语法松散地基于统一expression式语言。 它应该给你一个相当好的主意,你是什么反对。

org.eclipse.sapphire / plugins / org.eclipse.sapphire.modeling / src / org / eclipse / sapphire / modeling / el / parser / internal / ExpressionLanguageParser.jj的内容

给定的expression式(5 + 2)* 7我们可以作为中缀

 Infix : (5+2)*7 Prefix : *+527 

从上面我们知道树的序列和序列…我们可以很容易地从这里构造树。 谢谢,

  • ADL的陷阱是什么?
  • 如何parsingISO 8601格式的date?
  • 按列sortingcsv
  • HTMLparsing如果不使用正则expression式,如何工作?
  • 无法从程序集中加载“SlowCheetah.Xdt.TransformXml”任务
  • 为什么要添加一个方法添加一个模糊的调用,如果它不会涉及到模糊性
  • 使用C#正则expression式删除HTML标记
  • 如何parsing和处理PHP中的HTML / XML?
  • 如何在Linux中使用单行命令获取Java版本
  • PHP的CSVstring到数组
  • Scala PackratParser忽略失败分析器