Description

Introduction

In this assignment, you will practice refactoring and design patterns. You are given working but quite “smelly” code and your task is to refactor and augment this code using appropriate design patterns.

Willy Wazoo has written a program that parses, evaluates and prints boolean expressions, and his code works! The parser takes a string expression in preorder form and constructs a boolean expression tree (as we did in class). In preorder, the operator (AND or OR) appears before the two operands; e.g., x AND y is AND x y, and x AND y OR z is OR AND x y z. For simplicity, AND and OR take exactly two operands. As another example, the expression from lecture, (x OR true) AND y, translates into AND OR x true y in preorder. Note that in preorder there is no need to worry about the order of operations. The reason why Willy chose preorder is that it is much easier to parse an expression if it is in preorder form, than if it is in the “normal” inorder form.

Willy’s code is in directory hw8/ and his test cases are in hw8/test. Willy’s code parses, evaluates in a context of variable-to-boolean mappings, and prints the expressions. It prints the expressions in preorder and in inorder. Printing in inorder is a little more involved, because one must take into account the order of operations and insert parentheses when needed. Recall that in boolean arithmetic NOT has highest precedence, followed by AND, followed by OR. If the preorder expression is AND OR x y z, this should be printed as (x OR y) AND z in inorder, to account for the fact that operand y associates with operator OR and not with operator AND. x OR y AND z is equivalent to x OR (y AND z), which is OR x AND y z in preorder.

Willy’s code works fine, except that he forgot to implement NOT! He tried to add NOT, but quickly became frustrated because it took too many changes in his code.

Problem 1: Boolean Expressions Using Composite, Interpeter and Template Method [25pts]

Your task is to fix Willy’s code. First, list all code smells you identify in Willy’s code in file hw8/answers/problem1.txt. Next, refactor the code, then implement NOT, passing all Willy’s tests. Your refactored code must have a boolean expression hierarchy, as shown in the figure below, with the following interpreter operations:
abstract boolean evaluate(Context); // evaluates this boolean expression
abstract String printPreorder(); // prints this boolean expression in preorder
abstract String printInorder(); // prints this boolean expression in inorder

You may implement other operations as well. For example, Constant may need getValue(), which returns the enclosed boolean constant.

Your refactored code must use (at least) Composite, Interpeter and Template Method and have no code duplication.

Figure 1: A Boolean expression hierarchy using the Composite pattern.

Problem 2: Boolean Expressions Using Composite and Visitor [24pts]

In this part, you will use the Visitor pattern to evaluate expessions and print expressions in inorder. First, augment the boolean expression hiearchy you created in Problem 1 to accept visitors. Next, implement a Visitor hierarchy with Evaluate and PrintInorder Visitors. You should leave the Interpreter-based evaluate and print operations in, however, you should not use these operations with your Visitors!

Fill in methods visitorEvaluate() and visitorPrint() at the end of ExpressionParser.java. These methods create the respective Visitor, start the traversal then retrieve and return the result. Methods visitorEvaluate() are visitorPrint() are called from VisitedExpressionTest, which tests the Visitor implementation.

Reflection [0.5 point]

Please answer the following questions in a file named reflection.txt in your answers/ directory. Answer briefly, but in enough detail to help you improve your own practice via introspection and to enable the course staff to improve Principles of Software in the future.

1. In retrospect, what could you have done better to reduce the time you spent solving this assignment?
2. What could the CSCI 2600 stuff have done better to improve your learning experience in this assignment?
3. What do you know now that you wish you had known before beginning the assignment?

Collaboration [0.5 point]

Please answer the following questions in a file named collaboration.txt in your answers/ directory.

The standard academic integrity policy applies to this assignment.

State whether or not you collaborated with other students. If you did collaborate with other students, state their names and a brief description of how you collaborated.

Grade Breakdown

• Problem 1: ExpressionTest JUnit tests: 10pts (auto-graded)
• Problem 1: Answers to questions in hw8/answers/problem1.txt: 5pts
• Problem 1: Implementation of Composite, Interpeter and Template Method: 10pts
• Problem 2: VisitedExpressionTest JUnit tests: 10pts (auto-graded)
• Problem 2: Implementation of Evaluate and PrintInorder Visitors: 14pts
• Collaboration and reflection: 1pt

Hints

Start by reading the code carefully. Although a mess, the code does have some good ideas.

Remember, the key to refactoring is to make small changes, each change immediately followed by testing. That way, if you break something you’ll know exactly where to look.

What to Turn In

You should add, commit and push the following files to Git:

• hw8/*.java [Refactored boolean expression code. Add as many files as you need.]
• hw8/test/*.java [JUnit test classes you edit or create]
• hw8/answers/problem1.txt
• hw8/answers/reflection.txt
• hw8/answers/collaboration.txt

Errata

None yet.