Building and Displaying Trees

Objectives

  • Continue learning about parsing expressions by building an expression tree.

  • Play around with a graphical tool, GraphViz, which allows visualization of the trees that you are building.

  • Start the next assignment.

Getting Started

If you haven’t downloaded the jar for the ExpressionTrees assignment, complete the Getting Started section.

Conceptual Overview

Your lab instructor will explain the following:

Your lab instructor will also show you the Shunting-yard algorithm, but will not discuss it in detail.

Assignment Overview

This is an overview of what you need to complete for the assignment:

  • The parse method parses an arbitrary infix expression into a token list.

  • The convert method converts the infix tokens into a list in postfix order.

  • The build method builds a tree from the list in postfix order.

  • The prefix method traverses the tree to convert the expression to prefix order.

  • The infix method traverses the tree to convert the expression to infix order.

  • The postfix method traverses the tree to convert the expression to postfix order.

  • The evaluate method traverses the tree to evaluate the expression and compute the answer.

  • The display method traverses the tree and produces a graphical version of the tree.

You will be completing the parse and build methods during this recitation and then check your answers using Graphviz.

Step One

Copy the code from the previous lab on lexical analysis into the parse method in ExpressionTree.java. You should only need one of the methods, we suggest the method that uses the StringTokenizer.

Note
 Make sure to add the modulo operator to the list of delimiters.

Next, test this method with both of the expressions given in the assignment, matching white space exactly. The lab instructor will discuss running the test program.

Step Two

Do not implement the convert method yet. This is the main task associated with the assignment. Instead, hard-code the method to return an ArrayList in the correct postfix order:

return new ArrayList<String>(Arrays.asList("3", "5", "*", "6", "2", "/", "+"));
Step Three

Implement build and its recursive helper method. The basic idea is to build the expression tree in the correct order, as specified in the assignment.

Tip
 In the next part you will verify that your expression tree is built correctly by displaying it in a graphical manner. To begin, you might want to print each time you add a node, in order to convince yourself that the tree is built correctly.
Step Four

Expand the resources directory and open up FirstGraph.dot. This is an example of DOT file format that represents the expression "6 * 3". The file can be processed by the GraphViz tool to make a visual representation of the tree, in various formats.

For this recitation use webgraphviz to render the dot files and check your results.

  • Copy and paste the contents of FirstGraph.dot into the browser and click Generate Graph, you should see the following picture:

First Graph
Step Five

  • Look over the format of the FirstGraph dot file.

  • Once you feel like you have a good understanding, open SecondGraph.dot and replace the question marks (?) so that it creates the following expression:

"(6 * 3) + (7 / 2)"

Your graph should have three operator nodes (squares) named root, rootL, and rootR and four operand nodes (circles) named leafLL, leafLR, leafRL, and leafRR.

  • Once complete, paste your graph into the webgraphviz. It should generate the following image:

Second Graph
Step Six

Play around some more with shapes and colors. Here are some more resources:

Paste the contents of ThirdGraph.dot into the browser and see what it produces.

Now, run your code for the ExpressionTree assignment, this produces a .dot file named Graph.dot in the resources folder of your assignment. If you have constructed the expression tree correctly in the build method, then you should be able to make images from trees for arbitrary expressions.

Submission

To receive credit for this recitation, replace the code in your convert method to return this:

return new ArrayList<String>(Arrays.asList("10", "8", "2", "+", "*", "13", "32", "/", "5", "%", "-"));

then generate the graph and show it to your TA.

If you have already completed the entire assignment, generate the graph for: "10 * (8 + 2) - 13 / 32 % 5" instead.