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

Configure the project with JUnit 5, go here for instructions.

Your directory should now look like this:

P7/
└── src
    ├── ATree.java
    ├── ExpressionTree.java
    └── P7_Unit_Testing.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 P7_Unit_Testing class is provided for testing, and is similar to the code used for automated grading. Make sure to read through the provided tests to understand how these methods interact with each other. You are encouraged to write more tests than are provided to practice with the code you have written and unit testing in general. If you run into bugs in your program, use the debugger to understand what your program is actually doing.

The unit tests provided are rudimentary and may not cover every case. That’s your job to finish. It’s suggested that you test with more complex expressions to make sure your code works for all cases. Looking at the code coverage of your tests is also a great way to make sure you havn’t missed any cases.

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