Cho*_*ear 38 java tree parsing
给定一个算术表达式,我需要一些创建自定义树的帮助.比如说,您输入此算术表达式:
(5+2)*7
结果树应如下所示:
*
/ \
+ 7
/ \
5 2
我有一些自定义类来表示不同类型的节点,即PlusOp,LeafInt等.我不需要评估表达式,只需创建树,所以我可以在以后执行其他功能.此外,否定运算符' - '只能有一个子节点,并且要表示'5-2',您必须将其输入为5 +( - 2).
需要对表达式进行一些验证,以确保每种类型的运算符都具有正确的no.参数/儿童,每个开口括号都附有一个结束括号.
另外,我应该提一下,我的朋友已经编写了将输入字符串转换为一堆标记的代码,如果这对此有帮助的话.
我会感激任何帮助.谢谢 :)
(我读过你可以编写一个语法并使用antlr/JavaCC等来创建解析树,但我不熟悉这些工具或编写语法,所以如果这是你的解决方案,我将不胜感激,如果你可以为他们提供一些有用的教程/链接.)
Bil*_*l K 49
假设这是某种功课,你想自己做.
我做了一次,你需要一个堆栈
所以你为这个例子做的是:
parse what to do? Stack looks like
( push it onto the stack (
5 push 5 (, 5
+ push + (, 5, +
2 push 2 (, 5, +, 2
) evaluate until ( 7
* push * 7, *
7 push 7 +7, *, 7
eof evaluate until top 49
像"5"或"+"这样的符号可以存储为字符串或简单对象,或者您可以将+存储为+()对象而不设置值,并在评估时设置它们.
我认为这也需要一个优先顺序,所以我将描述它是如何工作的.
在:5 + 2*7的情况下
你必须推5推+推2下一个优先级更高,所以你也推它,然后推三个.当您遇到a)或文件结尾或优先级较低或相同的运算符时,您开始计算堆栈到前一个(或文件的开头).
因为您的堆栈现在包含5 + 2*7,所以当您评估它时,首先弹出2*7并将生成的*(2,7)节点推入堆栈,然后再次评估堆栈中的前三项( 5 +*节点)所以树出来是正确的.
如果它是以另一种方式订购的:5*2 + 7,你会推动直到你得到一个"5*2"的堆栈然后你会达到较低的优先级+这意味着评估你现在得到的.你将5*2评估成一个*节点并推送它,然后你继续推动+和3,这样你就得到了*node + 7,此时你就可以评估它了.
这意味着你有一个"最高当前优先级"变量,当你按下+/-时存储1,当你按*或/和3时为"^"时存储2.这样您就可以测试变量,看看下一个运算符的优先级是否<=您当前的优先级.
如果")"被认为是优先级4,则可以将其视为其他运算符,除非它删除匹配的"(",较低的优先级不会.
小智 13
我想回答Bill K.的答案,但我缺乏在那里添加评论的声誉(这真的是这个答案所属的地方).您可以将此视为Bill K.答案的附录,因为他有点不完整.缺少的考虑因素是运营商的相关性 ; 即,如何解析如下表达式:
49 / 7 / 7
根据是否为左或右关联,答案是:
49 / (7 / 7) => 49 / 1 => 49
要么
(49 / 7) / 7 => 7 / 7 => 1
通常,除法和减法被认为是左关联的(即上面的情况二),而取幂是右关联的.因此,当您遇到具有相同优先级的一系列运算符时,如果它们是关联的,则需要按顺序解析它们,如果是右关联的,则按顺序解析它们.这只是决定你是推送还是弹出堆栈,所以它不会使给定的算法过于复杂,它只是为连续运算符具有相同优先级时添加的情况(即如果左关联则评估堆栈,如果是右关联则推送到堆栈) .
所述"五分钟的介绍ANTLR"包括算术语法例子.值得一试,特别是因为antlr是开源的(BSD许可证).