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

The result tree should look like:

    *
   / 
  +   7
 / 
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).

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 🙂

(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.)

Answer

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