Can You use intel j Because I use intel j for programming so it is easy for me to run the file
Assignment 3: Hashing COMP 2140, Fall 2021 Due: Tuesday 2 November 2021 at 5:00 p.m Instructions • You must complete the “Honesty Declaration” checklist on the course website before you can submit any assignment. • Assignments must follow the programming standards document published on UM Learn. • After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please see the course outline document published on UM Learn for the course policy for late submissions. • If you make multiple submissions, only the most recent version (the last submission) will be marked. We strongly encourage you to submit early! • These assignments are your chance to learn the material for the exams. Code your assignments inde- pendently. We use software to compare all submitted assignments to each other, and pursue academic dishonesty vigorously. • You can get help from the T.A. during your lab section and from the instructors and from the course Assignment 3 discussion forum on UM Learn. You can discuss general topics related to the assignment with fellow students or other people, but you cannot discuss the solution to the assignment with them. You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a full discussion of our expectations for individual work on this assignment, see the Department of Computer Science’s expectations webpage. • Your Java program must compile and run upon download, without requiring any modifica- tions. The marker will not fix your program’s problems. See also the “Hand in” instructions at the end of this assignment Objective To execute “programs” in a mini “programming language” (Karon) that has only integer variables, assignment statements and simple integer expressions. The Programming Language Karon Here’s an example Karon program length = 13 width = 10 area = length * width extension = 14 fullarea = area + extension t1 = 13 + 63 t1 = t1 / 4 t1 = 65 - t1 1 https://sci.umanitoba.ca/cs/expectations/ A Karon program consists of a sequence of assignment statements. Each assignment statement takes up one line — there are no multi-line assignment statements in Karon. An assignment statement consists of a variable name (described below), followed by an equals sign (=), followed by the right side of the assignment statement, which can have one of the following two forms: 1. It can consist solely of one operand, which can be either an integer constant or a variable name. 2. It can consist of an operand, followed by an operator (’+’, ’-’, ’*’, or ’/’ ), followed by a second operand, where each operand is either an integer constant or a variable name. As you can see, variable names are strings of length at least one beginning with a letter and containing only letters and numbers (all letters are lower case). All variables are integer variables. A variable is “declared” when it first appears on the left side of an assignment statement. In other words, because there are no separate variable declarations, only assignment statements, a variable declaration is an assignment statement that assigns a value to the variable for the first time. So, the first time a variable appears should be on the left side of an assignment statement. If a variable appears on the right side of an assignment statement before it has had a value assigned to it, then we say that the variable is being used before it was declared and that assignment statement contains an error. For example, consider the following Karon program: x = 3 r = x x = x + t t = 36 Variables x and r are properly declared before they are used, but variable t is used before it is declared. Thus, the assignment statement x = x + t is erroneous. The purpose of a Karon program is to compute values and store the values in variables. The output of a Karon program is the values in the variables at the end of the program. Your Program You must write a program that reads in and executes Karon programs. Your program will use a Dictionary to store “variable records”. Each variable record contains a variable name and its associated value, with the variable name being the key. You will implement the Dictionary as a hash table. (More information on the hash table below.) For each assignment statement in a Karon program: • Your program will read in an assignment statement as a String. • You must first compute the value of the right side. – There may be none, one, or two variables on the right side. For example, x = 3 has none, x = 32 + t has one, and x = t * y has two. – For each of the variables on the right side, you must find the variable in the Dictionary to retrieve its value. – For an integer constant, you can use Integer.parseInt() to retrieve its value. – If there’s an operator on the right side, then, once you have the values of its operands, you must perform the operation on the values of the two operands, to get the value of the right side. • Then you must search the Dictionary for the variable on the left side of the assignment statement. – If you find the variable, then you change its value to the value you computed for the right side of this assignment statement. For example, consider the third assignment statement in the following: 2 x1 = 23 y = x1 + 2 y = y * 5 The variable on the left side (y) has already been declared in the previous statement, so it will already be in the Dictionary. Thus, you will find it in the Dictionary, and simply change the value stored with it to 125 (the value of the right side). – If you don’t find the variable in the Dictionary, then this assignment statement is this variable’s declaration. You must add the new variable (as a variable record) to the Dictionary along with the value you computed for it on the right side of the assignment statement. For example, consider the third assignment statement in the following: x2 = 23 y2 = x2 + 2 z = y2 * 5 The variable on the left side (z) has not yet been declared, so this assignment statement is its declaration. You will not find it in the Dictionary, so you will have to insert it along with its value given by the right side (125). • If a variable on the right side is not in the Dictionary, then it has not been declared before being used, so you should print an error message, abandon this assignment statement, and go on to the next assignment statement. When you have executed all the assignment statements in a Karon program, you should print out all the variable names and their values. Hash Table: You must create a Dictionary class that is implemented as a hash table that uses separate chaining to resolve collisions. The dictionary (an array of Nodes — as described in the pre-recorded videos) should have size N = 79 (which is a prime number). You should use the polynomial hash code for the variable name keys (and use Horner’s method to compute the polynomial hash code efficiently). You should use the small prime constant a = 23 for computing the polynomial hash code. Furthermore, for each step of Horner’s method, compute the value modulo the table size N. Dictionary Operations: You must implement the following methods in your Dictionary implementation (hash table): • A constructor, which creates a new, empty Dictionary (for this hash table implementation, the empty Dictionary should have size 79). • search(String variableName), which returns the variable record containing the variable’s name and its associated value, or null if the variable is not in the Dictionary. • insert(String variableName, int variableValue), which inserts the given variable and its associated value into the Dictionary. • updateValue(String variableName, int newValue), which attempts to find the variable in the Dictionary and change its value to the given new value. This method should return true if it succeeds in finding the variable and changing its value, and false if it fails. • printVariables(), which simply goes through the Dictionary and prints out the variables stored in it. Each variable should be printed on a separate line containing the variable name followed by its value. In this hash table implementation, it should simply do a scan through the table, and for each array entry that is not an empty list, it should print out all the variables and their associated values that are stored in the linked list. You may, of course, create other helper methods as needed. 3 The Input: The input file will contain multiple Karon programs. The first line of the input file will contain the number of Karon programs contained in the file. Each Karon program will contain a number of assignment statements, one assignment statement per line. (There may also be blank lines anywhere in a Karon program; simply ignore them.) You may assume that the integer constants, variable names, operator and equals sign within an assignment statement are separated from each other by at least one blank. (There may be multiple blanks between them.) The end of a Karon program will be indicated by a line containing a ‘Q’ (and no other letters, numbers, operators, or equals signs). Notice that the ‘Q’ is uppercase, which differentiates it from a Karon variable, which contains only lowercase letters or numbers. We will provide a larger input file, called “A3bigData.txt”, a few days before the due date. Your program must run on that input file. In the meantime, you can use the smaller input file “A3smallData.txt” to get your code working. Write your own test files, too! (You can find both of these files in the “Assignments” section of the course web site.) Your program should prompt the user for the file to use as input — don’t hard-code file names! The markers should be able to use whatever file they want as input. The Output: The output should begin with an appropriate opening message. Then, for each Karon program, the output should contain an appropriate heading (number the programs), followed by any error messages generated by variables being used before they were declared, followed by a print-out of the final values of the variables after the program has been executed. Finally, the output should end with an appropriate closing message. For example, the output might look like the following: COMP 2140 Assignment 4: Executing Karon Programs Karon Program 0 ---------------- Error messages: Final values of the variables: temp = 43 answer = 166 Karon Program 1 ---------------- Error messages: Error in statement x = t1 * 13: t1 was used before being declared. Final values of the