/** * A4Q1: Purpose of this program is to execute 'milen' programs and store the variables in a hashtable * COMP 2140 SECTION L01 * INSTRUCTOR Helen Cameron * ASSIGNMENT Assignment #4, Question #1 * AUTHOR Jonathan Chartrand, 6818334 * VERSION November 15th, 2007 */import java.io.*;public class A4Q1{//**********************************************************************/** Node * PURPOSE: Node class which is used to store a variable's name and its corresponding value for a milen program. Nodes are used so the program can employ the separate chaining method. */ static class Node { int number = 0; String name = null; Node next = null; //******************** //Constructor //******************** public Node(String name, int number, Node next) { this.name = name; this.number = number; this.next = next; } //******************** //Accessors //******************** public String getName() { return name; } public int getNum() { return number; } public Node getNext() { return next; } //******************** //Mutators //******************** public void setName(String name) { this.name = name; } public void setNum(int number) { this.number = number; } public void setNext(Node next) { this.next = next; } }//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //********************************************************************** /** Hashtable * PURPOSE: stores a variable with its corresponding value into a hashtable. position in which information is stored is based on the variable's name using Horner's method. */ static class Hashtable { int size = 0; Node[] table; int constant = 23; int elements = 0; //******************** //Constructor //******************** public Hashtable() { size = 79; table = new Node[size]; } //******************** //Methods //******************** /**printVariables * PURPOSE: prints all the variables and their corresponding value contained in the hashtable * PARAM: none * RETURN: void */ public void printVariables() { for (int i=0;i<table.length;i++)//goes through each element in the table { if (table[i] != null)//if an element is not null, it contains a value { Node current = table[i]; while (current.getNext() != null)//loop traverses through the chain of nodes (if a chain exists) and prints the entire chain { System.out.println(current.getName() + ": "+current.getNum()); current = current.getNext(); } System.out.println(current.getName() + ": "+current.getNum()); } } } /**search * PURPOSE: searches hashtable to find a variable name that matches the query being made * PARAM: String name: name of variable to find in table * RETURN: Node: object which contains a variable's name and value. if object is not found, null is returned */ public Node search(String name) { int place = Hashcode(name); //resolves the hashcode for the given query boolean found = false; //used to determine if a match is found Node prev = null; //if a match is made to the query, this keeps track of the matched node if (table[place] != null)//checks to see if there is any objects stored at the given hashcode location { Node current = table[place]; while (current != null && !found) //traverses through the node chains (if they exist) and stops if a match is found { if (current.getName().equals(name)) //checks for a match { found = true; } prev = current; current = current.getNext(); } } if (!found) { return null; } else { return prev; } } /**updateValue * PURPOSE: updates a value of a variable in the hashtable if the variable exists * PARAM: String name: name of variable to update * int number: new value to update variable to * RETURN: boolean: whether or not value was successfully updated (true if it succeeds) */ public boolean updateValue(String name, int number) { int place = Hashcode(name); boolean found = false; Node prev; if (table[place] != null) { Node current = table[place]; while (current != null && !found)//traverses chain of nodes { if (current.getName().equals(name))//checks for variable match { found = true; current.setNum(number); //updates variable to new value } prev = current; current = current.getNext(); } } return found; } /**insert * PURPOSE: inserts a variable and its value into the hashtable * PARAM: String name: name of variable * int number: value of variable * RETURN: none */ public void insert(String name, int value) { int place = Hashcode(name);//location in hashtable which variable will resolve to Node temp = new Node(name,value,null);//new node which corresponds to the new variable being added if(table[place] != null)//checks to see if any other variables resolve to the same spot as the new one being added { Node current = table[place]; Node prev = null; boolean dupe = false; //used to keep track of any variable name duplicates are found so they arent added to the table while (current != null && !dupe)//loops through chain of nodes to get to the very last node so that we can add the new variable at the end of the chain { prev = current;//keeps track of the 'previous' node so we can properly add new variable to the end of the node chain current = current.getNext(); if (prev.getName().equals(name)) { dupe = true; } } if (!dupe)//if no variable name duplicates exist.. { prev.setNext(temp);//..we add it to the table } else { System.out.println("Error: variable '"+name+"' already exists in hashtable."); } } else //if no other variables resolve to same point in the hashtable... { table[place] = temp; //we simply store the variable at the point } } /**Hashcode * PURPOSE: generates a hashcode for a hashtable of a given size using horners method * PARAM: String text: name of variable to generate hashcode for * RETURN: int: value of hashcode for given string parameter */ public int Hashcode (String text) { double hashcode = 0;//stores hashcode as a double because un-modulused value may become very large for long strings int character = 0;//temporarily stores integer value of a character for characters in 'text' for (int i=0;i<text.length();i++)//loops through every character in 'text' { if (Character.isDigit(text.charAt(i))) { character = Integer.parseInt( text.substring(i,i+1) ); } else { character = (int)text.charAt(i); } hashcode = hashcode*constant + character; //horniers method for calculating polynomial hashcode } return (int)(hashcode % size); } }/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////**parseEq * PURPOSE: Processes a milen string and validates both sides of the equation. also inserts/updates a variables value in the given hashtable. * PARAM: String text: milen equation to process * Hashtable mytable: hashtable used to lookup,update, and add variables that may be present in given milen equation * RETURN: none. */ public static void parseEq(String text, Hashtable mytable) { /* -assumes milen equations come in two formats: varname = aterm (operator) bterm varname = aterm */ String varname = null; //name of variable on left side of equation String aterm = null; //string of first term on right side of equation String bterm = null; //string of second term on right side of the equation String ErString = null; //string that stores error information int rightside = 0; //final number value of the right side of the equation int aval = 0; //integer value of first term in equation int bval = 0; //integer value of second term in equation char oper = ' ';//stores the operator used on a and b terms int equal = 0; //stores the index at which the equal sign is located in the string int odex = 0; //stores the index at which the operator is found in the string boolean error = false;//if an error occurs, tells this method to print error statement stored in ErString for (int i=0; i<text.length();i++)//loops through each character in given milen equation { if (text.charAt(i) == '=')//finds 'middle' point of equation and stores index of it { equal = i; } if (text.charAt(i) == '+' || text.charAt(i) == '-' || text.charAt(i) == '*' || text.charAt(i) == '/')//if operator is valid, we store the index of it { odex = i; } } varname = text.substring(0,equal).trim(); //determines the left side variable name based on location of equal sign if (odex != 0) //if odex is not 0, right side of equation contains an operator. { oper = text.charAt(odex);//contains operator for aterm and beterm aterm = text.substring(equal+1,odex).trim();//stores the string in which aterm is contained bterm = text.substring(odex+1,text.length()).trim();//stores string in which bterm is contained if (isVar(aterm))//if aterm is a variable.. { Node temp = mytable.search(aterm); //looks up aterm in the hashtable if (temp != null) { aval = temp.getNum(); //gets value of aterm from table } else { ErString = "Variable '"+aterm+"' undeclared."; error = true; } } else //if aterm is just a number.. { aval = Integer.parseInt(aterm); //parses aval as it is to get its value } if (isVar(bterm)) { Node temp = mytable.search(bterm); if(temp != null) { bval = temp.getNum(); } else { ErString = "Variable '"+bterm+"' undeclared."; error = true; } } else { bval = Integer.parseInt(bterm); } // //below statements perform the given operation the values for aterm and bterm if (oper == '+') { rightside = aval + bval; } if (oper == '-') { rightside = aval - bval; } if (oper == '*') { rightside = aval * bval; } if (oper == '/') { rightside = aval / bval; } } else //...if there is no operator and just a single term (aterm) { aterm = text.substring(equal+1,text.length()).trim(); if (isVar(aterm))//...if aterm is a variable { Node temp = mytable.search(aterm); if (temp != null) { rightside = temp.getNum(); } else { ErString = "Variable '"+aterm+"' undeclared."; error = true; } } else//...if aterm is just a number { rightside = Integer.parseInt(aterm); } } if (!error) { if (!mytable.updateValue(varname, rightside))//attempts to update variable on left side (if it exists in hashtable) { mytable.insert(varname, rightside);//if variable on left side doesnt exist in the hashtable, it is inserted as a brand new variable } } else//...if there are any errors, it prints them { System.out.println("error in equation '"+text+"': "+ErString); } } /**isVar * PURPOSE: determines if a string of text is a variable or a number by checking to see if anything other than numbers are in the string. if there are, it is considered a variable * PARAM: String text: string of text to check if it is a 'variable' or not * RETURN: boolean: if string is a variable or not */ public static boolean isVar(String text) { boolean isVar = false; for (int i=0;i<text.length();i++)//checks through every character in string { if (Character.isLetter(text.charAt(i)))//if character is found, string is considered a 'variable' { isVar = true; } } return isVar; } /**Filein * PURPOSE: reads in milen programs from a textfile and processes them * PARAM: String filename: filename to read programs from * RETURN: Hashtable: hashtable with variables read in */ public static Hashtable FileIn(String filename) { int[] array = new int[0];//array is initialized File file = new File(filename); Hashtable mytable = new Hashtable(); try { FileReader file_reader = new FileReader (file); BufferedReader buf_reader = new BufferedReader(file_reader); String line = null; int loops = Integer.parseInt(buf_reader.readLine()); //first line contains number of milen programs to do int count = 0;//keeps track of which milen program a loop is on boolean quit = false;//used to determine when a 'quit' point for a milen program is found line = buf_reader.readLine(); while(count < loops)//loops for as many milen programs the textfile has told us there is in the file { System.out.println("Milen Program "+count+":"); System.out.println("------------------------"); System.out.println("Errors:"); while(line != null && !quit)//loops until text file is empty or quit statement for milen program is found { if (line != " " && line.length() > 0)//if a line isnt blank or just whitespace, the milen statement is processed { parseEq(line,mytable); } line = buf_reader.readLine(); // new line is read in from text file if (line.trim().equals("Q"))//if the new line is a quit line, loop is stopped { quit = true; count++; line = buf_reader.readLine();//reads in new line so current line still isnt quit statement } } System.out.println(); System.out.println("Final values of variables:"); mytable.printVariables(); mytable = new Hashtable(); System.out.println(); quit = false; } buf_reader.close (); } catch (IOException e) { System.out.println ("IO exception =" + e ); } return mytable; } /**main * PURPOSE: creates a hashtable and reads in milen statements from a given textfile * PARAM: None. * RETURN: None. */ public static void main(String[] args) { System.out.println("Comp 2140 Assignment 4 November 2007"); System.out.println ("Executing Milen Programs"); System.out.println("(Author Jonathan Chartrand)"); System.out.println(); System.out.println(); String File = "A4Data.txt"; Hashtable mytable = new Hashtable(); mytable = FileIn(File); System.out.println("Program completed normally."); }}