在Java中解析算术表达式并从中构建树 [英] Parsing an arithmetic expression and building a tree from it in Java

问题描述

我需要一些帮助，在给定算术表达式的情况下创建自定义树。比如说，你输入这个算术表达式：

I needed some help with creating custom trees given an arithmetic expression. Say, for example, you input this arithmetic expression:

(5+2)*7

结果树应如下所示：

    *
   / \
  +   7
 / \
5   2

我有一些自定义类来表示不同类型的节点，即PlusOp，LeafInt等。我不需要评估表达式，只需创建树，所以我可以执行其他功能它以后。
此外，负数运算符' - '只能有一个子项，并且要表示'5-2'，您必须将其输入为5 +（ - 2）。

I have some custom classes to represent the different types of nodes, i.e. PlusOp, LeafInt, etc. I don't need to evaluate the expression, just create the tree, so I can perform other functions on it later. Additionally, the negative operator '-' can only have one child, and to represent '5-2', you must input it as 5 + (-2).

需要对表达式进行一些验证，以确保每种类型的运算符都具有正确的no。 of arguments / children，每个左括号都附有一个右括号。

Some validation on the expression would be required to ensure each type of operator has the correct the no. of arguments/children, each opening bracket is accompanied by a closing bracket.

另外，我应该提一下我的朋友已经编写了将输入字符串转换为堆栈的代码令牌，如果这会对此有所帮助。

Also, I should probably mention my friend has already written code which converts the input string into a stack of tokens, if that's going to be helpful for this.

我会感激任何帮助。谢谢：）

I'd appreciate any help at all. Thanks :)

（我读过你可以写一个语法并使用antlr / JavaCC等来创建解析树，但我不熟悉这些工具或者编写语法，所以如果这是你的解决方案，如果你能为他们提供一些有用的教程/链接，我将不胜感激。）

(I read that you can write a grammar and use antlr/JavaCC, etc. to create the parse tree, but I'm not familiar with these tools or with writing grammars, so if that's your solution, I'd be grateful if you could provide some helpful tutorials/links for them.)

推荐答案

五分钟介绍ANTLR包括算术语法示例。值得一试，特别是因为antlr是开源的（BSD许可证）。

The "Five minute introduction to ANTLR" includes an arithmetic grammar example. It's worth checking out, especially since antlr is open source (BSD license).

这篇关于在Java中解析算术表达式并从中构建树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！