COMP 2150 Assignment 4 Winter 2018
Due:
April 9, 2018, before 11:59 pm.
Notes
• Please follow both the “Programming Standards” and “Assignment Guidelines” for all work you submit. Programming standards 1-25 are in effect, but see also the notes in this assignment.
• Make sure to complete the honesty declaration on D2L before the assignment submission. You can’t submit the assignment without completing the online honesty declaration.
• Hand-in will be via the D2L Dropbox facility. Make sure you leave enough time before the deadline to ensure your hand-in works properly. The assignments are submitted using D2L’s time (not the time on your computer). Assignments that are late will be marked according to the late policy in the ROASS.
• All assignments in this course carry an equal weight.
Assignment 4: Expression Trees in Ruby
Description
In this assignment, you will create a binary tree class and then use it to develop an expression tree class.
Binary Tree Class
Create a generic Node class (i.e. an abstract class) and use it to build a Binary Tree class, where a tree consists of Nodes containing a pointer to a left subtree (itself a Binary Tree), and a pointer to a right subtree. Include in-order, post-order, and pre-order traversal methods. Those three methods should not do anything other than traversing the tree in the required order, and should have a yield statement so that we can call them with a block ({} or do-end) of code to be executed during the traversal.
Expression Tree Class
An Expression Tree is a subclass of a Binary Tree and will have three types of nodes: operator, variable, and constant. You MUST use inheritance and create three concrete subclasses.
An operator node will contain a character that is one of ‘+’, ‘-‘, ‘*’, or ‘^’ (addition, subtraction, multiplication, or power, respectively). We will not include division so that we never have fractions or floating point numbers. The power operator (^) has higher priority than the multiplication operator (*), which has higher priority than addition (+) or subtraction (-).
A variable node will contain a character that is a letter giving the name of a variable. A constant node will contain an integer.
The left and right pointers will contain a pointer to a subtree if the node is an operator node, and nil otherwise (i.e. for variable and constant nodes).
COMP 2150 Assignment 4 Winter 2018 Some examples of expression trees are:
A-(B-C): A*(B*(C+D)): (A*B)*(C+D):
-** /\/\/\ A-A**+
/\ /\ /\/\ BC B+ ABCD
/\ CD
Input Format
Commands will be input from a text file (your program should take the name of the file as a command- line argument). The official test data will be available one week before the due date. In the meantime, test your program on the examples given here and your own test data. Assume that the test data is free of errors (i.e. all parentheses are present, all numbers are integers, the only characters are variable names or legal operators).
A comment command will read in a comment from the following line, and echo that comment to the screen.
e.g. comment
Reading expression 1…
A read command will read in a fully parenthesized arithmetic expression from the following line in the file. You will have only one expression tree instance at a time. A later read command will dispose of the old expression and read in a new expression.
e.g. read
((x * 3) – (5 + 9))
Print commands will print the expression by traversing the tree. All print commands should print parentheses to denote the left and right subtrees. The three following methods MUST be implemented and call the corresponding traversal method from Binary Tree with a block.
o printInfix will print the tree on a single line (fully parenthesized) using an inorder traversal.
o printPostfixwillprintthetreeonasingleline(fullyparenthesized)usingapostorder traversal.
o printPrefix will print the tree on a single line (fully parenthesized) using a preorder traversal.
COMP 2150 Assignment 4 Winter 2018
An assign command will read a variable name from the following line, and a fully parenthesized expression from the line following that. You will substitute the expression for the variable in your tree. You may assume that you will only be asked to make legal substitutions, where the variable listed exists in your current expression.
e.g. assign x
((2 * y) + (z + 3))
- A simplify command will use the following rules to simplify the expression: If both operands are constants, calculate the result.
- Simplify when a zero occurs (ex. 0 + a = a, a – 0 = a, 0 * a = 0, a ^ 0 = 1, 0 ^ a = 0)
- Simplify when a one occurs (ex. 1 * a = a, a ^ 1 = a, 1 ^ a = 1)
- A displayStructure command will print the full tree structure, with one node per line, in the format shown below. This command MUST use a ruby code block to call the appropriate traversal method (it is left to you to determine the correct type of traversal to use). In this printed format, write out the full name (ie. a string) of the operators: “add” for +, “subtract” for -, “multiply” for *, “power” for ^.
e.g. for the expression (((42 ^ b) * (9 – x)) + (y + 18)) displayStructure would output:
==> add
| ==> multiply
| | ==> power
| | | ==>42
| | | ==>b
| | ==> subtract | | | ==>9
| | | ==>x
| ==> add
| | ==>y
| | ==>18Example Test Data
comment Reading expression... read ((a+b)*(4+(2-x))) printInfix comment Substituting ((7^3)+9) for b... assign b ((7^3)+9) printInfix
COMP 2150
Assignment 4
Winter 2018
comment Simplifying expression... simplify printInfix
Example Output
Reading expression... (a+b)*(4+(2-x)) Substituting ((7^3)+9) for b... (a+((7^3)+9))*(4+(2-x)) Simplifying expression... (a+352)*(4+(2-x))
Additional Notes
- DATA STRUCTURES: Any data structures used must be implemented by you.
- Your program will be tested by the markers under Unix (on aviary.cs.umanitoba.ca), and must
run with “ruby your_program_name.rb testData.txt” as per the “Running scripts in files” section of the “Running Ruby” instructions on the course website.
Hand-in
Submit all your source code for all classes. You can use modules, as described in the lectures, to break your code into multiple files. Test data will be provided one week before the submission deadline. Submit the output of your program when run with the official test data.
You MUST submit all of your files in a zip file. Additionally, you MUST follow these rules: • All of the files required for your assignment should be in a single directory.
• Include a README.TXT file that describes exactly how to run your code from the command line. The markers will be using these instructions exactly and if your code does not run, you will lose marks.
• Markers will run your program on aviary.cs.umanitoba.ca. Test your program there!
The easier it is to mark your assignment, the more marks you are likely to get. Do yourself a favour.Submit all files on D2L. Remember to submit your electronic honesty declaration on D2L before the assignment deadline.