March 24, 2016 02:37
March 16, 2016 23:19
Blogger
CS 2420 - Assignment 5 - Part 4
At first I had created each class in separate class files, but it was kind of weird how I was parsing the input and how I was building the tree. So I decided to move my Expression Parser class to be nested within my Expression Tree class. This would allow me to do all the parsing and building of the tree within one class file instead of two where it can get messy and confusing.
Here is my new code, thanks for reading:
using System; using System.Collections.Generic; namespace Assignment5 { class ExpressionTree { public TreeNode<string> root; private int node_count; public ExpressionTree(string input) { root = null; ExpressionParser parser = new ExpressionParser(this, input); } private class ExpressionParser { private Stack<TreeNode<string>> numberStack, operatorStack; public ExpressionParser(ExpressionTree tree, string input) { numberStack = new Stack<TreeNode<string>>(); operatorStack = new Stack<TreeNode<string>>(); Console.WriteLine(input.Length); string[] expressionArray = new string[input.Length]; expressionArray = input.Split(); BuildNodes(tree, expressionArray); } private void BuildNodes(ExpressionTree tree, string[] expressionArray) { foreach (string item in expressionArray) { int tempInt; if (Int32.TryParse(item, out tempInt)) { TreeNode<string> number_node = new TreeNode<string> { Data = tempInt.ToString() }; numberStack.Push(number_node); } else
{ TreeNode<string> operator_node = new TreeNode<string> { Data = item }; operatorStack.Push(operator_node); } } BuildTree(tree); } private void BuildTree(ExpressionTree tree) { tree.node_count = numberStack.Count + operatorStack.Count; while (operatorStack.Count != 0) { TreeNode<string> tempRoot = operatorStack.Pop(); tempRoot.Right = numberStack.Pop(); tempRoot.Left = numberStack.Pop(); numberStack.Push(tempRoot); } tree.root = numberStack.Pop(); } } public int NodeCount { get { return node_count; } } // TODO Finish Evaluate public void Evaluate(MyList<string> list, TreeNode<string> node) { if (node.Left != null) Evaluate(list, node.Left); if (node.Right != null) Evaluate(list, node.Right); throw new NotImplementedException(); } public string TraversePre(MyList<string> list, TreeNode<string> node) { list.Add(node.Data); if (node.Left != null) TraversePre(list, node.Left); if (node.Right != null) TraversePre(list, node.Right); return string.Join(", ", list); } public string TraverseIn(MyList<string> list, TreeNode<string> node) { if (node.Left != null) TraverseIn(list, node.Left); list.Add(node.Data); if (node.Right != null) TraverseIn(list, node.Right); return string.Join(", ", list); } public string TraversePost(MyList<string> list, TreeNode<string> node) { if (node.Left != null) TraversePost(list, node.Left); if (node.Right != null) TraversePost(list, node.Right); list.Add(node.Data); return string.Join(", ", list); } } }
March 9, 2016 10:37
Blogger
CS 2420 - Assignment 5 - Part 3
Yesterday after class, I figured out how to finish my Expression Tree and the Parser that takes the user's input.
Expression Tree:
using System; namespace Assignment5 { class ExpressionTree { public TreeNode<string> root; public int node_count; public ExpressionTree() { root = null; } // TODO Finish Evaluate public void Evaluate() { } public string TraversePre(MyList<string> list, TreeNode<string> node) { list.Add(node.data); if (node.left != null) TraversePre(list, node.left); if (node.right != null) TraversePre(list, node.right); return string.Join(", ", list); } public string TraverseIn(MyList<string> list, TreeNode<string> node) { if (node.left != null) TraverseIn(list, node.left); list.Add(node.data); if (node.right != null) TraverseIn(list, node.right); return string.Join(", ", list); } public string TraversePost(MyList<string> list, TreeNode<string> node) { if (node.left != null) TraversePost(list, node.left); if (node.right != null) TraversePost(list, node.right); list.Add(node.data); return string.Join(", ", list); } } }
Parser:
using System; using System.Collections; using System.Collections.Generic; namespace Assignment5 { class ExpressionParser { private Stack<TreeNode<string>> numberStack, operatorStack; public ExpressionParser(ExpressionTree ETree, string input) { numberStack = new Stack<TreeNode<string>>(); operatorStack = new Stack<TreeNode<string>>(); ToArray(ETree, input); } public void ToArray(ExpressionTree ETree, string input) { string[] expressions = new string[input.Length]; expressions = input.Split(); BuildNodes(expressions, ETree); } private void BuildNodes(string[] expressions, ExpressionTree ETree) { foreach (string item in expressions) { int tempInt; if (Int32.TryParse(item, out tempInt)) { TreeNode<string> number_node = new TreeNode<string> { data = tempInt.ToString() }; numberStack.Push(number_node); } else { TreeNode<string> operator_node = new TreeNode<string> { data = item }; operatorStack.Push(operator_node); } } BuildTree(ETree); } private void BuildTree(ExpressionTree ETree) { ETree.node_count = numberStack.Count + operatorStack.Count; while (operatorStack.Count != 0) { TreeNode<string> tempRoot = operatorStack.Pop(); tempRoot.right = numberStack.Pop(); tempRoot.left = numberStack.Pop(); numberStack.Push(tempRoot); } ETree.root = numberStack.Pop(); } } }
I will continue to work on this assignment. Thanks for reading!
March 7, 2016 00:29
Blogger
CS 2420 - Assignment 5 - Part 2
Here is what I have now:
using System; class BinarySearchTree { public TreeNoderoot; private int node_count; public BinarySearchTree() { root = null; node_count = 0; } public void Add(int item) { TreeNode new_node = new TreeNode (item); if (root == null) root = new_node; else { TreeNode crawler = root; while (crawler != null) { new_node.parent = crawler; if (item >= crawler.data) crawler = crawler.right; else crawler = crawler.left; } if (item >= new_node.parent.data) new_node.parent.right = new_node; else new_node.parent.left = new_node; } node_count++; CalculateHeight(root); Console.WriteLine(""); } public TreeNode Contains(int item) { TreeNode crawler = root; while (crawler != null) { if (item == crawler.data) return crawler; else if (item >= crawler.data) crawler = crawler.right; else crawler = crawler.left; } return null; } // TODO Finish Remove function public void Remove(TreeNode node) { if (node == null) Console.WriteLine("\nCould not remove the node you were looking for!\n"); else { //Work needed } } public void Clear() { root = null; node_count = 0; } public int NodeCount { get { return node_count; } } private void CalculateHeight(TreeNode node) { if (node.left != null) CalculateHeight(node.left); if (node.right != null) CalculateHeight(node.right); if (node.left != null && node.right != null) node.height = Math.Max(node.left.height, node.right.height) + 1; else if (node.left != null && node.right == null) node.height = node.left.height + 1; else if (node.left == null && node.right != null) node.height = node.right.height + 1; else if (node.left == null && node.right == null) node.height = 1; Console.WriteLine("Node value: {0} Node Height: {1}", node.data, node.height); CheckBalance(node); } private void CheckBalance(TreeNode node) { if (node.left == null && node.right == null) return; else if (node.left != null && node.right == null) if (node.left.height > 1) Rotate(node); else if (node.left == null && node.right != null) if (node.right.height > 1) Rotate(node); else if (node.left != null && node.right != null) { if (node.left.height > node.right.height + 1) Rotate(node.left); else if (node.right.height > node.left.height + 1) Rotate(node.right); } } // TODO Finish Rotate function private void Rotate(TreeNode node) { //Work needed } public string TraversePre(MyList list, TreeNode node) { list.Add(node.data); if (node.left != null) TraversePre(list, node.left); if (node.right != null) TraversePre(list, node.right); return string.Join(", ", list); } public string TraverseIn(MyList list, TreeNode node) { if (node.left != null) TraverseIn(list, node.left); list.Add(node.data); if (node.right != null) TraverseIn(list, node.right); return string.Join(", ", list); } public string TraversePost(MyList list, TreeNode node) { if (node.left != null) TraversePost(list, node.left); if (node.right != null) TraversePost(list, node.right); list.Add(node.data); return string.Join(", ", list); } }
There has been a few changes to the rest of the code as well. I have been trying to figure out how to make my tree self balancing. And while I have been able to calculate the depth/height of each node, I am running into issues on how I should rotate the nodes. I am also working on removing nodes, but I haven't made much progress in that department either.
Anyways, that's all for now. Thanks for reading!
March 3, 2016 19:24
Blogger
CS 2420 - Assignment 5 - Part 1
The assignment will have us built two trees: a Binary Search Tree and a Binary Expression Tree.
I have started working on both, but I have been mainly focusing on the BS Tree since to me its the easiest of the two. I am actually almost done with the BS Tree, here is what I have:
class BinarySearchTree { public TreeNoderoot; private int node_count; public BinarySearchTree() { root = null; node_count = 0; } public void Add(int item) { TreeNode new_node = new TreeNode (item); if (root == null) root = new_node; else { TreeNode crawler = root; while (crawler != null) { new_node.parent = crawler; if (item >= crawler.data) crawler = crawler.right; else crawler = crawler.left; } if (item >= new_node.parent.data) new_node.parent.right = new_node; else new_node.parent.left = new_node; } node_count++; } public bool Contains(int item) { TreeNode crawler = root; while (crawler != null) { if (item == crawler.data) return true; else if (item >= crawler.data) crawler = crawler.right; else crawler = crawler.left; } return false; } public void Clear() { root = null; node_count = 0; } public int NodeCount { get { return node_count; } } public void TraversePre(MyList list, TreeNode node) { list.Add(node.data); if (node.left != null) TraversePre(list, node.left); if (node.right != null) TraversePre(list, node.right); } public void TraverseIn(MyList list, TreeNode node) { if (node.left != null) TraverseIn(list, node.left); list.Add(node.data); if (node.right != null) TraverseIn(list, node.right); } public void TraversePost(MyList list, TreeNode node) { if (node.left != null) TraversePost(list, node.left); if (node.right != null) TraversePost(list, node.right); list.Add(node.data); } }
My Binary Search Tree takes advantage of the List class I wrote for assignment 4 and of a Node class that has only three properties: Left, Right, & Parent. That's all for now, thanks for reading!
March 1, 2016 17:25
Blogger
Linked List class in C#
I also decided to make my own enumerator for the linked list. Here is what I wrote:
February 26, 2016 22:27
Blogger
CS 2420 - Assignment 4 - Part 5
After thinking about it for a while, I decided that I would create a new class that would just be called from the Main function and it would sort lists of different sizes and it would output the time in milliseconds to a text file. This would make it easier to actually make a graph for each sort. In a graph, X would be the number of elements in the list and Y would be the time it took to sort the list.
Here is what I have for this new class:
using System; using System.Diagnostics; using System.IO; class RunningTimes { public static void SortPlot(ISorter sorter, int elements, string name) { Random randint = new Random(); Stopwatch watch = new Stopwatch(); StreamWriter file = new StreamWriter(@"ChristianMunoz_RunningTimes.txt", true); long time = watch.ElapsedMilliseconds; int[] list; while(elements > 0) { list = new int[elements]; for (int i = 0; i < list.Length; i++) list[i] = randint.Next(1, 200); watch.Reset(); watch.Start(); sorter.sort(list, 0, list.Length); watch.Stop(); time = watch.ElapsedMilliseconds; Console.WriteLine(time); file.WriteLine("Sort: {0} Element count: {1} Time in Milliseconds: {2}", name, elements, time); elements = elements - 10000; } file.WriteLine(" "); file.Close(); } }
In the part that says: @"ChristianMunoz_RunningTimes.txt" that is the location and name of the text file I'm creating. You can change the name to anything you want, and you can find the file in your pc by first going to the folder where you have your C# work: Documents\CSharp\DataStructuresAndSorts\Assignment4\bin\Debug. Or you can also replace the name and tell Visual Studio a specific location by pasting in a path that you want.
This is how I call the function from my main:
RunningTimes.SortPlot(qSorter, 70000, "Quick Sort");
Since this new class isn't doing anything special, I don't have to create a new instance of the class and I can just call it from my other file. In the above example: I pass in a Quick Sort object, I tell it how big I want my list to be (in this case it will be 70000 integers), and just for kicks I pass in a string to make it easier to read the txt file of the sort that I am on. The output of the file will look like this:
Quick Sort Element count: 70000 Time in Milliseconds: 93 Quick Sort Element count: 60000 Time in Milliseconds: 72 Quick Sort Element count: 50000 Time in Milliseconds: 48 Quick Sort Element count: 40000 Time in Milliseconds: 37 Quick Sort Element count: 30000 Time in Milliseconds: 20 Quick Sort Element count: 20000 Time in Milliseconds: S Quick Sort Element count: 10000 Time in Milliseconds: 2
That's all for now, thanks for reading!
February 25, 2016 19:03
Blogger
CS 2420 - Assignment 4 - Part 4
Here is the finished Enumerator class:
private class myEnumerator : IEnumerator{ private MyList myList; private int index; public myEnumerator(MyList myList) { this.myList = myList; index = -1; } public bool MoveNext() { index++; return (index < myList.Count); } public T Current { get { return myList[index]; } } object IEnumerator.Current { get { return Current; } } // Not Needed public void Dispose() { //Not Needed } public void Reset() { index = -1; } }
This new class is embedded in the List class, and it just spits out the next item in the list. The cool thing about this new Enumerator is that it will stop as soon as it reached the Count of the items in the list instead of the length of the array. This way if there are any empty slots in the array, they won't get printed in the list.
That's all for now, thanks for reading!
February 25, 2016 00:41
Blogger
Python Script for Work
A couple days ago, I was actually in the middle of testing an internal tool that we use to send client information to insurance providers. This tool generates XML files from the information that we collect from our customers, and then transmits the information to the insurance providers. We call these tools "dispatchers", and each carrier/provider has its own dispatcher that we use to send the information.
Whenever there is an update to a dispatcher, we have to generate the new XML files to make sure that they have the correct information. But this process can take a while since we have to go manually check each line of the XML to make sure that the information is there. This can get tedious and its just not efficient.
One of my team mates mentioned to me that it would be nice if there was a program we could use to check verify the changes instead of doing it by hand. This got me thinking, and I realized that it wouldn't be very hard to get something working. So today I spent part of the day working on a Python script that I could use to verify the updated XML files. Here is what I wrote:
This script takes two files, one file is the XML that we want to look at and the other is just a simple text file with all the tags that you want to verify that have been added/removed from the XML. I then simply print the tags that were found in the file and done.
While testing my code I found that there is a limitation to my script. For example: if I am looking for a tag call Name, the script will say that it has found the tag in the StateName or DoctorName tags. I haven't had time to work on it further, but hopefully I can figure out a way to search for an exact match only. But if not, I still think that my script will cut down in the time it takes for us to check XML files.
Anyways, that's all for now. Thanks for reading!
February 22, 2016 14:05
Blogger
CS 2420 - Assignment 4 - Part 3
Here is what I have so far:
using System; using System.Collections; using System.Collections.Generic; class MyList: IList { private T[] underlyingArray; private int element_count; public MyList(int initial_size) { underlyingArray = new T[initial_size]; element_count = 0; } public T this[int index] { get { return underlyingArray[index]; } set { underlyingArray[index] = value; } } public int Count { get { return element_count; } } private void UpdateCount(int amount) { element_count += amount; } public bool IsReadOnly { get { return underlyingArray.IsReadOnly; } } public void Add(T item) { try { underlyingArray[Count] = item; UpdateCount(1); } catch (IndexOutOfRangeException) { Resize(underlyingArray); Add(item); } } public void Clear() { for (int index = 0; index < Count; index++) underlyingArray[index] = default(T); UpdateCount(-Count); } public void Resize(T[] array) { T[] newArray = new T[array.Length * 2]; for (int index = 0; index < array.Length; index++) newArray[index] = array[index]; underlyingArray = newArray; } public bool Contains(T item) { for (int index = 0; index < Count; index++) if (EqualityComparer .Default.Equals(underlyingArray[index], item)) return true; return false; } public void CopyTo(T[] array, int arrayIndex) { if (Count == array.Length) Resize(array); for (int index = Count; index > arrayIndex; index--) array[index] = array[index - 1]; underlyingArray = array; } public IEnumerator GetEnumerator() { for (int i = 0; i < underlyingArray.Length; i++) yield return underlyingArray[i]; } // TODO No yield public IEnumerator GetEnumeratorNoYield() { throw new NotImplementedException(); } public int IndexOf(T item) { for (int index = 0; index < Count; index++) if (EqualityComparer .Default.Equals(underlyingArray[index], item)) return index; return -1; } public void Insert(int index, T item) { if (Count == underlyingArray.Length) Resize(underlyingArray); if (index >= Count) Add(item); else { CopyTo(underlyingArray, index); underlyingArray[index] = item; UpdateCount(1); } } public bool Remove(T item) { for (int index = 0; index < Count; index++) if (EqualityComparer .Default.Equals(underlyingArray[index], item)) { RemoveAt(index); return true; } return false; } public void RemoveAt(int index) { while (index < Count - 1) { underlyingArray[index] = underlyingArray[index + 1]; index++; } UpdateCount(-1); underlyingArray[Count] = default(T); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } }
I know that I probably still need to fix a bunch of stuff in my class, but for now I think I'm done with it. I will now focus on writing functions that put my List class to the test.
That's all for now, thanks for reading!
February 17, 2016 21:35
Blogger
CS 2420 - Assignment 4 - Part 2
I am going to be honest here, I had no idea how to start this part of the assignment. At first I thought I was building another Linked List class, but after talking to a friend of mine he got me started on the right direction. He told me that I had to use an array and I had to manually keep track of the items in the array.
I can't just insert items into the array at any index, I have to keep it all together and I have to manage the size of the array as well or use any built in functions. Basically, this is going to be the hardest assignment I've done so far. Here is what I have so far:
using System; using System.Collections; using System.Collections.Generic; class MyList: IList { public T[] underlyingArray; private int element_count; public MyList(int initial_size) { this.underlyingArray = new T[initial_size]; this.element_count = 0; } // TODO Implement: Indexer public T this[int index] { get { throw new NotImplementedException(); } set { throw new NotImplementedException(); } } public int Count { get { return this.element_count; } } public bool IsReadOnly { get { return this.underlyingArray.IsReadOnly; } } // TODO Handle Exception public void Add(T item) { if (element_count < this.underlyingArray.Length) { this.underlyingArray[element_count] = item; this.element_count++; } else throw new IndexOutOfRangeException(); } public void Clear() { this.element_count = 0; } public bool Contains(T item) { for (int index = 0; index < Count; index++) { if (EqualityComparer .Default.Equals(underlyingArray[index], item)); return true; } return false; } // TODO Implement: Copy public void CopyTo(T[] array, int arrayIndex) { throw new NotImplementedException(); } // TODO Implement: Get Enumerator public IEnumerator GetEnumerator() { throw new NotImplementedException(); } // TODO Implement: Index of public int IndexOf(T item) { throw new NotImplementedException(); } // TODO Implement: Insert public void Insert(int index, T item) { throw new NotImplementedException(); } // TODO Implement: Remove public bool Remove(T item) { throw new NotImplementedException(); } // TODO Implement: Remove at public void RemoveAt(int index) { throw new NotImplementedException(); } // TODO Implement: Get IEnumerable IEnumerator IEnumerable.GetEnumerator() { throw new NotImplementedException(); } }
So far I have only worked on a couple of functions, most importantly the Add function. This function will append an item to the end of the list, but I still haven't figured out how to manage the size of the array on my own.
That's all for now, thanks for reading!
February 12, 2016 08:44
Blogger
CS 2420 - Assignment 4 - Part 1
The assignment is split in two parts, first I have to rewrite all my sorts that I've done in past assignments but I have to implement an interface on each sort.
So far I have finished most of the sorts and implement the interface on each. Here is my Quick Sort for reference:
class QuickSort : ISorter { public void sort(int[] numbers, int low, int high) { if (low < high) { int pivot_location = partition(numbers, low, high); sort(numbers, low, pivot_location); sort(numbers, pivot_location + 1, high); } } private static int partition(int[] numbers, int low, int high) { int pivot = numbers[low]; int wall = low; for (int i = low + 1; i < high; i++) { if (numbers[i] < pivot) { wall++; swap_numbers(numbers, i, wall); } } swap_numbers(numbers, low, wall); return wall; } private static void swap_numbers(int[] numbers, int index1, int index2) { int temp = numbers[index1]; numbers[index1] = numbers[index2]; numbers[index2] = temp; } }
I will try to finish this part of the assignment as soon as possible so I can move to the next part. That's all for now, thanks for reading!
February 10, 2016 22:36
Blogger
CS 2420 - Assignment 3
The Linked List was actually fairly straight forward, but the quicksort gave me the most trouble. Here is my file:
February 1, 2016 17:12
Blogger
CS 2420 - Assignment 2
The sorting algorithms gave me the most trouble, but I was able to figure it out. Here is my code:
January 24, 2016 00:25
Blogger
CS 2420 - Assignment 1
For the first assignment we had to write a few different functions using Python, which is great because its the language that I am the most familiar with it. Here is what I have:
Archive
- September 2016
- August 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- July 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- November 2014
- October 2014
- September 2014
- August 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- August 2011
- March 2011
- February 2011
- January 2011
- December 2010
- November 2010
- October 2010
I was not able to make my Binary Search Tree self balancing. I know what I need to do, but I never had time to actually implement the code. I will try to finish writing the code and post it here when I'm done with my AVL tree.
Anyways, that's all for now. Thanks for reading!