Expression Trees

Objectives
  1. Learn how to parse an infix expression into a list of tokens.

  2. Convert a list of tokens from infix to postfix.

  3. Build a tree data structure to represent the expression.

  4. Traverse the tree in prefix, infix, and postfix order.

  5. Use the tree to evaluate the expression.

Getting Started

Create a project called P7 and import ExpressionTrees-starter.jar

Your directory should now look like this:

P7/
└── src
    ├── ATree.java
    ├── ExpressionTree.java
    └── TestCode.java
Directions

The following UML representation shows the structure of the classes you’ll be working with:

UML Diagram

This assignment covers tree building and tree traversal, in addition to conversion between prefix, infix, and postfix representations of expressions. The data structure is an expression tree, not a binary search tree as discussed in Chapter 25 of the Liang textbook. The lexical analysis involved in this assignment was previously done in a lab.

In the ExpressionTree class, implement the following methods (or their corresponding helper methods):

Testing

The TestCode class is provided for testing, and is similar to the code used for automated grading. It takes one command line parameter, which is the expression. You must place the expression in double quotes, for example "3*5+6/2" or "5-3+12/2*(9%5)". The test code calls all of the abstract methods in main. If you want, you can comment out or ignore methods that you have not yet implemented, to allow for incremental development. Here is an example output for the two expressions above:

For the expression "3*5+6/2":

Original Expression: 3*5+6/2
Infix Tokens: [3, *, 5, +, 6, /, 2]
Postfix Tokens: [3, 5, *, 6, 2, /, +]
Build: complete
Prefix: + * 3 5 / 6 2
Infix: ((3*5)+(6/2))
Postfix: 3 5 * 6 2 / +
Evaluate: 18
Display: complete

And here is the resulting expression tree:

expression one

For the expression "6 - 3 + 12 / 2 * (9 % 5)":

Original Expression: 6 - 3 + 12 / 2 * (9 % 5)
Infix Tokens: [6, -, 3, +, 12, /, 2, *, (, 9, %, 5, )]
Postfix Tokens: [6, 3, -, 12, 2, /, 9, 5, %, *, +]
Build: complete
Prefix: + - 6 3 * / 12 2 % 9 5
Infix: ((6-3)+((12/2)*(9%5)))
Postfix: 6 3 - 12 2 / 9 5 % * +
Evaluate: 27
Display: complete

And here is the resulting expression tree:

expression two
Specifications
  • Your program must meet the following specifications:

    • The code must produce the correct upload file and assertion messages.

    • Work on your own, as always.

    • You must submit the completed version of ExpressionTree.java.

    • Assignments should be implemented using Java 1.8.

    • Make sure your code runs on machines in the COMCS 120 lab.

    • Submit your program to the Checkin tab.

    • Read the syllabus for the late policy.

    • We will be checking programs for plagiarism, so please don’t copy from anyone else.

Grading Criteria
  • 100 points for perfect submission.

  • 0 points for no submission, will not compile, submitted class file, etc.

  • Preliminary Tests: no preliminary testing, use the test code provided!

  • Final Tests: final testing will use valid expression of our making.

    • testParse: Tests the parse method with two expressions. (15 points)

    • testConvert: Tests the convert method with two expressions. (25 points)

    • testBuild: Tests the build method with two expressions. (15 points)

    • testPrefix: Tests the prefix method with two expressions. (10 points)

    • testInfix: Tests the infix method with two expressions. (10 points)

    • testPostfix: Tests the postfix method with two expressions. (10 points)

    • testEvaluate: Tests the evaluate method with two expressions. (15 points)

Submission

Add a comment block with your name and email, and submit ExpressionTree.java to Checkin