Expression Trees with a Symbol Table

Objectives

  1. Implement a symbol table (in the form of a binary tree) to add and look up variables

  2. Integrate the symbol table into the expression tree to evaluate an expression.

Getting Started

Create a project called P8 and import ExpressionTreeExtended-starter.jar

Copy ExpressionTree.java from P7 into your P8 project.

Note
 If you did not receive full credit on the previous assignment make sure to correct your code before turning this assignment in.

Your directory should now look like this:

P8/
└── src
    ├── ATree.java
    ├── ExpressionTree.java
    ├── ExpressionTreeExpanded.java
    ├── Shell.java
    └── SymbolTable.java
Introduction

In P7 you created a project that evaluates operations between two integers, now it’s time to expand this idea one step farther. This assignment adds a symbol table in the form of a binary search tree.

In a Compiler, the symbol table records information about each symbol name in a program. Historically, names were called symbols, and hence we talk about a symbol table rather than a name table.

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

UML Diagram
Directions

Complete the following methods:

  1. The performOperation method in the ExpressionTreeExpanded class

  2. The valueOfExpanded method in the ExpressionTreeExpanded class

  3. The isValidJavaIdentifier method in the SymbolTable class

  4. The put method in the SymbolTable class

  5. The get method in the SymbolTable class

  6. The inorderRecursive method in the SymbolTable class

Testing

We have provided starter code for testing in the SymbolTable class so that you can make sure that you’re adding and getting nodes correctly. Here is the code:

main

And here is what your output should look like:

output

These are just sanity tests. You should think about what could go wrong and change the code in the main to test different scenarios. You should also test your get method here.

Once you feel certain about about your SymbolTable. Run the main method in Shell.java. This runs an infinite loop letting you play around with expressions. Here’s an example:

console output
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.

    • Submit ExpressionTree.java, ExpressionTreeExpanded.java and SymbolTree.java in P8.jar.

    • 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.

    • testperformOperation: Tests to make sure operations are performed correctly. (5 points)

    • testvalueOfExpanded: Tests that the valueOf method still parses Integers correctly. (5 points)

    • testjavaIdentifier: Tests to make sure only valid Java identifiers return true. (15 points)

    • testSinglePutandGet: Tests the put method in SymbolTree. (20 points)

    • testMulitplePutAndGet: Tests the put and get methods with multiple method calls in SymbolTree. (20 points)

    • testInorderTraversal: Tests to make sure put and inorder traversal work (10 points)

    • testEvaluate: Tests several expressions to make sure they evaluate correctly. (15 points)

    • testputAndGetValid: Tests to make sure only valid java identifiers are added to the SymbolTree and that the correct exceptions are thrown. (10 points)

Submission

Submit P8.jar to Checkin